isCCW static method
Computes whether a ring defined by an array of {@link Coordinate}s is oriented counter-clockwise.
- The list of points is assumed to have the first and last points equal.
- This will handle coordinate lists which contain repeated points.
@param ring an array of Coordinates forming a ring @return true if the ring is oriented counter-clockwise. @throws IllegalArgumentException if there are too few points to determine orientation (< 4)
Implementation
static bool isCCW(List<Coordinate> ring) {
// # of points without closing endpoint
int nPts = ring.length - 1;
// sanity check
if (nPts < 3)
throw new ArgumentError(
"Ring has fewer than 4 points, so orientation cannot be determined");
// find highest point
Coordinate hiPt = ring[0];
int hiIndex = 0;
for (int i = 1; i <= nPts; i++) {
Coordinate p = ring[i];
if (p.y > hiPt.y) {
hiPt = p;
hiIndex = i;
}
}
// find distinct point before highest point
int iPrev = hiIndex;
do {
iPrev = iPrev - 1;
if (iPrev < 0) iPrev = nPts;
} while (ring[iPrev].equals2D(hiPt) && iPrev != hiIndex);
// find distinct point after highest point
int iNext = hiIndex;
do {
iNext = (iNext + 1) % nPts;
} while (ring[iNext].equals2D(hiPt) && iNext != hiIndex);
Coordinate prev = ring[iPrev];
Coordinate next = ring[iNext];
/*
* This check catches cases where the ring contains an A-B-A configuration
* of points. This can happen if the ring does not contain 3 distinct points
* (including the case where the input array has fewer than 4 elements), or
* it contains coincident line segments.
*/
if (prev.equals2D(hiPt) || next.equals2D(hiPt) || prev.equals2D(next))
return false;
int disc = Orientation.index(prev, hiPt, next);
/*
* If disc is exactly 0, lines are collinear. There are two possible cases:
* (1) the lines lie along the x axis in opposite directions (2) the lines
* lie on top of one another
*
* (1) is handled by checking if next is left of prev ==> CCW (2) will never
* happen if the ring is valid, so don't check for it (Might want to assert
* this)
*/
bool isCCW;
if (disc == 0) {
// poly is CCW if prev x is right of next x
isCCW = (prev.x > next.x);
} else {
// if area is positive, points are ordered CCW
isCCW = (disc > 0);
}
return isCCW;
}