algorithm.c

void ui_run_algorithm (Ui *u) {
  GPtrArray *A = u->polys[0],
            *B = u->polys[1],
            *Conv;
  GdkPoint  *a, *b, *c, *ap, *bp,
             p, q;
  guint      i, j;

  reorder (A);
  reorder (B);

  /* Make the lists circular */
  g_ptr_array_add (A, g_ptr_array_index (A, 0));
  g_ptr_array_add (B, g_ptr_array_index (B, 0));

  i = j = 0;

  do {
    a = g_ptr_array_index (A, i);
    b = g_ptr_array_index (B, j);

    c = g_malloc (sizeof (*c));
    assert (c);
    c->x = a->x + b->x;
    c->y = a->y + b->y;
    g_ptr_array_add (u->polys[2], c);

    ap = g_ptr_array_index (A, i+1);
    p.x = ap->x - a->x;
    p.y = ap->y - a->y;
    bp = g_ptr_array_index (B, j+1);
    q.x = bp->x - b->x;
    q.y = bp->y - b->y;

    if (p.x * q.y - q.x * p.y < 0)
      i++;
    else if (p.x * q.y - q.y * p.y > 0)
      j++;
    else {
      i++; j++;
    }

  } while (i < A->len - 1 && j < B->len - 1);

  /* Remove the unneeded point */
  g_ptr_array_remove_index_fast (A, A->len - 1);
  g_ptr_array_remove_index_fast (B, B->len - 1);

  Conv = make_convex_hull (u->polys[2]);
  u->polys[2] = Conv;
}