Listing 6: The search algorithm

triangle run_time::find_triangle(void)
{
  //  Return the zero triangle if one isn't found.
  triangle result;
  result.x[0] = pt(0,0,0);
  result.x[1] = pt(0,0,0);
  result.x[2] = pt(0,0,0);

  int idx0 = conjugate_idx[idx1];
  int first_idx = idx0;
  int next_idx;

  while (1) {
    //  Find the next segment to check out.
    next_idx = postfix(idx0);
    //  If it's gone all the way around the vertex then something
    //  is wrong, avoid an infinit loop.
    if (next_idx == first_idx) break;
    //  Check for boundary segments.
    if (angle(d_array[idx0], d_array[next_idx]) > PI) {
      idx0 = next_idx;
      continue;
    }
    // easier reading:
    double x0 = d_array[idx0][0][0];
    double y0 = d_array[idx0][0][1];
    double x1 = d_array[idx0][1][0];
    double y1 = d_array[idx0][1][1];
    double x2 = d_array[next_idx][1][0];
    double y2 = d_array[next_idx][1][1];
    double xh = helo[0];
    double yh = helo[1];
    //  calculate a and b.
    double denominator = (x1-x0)*(y2-y0) - (x2-x0)*(y1-y0);
    if (denominator == 0.0) { //  move on to the next edge.
      idx0 = next_idx;
      continue;
    }

    double a= ((xh-x0)*(y2-y0) - (x2-x0)*(yh-y0)) / denominator;
    double b= ((x1-x0)*(yh-y0) - (xh-x0)*(y1-y0)) / denominator;

    //  The helicopter is in the wedge if a and b are positive.
    if (a >= 0.0 && b >= 0.0) break;
    idx0 = next_idx;
  } //  end loop;

  //  Find the other endpoint for next iteration.
  idx1 = conjugate_idx[idx0];
  idx0 = next_idx;

  //  Is it closed in on a triangle?
  if (idx0 == idx3) {
    result.x[0] = d_array[idx0][0];
    result.x[1] = d_array[idx1][0];
    result.x[2] = d_array[idx2][0];
  }

  if (use_bgi) {
    setcolor(color+8);
    ++color %= 8;
        line(d_array[idx0][0][0], d_array[idx0][0][1],
            d_array[idx0][1][0], d_array[idx0][1][1]);
  }

  //  shift the indicies for next time.
  idx3 = idx2;
  idx2 = idx1;
  idx1 = idx0;

  return result;
}
//End of File