reduce method

List<Coordinate> reduce(List<Coordinate> inputPts)

Uses a heuristic to reduce the number of points scanned to compute the hull. The heuristic is to find a polygon guaranteed to be in (or on) the hull, and eliminate all points inside it. A quadrilateral defined by the extremal points in the four orthogonal directions can be used, but even more inclusive is to use an octilateral defined by the points in the 8 cardinal directions.

Note that even if the method used to determine the polygon vertices is not 100% robust, this does not affect the robustness of the convex hull.

To satisfy the requirements of the Graham Scan algorithm, the returned array has at least 3 entries.

@param pts the points to reduce @return the reduced list of points (at least 3)

Implementation

List<Coordinate> reduce(List<Coordinate> inputPts) {
  //List<Coordinate> polyPts = computeQuad(inputPts);
  List<Coordinate>? polyPts = computeOctRing(inputPts);
  //List<Coordinate> polyPts = null;

  // unable to compute interior polygon for some reason
  if (polyPts == null) return inputPts;

//    LinearRing ring = geomFactory.createLinearRing(polyPts);
//    System.out.println(ring);

  // add points defining polygon
  var reducedSet = SplayTreeSet<Coordinate>();
  // TreeSet reducedSet = new TreeSet();
  for (int i = 0; i < polyPts.length; i++) {
    reducedSet.add(polyPts[i]);
  }
  /**
   * Add all unique points not in the interior poly.
   * CGAlgorithms.isPointInRing is not defined for points actually on the ring,
   * but this doesn't matter since the points of the interior polygon
   * are forced to be in the reduced set.
   */
  for (int i = 0; i < inputPts.length; i++) {
    if (!PointLocation.isInRing(inputPts[i], polyPts)) {
      reducedSet.add(inputPts[i]);
    }
  }
  List<Coordinate> reducedPts = List.from(
      reducedSet); // CoordinateArrays.toCoordinateArray(reducedSet);

  // ensure that computed array has at least 3 points (not necessarily unique)
  if (reducedPts.length < 3) return padArray3(reducedPts);
  return reducedPts;
}