isCCW static method

bool isCCW(CoordinateSequence ring)

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.

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 an array of Coordinates forming a ring @return true if the ring is oriented counter-clockwise.

Implementation

static bool isCCW(CoordinateSequence ring) {
  // # of points without closing endpoint
  int nPts = ring.size() - 1;

  // find highest point
  double hiy = ring.getOrdinate(0, 1);
  int hiIndex = 0;
  for (int i = 1; i <= nPts; i++) {
    if (ring.getOrdinate(i, 1) > hiy) {
      hiy = ring.getOrdinate(i, 1);
      hiIndex = i;
    }
  }

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

  // find distinct point after highest point
  int iNext = hiIndex;
  do {
    iNext = (iNext + 1) % nPts;
  } while (equals2D(ring, iNext, hiIndex) && 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 (equals2D(ring, iPrev, hiIndex) ||
      equals2D(ring, iNext, hiIndex) ||
      equals2D(ring, iPrev, iNext)) return false;

  int disc = computeOrientation(ring, iPrev, hiIndex, iNext);

  /**
       * 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
       *
       * <p>(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 = false;
  if (disc == 0) {
    // poly is CCW if prev x is right of next x
    isCCW = (ring.getOrdinate(iPrev, 0) > ring.getOrdinate(iNext, 0));
  } else {
    // if area is positive, points are ordered CCW
    isCCW = (disc > 0);
  }
  return isCCW;
}