From bdc29f0cd26f7014c4c1e283496291ddefa61736 Mon Sep 17 00:00:00 2001 From: Martin Davis Date: Fri, 26 Apr 2019 21:29:27 -0700 Subject: [PATCH 1/5] Improve Convex Hull performance by avoid computing unique pts where possible Signed-off-by: Martin Davis --- .../jts/algorithm/ConvexHull.java | 88 +++++++++++++------ 1 file changed, 60 insertions(+), 28 deletions(-) diff --git a/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java b/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java index 665d0b4a08..5c464a825e 100644 --- a/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java +++ b/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java @@ -14,10 +14,9 @@ import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; -import java.util.List; +import java.util.HashSet; import java.util.Set; import java.util.Stack; -import java.util.TreeSet; import org.locationtech.jts.geom.Coordinate; import org.locationtech.jts.geom.CoordinateArrays; @@ -30,7 +29,6 @@ import org.locationtech.jts.geom.Point; import org.locationtech.jts.geom.Polygon; import org.locationtech.jts.util.Assert; -import org.locationtech.jts.util.UniqueCoordinateArrayFilter; /** * Computes the convex hull of a {@link Geometry}. @@ -43,6 +41,8 @@ */ public class ConvexHull { + private static final int TUNING_REDUCE_SIZE = 50; + private GeometryFactory geomFactory; private Coordinate[] inputPts; @@ -51,25 +51,17 @@ public class ConvexHull */ public ConvexHull(Geometry geometry) { - this(extractCoordinates(geometry), geometry.getFactory()); + this(geometry.getCoordinates(), geometry.getFactory()); } /** * Create a new convex hull construction for the input {@link Coordinate} array. */ public ConvexHull(Coordinate[] pts, GeometryFactory geomFactory) { - inputPts = UniqueCoordinateArrayFilter.filterCoordinates(pts); - //inputPts = pts; + inputPts = pts; this.geomFactory = geomFactory; } - private static Coordinate[] extractCoordinates(Geometry geom) - { - UniqueCoordinateArrayFilter filter = new UniqueCoordinateArrayFilter(); - geom.apply(filter); - return filter.getCoordinates(); - } - /** * Returns a {@link Geometry} that represents the convex hull of the input * geometry. @@ -84,21 +76,19 @@ private static Coordinate[] extractCoordinates(Geometry geom) */ public Geometry getConvexHull() { - if (inputPts.length == 0) { - return geomFactory.createGeometryCollection(); - } - if (inputPts.length == 1) { - return geomFactory.createPoint(inputPts[0]); - } - if (inputPts.length == 2) { - return geomFactory.createLineString(inputPts); - } - + Geometry fewPointsGeom = createFewPointsResult(); + if (fewPointsGeom != null) + return fewPointsGeom; + Coordinate[] reducedPts = inputPts; // use heuristic to reduce points, if large - if (inputPts.length > 50) { + if (inputPts.length > TUNING_REDUCE_SIZE) { reducedPts = reduce(inputPts); } + else { + // the points must be made unique + reducedPts = extractUnique(inputPts); + } // sort points for Graham scan. Coordinate[] sortedPts = preSort(reducedPts); @@ -112,6 +102,46 @@ public Geometry getConvexHull() { return lineOrPolygon(cH); } + private Geometry createFewPointsResult() { + Coordinate[] uniquePts = extractUnique(inputPts, 3); + if (uniquePts == null) { + return null; + } + else if (uniquePts.length == 0) { + return geomFactory.createGeometryCollection(); + } + else if (uniquePts.length == 1) { + return geomFactory.createPoint(uniquePts[0]); + } + else { + return geomFactory.createLineString(uniquePts); + } + } + + private static Coordinate[] extractUnique(Coordinate[] pts) { + return extractUnique(pts, -1); + } + + /** + * Extracts unique coordinates from an array of coordinates, + * up to a maximum count of values. + * If there are more than the given maximum of unique values + * found, indicates this by returning null + * (the expectation is that the original array can then be used). + * + * @param pts an array of Coordinates + * @param maxPts the maximum number of unique points to scan + * @return an array of unique values, or null + */ + private static Coordinate[] extractUnique(Coordinate[] pts, int maxPts) { + Set uniquePts = new HashSet(); + for (Coordinate pt : pts) { + uniquePts.add(pt); + if (maxPts >= 0 && uniquePts.size() >= maxPts) return null; + } + return CoordinateArrays.toCoordinateArray(uniquePts); + } + /** * An alternative to Stack.toArray, which is not present in earlier versions * of Java. @@ -140,6 +170,9 @@ protected Coordinate[] toCoordinateArray(Stack stack) { *

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

+ * This has the side effect of making the reduced points unique, + * as required by the convex hull algorithm used. * * @param pts the points to reduce * @return the reduced list of points (at least 3) @@ -148,8 +181,7 @@ private Coordinate[] reduce(Coordinate[] inputPts) { //Coordinate[] polyPts = computeQuad(inputPts); Coordinate[] polyPts = computeOctRing(inputPts); - //Coordinate[] polyPts = null; - + // unable to compute interior polygon for some reason if (polyPts == null) return inputPts; @@ -158,13 +190,13 @@ private Coordinate[] reduce(Coordinate[] inputPts) // System.out.println(ring); // add points defining polygon - Set reducedSet = new TreeSet(); + Set reducedSet = new HashSet(); 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, + * CGAlgorithms.isPointInRing is not defined for points exactly on the ring, * but this doesn't matter since the points of the interior polygon * are forced to be in the reduced set. */ From e4f8510ae972a4cc8d6b1870fab96b8ea2bab85f Mon Sep 17 00:00:00 2001 From: Martin Davis Date: Tue, 20 Jun 2023 18:03:01 -0700 Subject: [PATCH 2/5] Add List import --- .../src/main/java/org/locationtech/jts/algorithm/ConvexHull.java | 1 + 1 file changed, 1 insertion(+) diff --git a/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java b/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java index 5c464a825e..cdeb387eb4 100644 --- a/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java +++ b/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java @@ -15,6 +15,7 @@ import java.util.Arrays; import java.util.Comparator; import java.util.HashSet; +import java.util.List; import java.util.Set; import java.util.Stack; From e47e7ef8ed85678425a8e4a0f8fa43b9dc36af29 Mon Sep 17 00:00:00 2001 From: Martin Davis Date: Tue, 20 Jun 2023 19:55:33 -0700 Subject: [PATCH 3/5] Add performance test --- .../perf/algorithm/ConvexHullPerfTest.java | 48 +++++++++++++++++++ 1 file changed, 48 insertions(+) create mode 100644 modules/core/src/test/java/test/jts/perf/algorithm/ConvexHullPerfTest.java diff --git a/modules/core/src/test/java/test/jts/perf/algorithm/ConvexHullPerfTest.java b/modules/core/src/test/java/test/jts/perf/algorithm/ConvexHullPerfTest.java new file mode 100644 index 0000000000..fc551f8f02 --- /dev/null +++ b/modules/core/src/test/java/test/jts/perf/algorithm/ConvexHullPerfTest.java @@ -0,0 +1,48 @@ +package test.jts.perf.algorithm; + +import java.util.ArrayList; +import java.util.Random; + +import org.locationtech.jts.geom.Coordinate; +import org.locationtech.jts.geom.Geometry; +import org.locationtech.jts.geom.GeometryFactory; +import org.locationtech.jts.geom.MultiPoint; +import org.locationtech.jts.util.GeometricShapeFactory; + +import test.jts.perf.PerformanceTestCase; +import test.jts.perf.PerformanceTestRunner; + +public class ConvexHullPerfTest extends PerformanceTestCase { + public static void main(String args[]) { + PerformanceTestRunner.run(ConvexHullPerfTest.class); + } + + private MultiPoint geom; + + public ConvexHullPerfTest(String name) + { + super(name); + setRunSize(new int[] { 1000, 10_000, 100_000, 1_000_000 }); + setRunIterations(100); + } + + public void startRun(int num) + { + System.out.println("Running with size " + num); + geom = createRandomMultiPoint(num); + } + + private MultiPoint createRandomMultiPoint(int num) { + Coordinate[] pts = new Coordinate[num]; + Random rand = new Random(1324); + for (int i = 0; i < num; i++) { + pts[i] = new Coordinate(rand.nextDouble()*100, rand.nextDouble()*100); + } + GeometryFactory fact = new GeometryFactory(); + return fact.createMultiPointFromCoords(pts); + } + + public void runConvexHull() { + Geometry convextHull = geom.convexHull(); + } +} From a2facfebe0befde507da20d7621efb011ef93577 Mon Sep 17 00:00:00 2001 From: Martin Davis Date: Tue, 20 Jun 2023 19:56:48 -0700 Subject: [PATCH 4/5] Renaming --- .../jts/algorithm/ConvexHull.java | 21 +++++++++++-------- 1 file changed, 12 insertions(+), 9 deletions(-) diff --git a/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java b/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java index cdeb387eb4..1dabc1d2c5 100644 --- a/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java +++ b/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java @@ -58,7 +58,10 @@ public ConvexHull(Geometry geometry) * Create a new convex hull construction for the input {@link Coordinate} array. */ public ConvexHull(Coordinate[] pts, GeometryFactory geomFactory) - { + { + //-- performance testing only + //inputPts = UniqueCoordinateArrayFilter.filterCoordinates(pts); + inputPts = pts; this.geomFactory = geomFactory; } @@ -181,10 +184,10 @@ protected Coordinate[] toCoordinateArray(Stack stack) { private Coordinate[] reduce(Coordinate[] inputPts) { //Coordinate[] polyPts = computeQuad(inputPts); - Coordinate[] polyPts = computeOctRing(inputPts); + Coordinate[] innerRingPts = computeInnerOctagonRing(inputPts); // unable to compute interior polygon for some reason - if (polyPts == null) + if (innerRingPts == null) return inputPts; // LinearRing ring = geomFactory.createLinearRing(polyPts); @@ -192,8 +195,8 @@ private Coordinate[] reduce(Coordinate[] inputPts) // add points defining polygon Set reducedSet = new HashSet(); - for (int i = 0; i < polyPts.length; i++) { - reducedSet.add(polyPts[i]); + for (int i = 0; i < innerRingPts.length; i++) { + reducedSet.add(innerRingPts[i]); } /** * Add all unique points not in the interior poly. @@ -202,7 +205,7 @@ private Coordinate[] reduce(Coordinate[] inputPts) * are forced to be in the reduced set. */ for (int i = 0; i < inputPts.length; i++) { - if (! PointLocation.isInRing(inputPts[i], polyPts)) { + if (! PointLocation.isInRing(inputPts[i], innerRingPts)) { reducedSet.add(inputPts[i]); } } @@ -310,8 +313,8 @@ private boolean isBetween(Coordinate c1, Coordinate c2, Coordinate c3) { return false; } - private Coordinate[] computeOctRing(Coordinate[] inputPts) { - Coordinate[] octPts = computeOctPts(inputPts); + private Coordinate[] computeInnerOctagonRing(Coordinate[] inputPts) { + Coordinate[] octPts = computeInnerOctagonPts(inputPts); CoordinateList coordList = new CoordinateList(); coordList.add(octPts, false); @@ -323,7 +326,7 @@ private Coordinate[] computeOctRing(Coordinate[] inputPts) { return coordList.toCoordinateArray(); } - private Coordinate[] computeOctPts(Coordinate[] inputPts) + private Coordinate[] computeInnerOctagonPts(Coordinate[] inputPts) { Coordinate[] pts = new Coordinate[8]; for (int j = 0; j < pts.length; j++) { From 031db398620a42cd4bdce7efd168e434ef7b30a0 Mon Sep 17 00:00:00 2001 From: Martin Davis Date: Tue, 20 Jun 2023 22:07:38 -0700 Subject: [PATCH 5/5] Javadoc, renaming --- .../jts/algorithm/ConvexHull.java | 55 +++++++++++++------ 1 file changed, 38 insertions(+), 17 deletions(-) diff --git a/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java b/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java index 1dabc1d2c5..438d69f718 100644 --- a/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java +++ b/modules/core/src/main/java/org/locationtech/jts/algorithm/ConvexHull.java @@ -37,6 +37,9 @@ * points in the input Geometry. *

* Uses the Graham Scan algorithm. + *

+ * Incorporates heuristics to optimize checking for degenerate results, + * and to reduce the number of points processed for large inputs. * *@version 1.7 */ @@ -59,7 +62,7 @@ public ConvexHull(Geometry geometry) */ public ConvexHull(Coordinate[] pts, GeometryFactory geomFactory) { - //-- performance testing only + //-- suboptimal early uniquing - for performance testing only //inputPts = UniqueCoordinateArrayFilter.filterCoordinates(pts); inputPts = pts; @@ -85,12 +88,12 @@ public Geometry getConvexHull() { return fewPointsGeom; Coordinate[] reducedPts = inputPts; - // use heuristic to reduce points, if large + //-- use heuristic to reduce points, if large if (inputPts.length > TUNING_REDUCE_SIZE) { reducedPts = reduce(inputPts); } else { - // the points must be made unique + //-- the points must be made unique reducedPts = extractUnique(inputPts); } // sort points for Graham scan. @@ -103,11 +106,24 @@ public Geometry getConvexHull() { Coordinate[] cH = toCoordinateArray(cHS); // Convert array to appropriate output geometry. + // (an empty or point result will be detected earlier) return lineOrPolygon(cH); } + /** + * Checks if there are <= 2 unique points, + * which produce an obviously degenerate result. + * If there are more points, returns null to indicate this. + * + * This is a fast check for an obviously degenerate result. + * If the result is not obviously degenerate (at least 3 unique points found) + * the full uniquing of the entire point set is + * done only once during the reduce phase. + * + * @return a degenerate hull geometry, or null if the number of input points is large + */ private Geometry createFewPointsResult() { - Coordinate[] uniquePts = extractUnique(inputPts, 3); + Coordinate[] uniquePts = extractUnique(inputPts, 2); if (uniquePts == null) { return null; } @@ -129,8 +145,8 @@ private static Coordinate[] extractUnique(Coordinate[] pts) { /** * Extracts unique coordinates from an array of coordinates, * up to a maximum count of values. - * If there are more than the given maximum of unique values - * found, indicates this by returning null + * If more than the given maximum of unique values are found, + * this is reported by returning null. * (the expectation is that the original array can then be used). * * @param pts an array of Coordinates @@ -141,7 +157,7 @@ private static Coordinate[] extractUnique(Coordinate[] pts, int maxPts) { Set uniquePts = new HashSet(); for (Coordinate pt : pts) { uniquePts.add(pt); - if (maxPts >= 0 && uniquePts.size() >= maxPts) return null; + if (maxPts >= 0 && uniquePts.size() > maxPts) return null; } return CoordinateArrays.toCoordinateArray(uniquePts); } @@ -184,10 +200,10 @@ protected Coordinate[] toCoordinateArray(Stack stack) { private Coordinate[] reduce(Coordinate[] inputPts) { //Coordinate[] polyPts = computeQuad(inputPts); - Coordinate[] innerRingPts = computeInnerOctagonRing(inputPts); + Coordinate[] innerPolyPts = computeInnerOctolateralRing(inputPts); // unable to compute interior polygon for some reason - if (innerRingPts == null) + if (innerPolyPts == null) return inputPts; // LinearRing ring = geomFactory.createLinearRing(polyPts); @@ -195,8 +211,8 @@ private Coordinate[] reduce(Coordinate[] inputPts) // add points defining polygon Set reducedSet = new HashSet(); - for (int i = 0; i < innerRingPts.length; i++) { - reducedSet.add(innerRingPts[i]); + for (int i = 0; i < innerPolyPts.length; i++) { + reducedSet.add(innerPolyPts[i]); } /** * Add all unique points not in the interior poly. @@ -205,7 +221,7 @@ private Coordinate[] reduce(Coordinate[] inputPts) * are forced to be in the reduced set. */ for (int i = 0; i < inputPts.length; i++) { - if (! PointLocation.isInRing(inputPts[i], innerRingPts)) { + if (! PointLocation.isInRing(inputPts[i], innerPolyPts)) { reducedSet.add(inputPts[i]); } } @@ -313,8 +329,8 @@ private boolean isBetween(Coordinate c1, Coordinate c2, Coordinate c3) { return false; } - private Coordinate[] computeInnerOctagonRing(Coordinate[] inputPts) { - Coordinate[] octPts = computeInnerOctagonPts(inputPts); + private Coordinate[] computeInnerOctolateralRing(Coordinate[] inputPts) { + Coordinate[] octPts = computeInnerOctolateralPts(inputPts); CoordinateList coordList = new CoordinateList(); coordList.add(octPts, false); @@ -326,7 +342,14 @@ private Coordinate[] computeInnerOctagonRing(Coordinate[] inputPts) { return coordList.toCoordinateArray(); } - private Coordinate[] computeInnerOctagonPts(Coordinate[] inputPts) + /** + * Computes the extremal points of an inner octolateral. + * Some points may be duplicates - these are collapsed later. + * + * @param inputPts the points to compute the octolateral for + * @return the extremal points of the octolateral + */ + private Coordinate[] computeInnerOctolateralPts(Coordinate[] inputPts) { Coordinate[] pts = new Coordinate[8]; for (int j = 0; j < pts.length; j++) { @@ -374,8 +397,6 @@ private Geometry lineOrPolygon(Coordinate[] coordinates) { coordinates = cleanRing(coordinates); if (coordinates.length == 3) { return geomFactory.createLineString(new Coordinate[]{coordinates[0], coordinates[1]}); -// return new LineString(new Coordinate[]{coordinates[0], coordinates[1]}, -// geometry.getPrecisionModel(), geometry.getSRID()); } LinearRing linearRing = geomFactory.createLinearRing(coordinates); return geomFactory.createPolygon(linearRing);