polarCompare method

int polarCompare(
  1. Coordinate o,
  2. Coordinate p,
  3. Coordinate q
)

Given two points p and q compare them with respect to their radial ordering about point o. First checks radial ordering. If points are collinear, the comparison is based on their distance to the origin.

p < q iff

  • ang(o-p) < ang(o-q) (e.g. o-p-q is CCW)
  • or ang(o-p) == ang(o-q) && dist(o,p) < dist(o,q)

@param o the origin @param p a point @param q another point @return -1, 0 or 1 depending on whether p is less than, equal to or greater than q

Implementation

int polarCompare(Coordinate o, Coordinate p, Coordinate q) {
  double dxp = p.x - o.x;
  double dyp = p.y - o.y;
  double dxq = q.x - o.x;
  double dyq = q.y - o.y;

  int orient = Orientation.index(o, p, q);

  if (orient == Orientation.COUNTERCLOCKWISE) return 1;
  if (orient == Orientation.CLOCKWISE) return -1;

  // points are collinear - check distance
  double op = dxp * dxp + dyp * dyp;
  double oq = dxq * dxq + dyq * dyq;
  if (op < oq) {
    return -1;
  }
  if (op > oq) {
    return 1;
  }
  return 0;
}