polarCompare method
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;
}