compareDirection method

int compareDirection(
  1. EdgeEnd e
)

Implements the total order relation:

a has a greater angle with the positive x-axis than b

Using the obvious algorithm of simply computing the angle is not robust, since the angle calculation is obviously susceptible to roundoff. A robust algorithm is: - first compare the quadrant. If the quadrants are different, it it trivial to determine which vector is "greater". - if the vectors lie in the same quadrant, the computeOrientation function can be used to decide the relative orientation of the vectors.

Implementation

int compareDirection(EdgeEnd e) {
  if (dx == e.dx && dy == e.dy) return 0;
  // if the rays are in different quadrants, determining the ordering is trivial
  if (quadrant > e.quadrant) return 1;
  if (quadrant < e.quadrant) return -1;
  // vectors are in the same quadrant - check relative orientation of direction vectors
  // this is > e if it is CCW of e
  return Orientation.index(e.p0!, e.p1!, p1!);
}