isCCWFromSeq static method

bool isCCWFromSeq(CoordinateSequence ring)

Computes whether a ring defined by an {@link CoordinateSequence} 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.

This algorithm is only guaranteed to work with valid rings. If the ring is invalid (e.g. self-crosses or touches), the computed result may not be correct.

@param ring a CoordinateSequence 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 isCCWFromSeq(CoordinateSequence ring) {
  // # of points without closing endpoint
  int nPts = ring.size() - 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.getCoordinate(0);
  int hiIndex = 0;
  for (int i = 1; i <= nPts; i++) {
    Coordinate p = ring.getCoordinate(i);
    if (p.y > hiPt.y) {
      hiPt = p;
      hiIndex = i;
    }
  }

  // find distinct point before highest point
  Coordinate prev;
  int iPrev = hiIndex;
  do {
    iPrev = iPrev - 1;
    if (iPrev < 0) iPrev = nPts;
    prev = ring.getCoordinate(iPrev);
  } while (prev.equals2D(hiPt) && iPrev != hiIndex);

  // find distinct point after highest point
  Coordinate next;
  int iNext = hiIndex;
  do {
    iNext = (iNext + 1) % nPts;
    next = ring.getCoordinate(iNext);
  } while (next.equals2D(hiPt) && iNext != hiIndex);

  /*
   * 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;
}