Listing 3: Create the problem-world triangulation

void triangulation::create_triangulation(void)
{
  int i,j;
  int array_size = a_array_size * (a_array_size +1) / 2; // all pairs
  b_array = new(segment[array_size]);
  if (b_array == NULL) {
    printf("b_array out of mem ");
    return;
  }
  array_size = 3 * (a_array_size - 1);  // upper bound.
  c_array = new(vector[array_size]);
  if (c_array == NULL) {
    printf("c_array out of mem ");
    return;
  }
  array_size *= 2;
  d_array = new(vector[array_size]);
  if (d_array == NULL) {
    printf("d_array out of mem ");
    return;
  }
  conjugate_idx = new(int[array_size]);
  if (conjugate_idx == NULL) {
    printf("conj_idx out of mem ");
    return;
  }

  for (i=0; i<a_array_size; i++)
    for (j=i+1; j<a_array_size; j++)
      b_array[b_array_size++] = segment(a_array[i], a_array[j]);

  //if (use_bgi) printf("sort b_array ");
  shell_sort_b_array();

  vector unit(pt(1.0,0.0,0.0),pt(0.0,0.0,0.0));
  for (i=0; i<b_array_size; i++) {
    for (j=0; j<c_array_size; j++)
      if (intersect(c_array[j], b_array[i])) break;
    if (j == c_array_size) { // no intersections were found.
      c_array[c_array_size] = vector(b_array[i][0], b_array[i][1]);
      d_array[d_array_size++] = vector(b_array[i][0], b_array[i][1]);
      d_array[d_array_size++] = vector(b_array[i][1], b_array[i][0]);
      if (angle(unit, c_array[c_array_size]) >= PI)
        c_array[c_array_size] = vector(b_array[i][1], b_array[i][0]);
      if (use_bgi) {
        line(b_array[i][0][0], b_array[i][0][1],
            b_array[i][1][0], b_array[i][1][1]);
        getch();
      }
      ++c_array_size;
    }
  } // triangulation is done.

  //if (use_bgi) printf("sort d_array ");
  shell_sort_d_array();
  //  create the conjugate_idx
  for (i=0; i<d_array_size; i++) {
    for (j=0; j<d_array_size; j++) {
      if ((d_array[i][0] == d_array[j][1]) &&
          (d_array[i][1] == d_array[j][0])) {
        conjugate_idx[i] = j;
        break;
      } // end if
    } //  end for j
    if (j == d_array_size) return; //error
  } //  end for i
}
//End of File