orientationIndexFilter static method

int orientationIndexFilter(Coordinate pa, Coordinate pb, Coordinate pc)

A filter for computing the orientation index of three coordinates.

If the orientation can be computed safely using standard DP arithmetic, this routine returns the orientation index. Otherwise, a value i > 1 is returned. In this case the orientation index must be computed using some other more robust method. The filter is fast to compute, so can be used to avoid the use of slower robust methods except when they are really needed, thus providing better average performance.

Uses an approach due to Jonathan Shewchuk, which is in the domain.

@param pa a coordinate @param pb a coordinate @param pc a coordinate @return the orientation index if it can be computed safely @return i > 1 if the orientation index cannot be computed safely

Implementation

static int orientationIndexFilter(
    Coordinate pa, Coordinate pb, Coordinate pc) {
  double detsum;

  double detleft = (pa.x - pc.x) * (pb.y - pc.y);
  double detright = (pa.y - pc.y) * (pb.x - pc.x);
  double det = detleft - detright;

  if (detleft > 0.0) {
    if (detright <= 0.0) {
      return signum(det);
    } else {
      detsum = detleft + detright;
    }
  } else if (detleft < 0.0) {
    if (detright >= 0.0) {
      return signum(det);
    } else {
      detsum = -detleft - detright;
    }
  } else {
    return signum(det);
  }

  double errbound = DP_SAFE_EPSILON * detsum;
  if ((det >= errbound) || (-det >= errbound)) {
    return signum(det);
  }

  return 2;
}