locationtech · dr-jts · May 9, 2022 · May 7, 2022 · May 7, 2022 · May 9, 2022
diff --git a/doc/JTS_Version_History.md b/doc/JTS_Version_History.md
@@ -45,7 +45,7 @@ Distributions for older JTS versions can be obtained at the
 * Fix `WKTReader` geometry typename parsing (#786)
 * Fix `CoordinateArrays.reverse` to handle zero-length arrays #787
 * Fix `GeometryFixer` to appply `isKeepCollapsed` flag to `GeometryCollection` elements (#790)
-* Fix `RectangleIntersects` to handle XYZM geometry (#794) 
+* Fix `RectangleIntersects` to handle XYZM geometry (#794)
 * Fix various operations to handle XYZM geometry (#795)
 * Fix `SnapRoundingNoder` to use tolerance in noding (also fixes `GeometryPrecisionReducer`) (#802)
 * Fix `MaximumInscribedCircle` to avoid infinite-looping on flat collapsed input (#807)
@@ -55,10 +55,11 @@ Distributions for older JTS versions can be obtained at the
 * Fix `RelateOp` for a snapped line boundary point (#839)
 * Fix IsValidOp for repeated node points (#845)
 * Fix `IsSimpleOp` for repeated endpoints (#851)
+* Fix `GeometryFixer` via noding check for zero-distance buffers (#867)
 
 # Version 1.18.2
 
-*Release Date: 08/27/2021* 
+*Release Date: 08/27/2021*
 
 ### API Changes
 
@@ -77,7 +78,7 @@ Distributions for older JTS versions can be obtained at the
 * Fix `MultiPoint.isValid` to check validity correctly (#700)
 * Fix `WKTReader` and `WKTWriter` handling of collections with all empty elements (#702)
 * Fix `HalfEdge.prev()` method (#703)
-* Fix `BufferOp` to remove invalid elements caused by inverted ring curves (#706) 
+* Fix `BufferOp` to remove invalid elements caused by inverted ring curves (#706)
 * Fix `IsSimpleOp` duplicate lines bug (#716)
 * Fix `Angle.interiorAngle` to produce interior angle correctly (#721)
 * Fix `IsValidOp` to correctly report invalidity for certain kinds of LinearRings (#737)
@@ -101,7 +102,7 @@ Distributions for older JTS versions can be obtained at the
 * Improve `Densifier` splitting algorithm to create longer segments (#677)
 * Allow constructing invalid `Polygon`s and `LinearRing`s with only 3 vertices (#682)
 * Ensure invalid 3-point polygons and rings are handled correctly (#683)
-* Fix `GeoJSONReader` to parse null and empty coordinates as empty geometry (#687) 
+* Fix `GeoJSONRead
8000
er` to parse null and empty coordinates as empty geometry (#687)
 * Fix `GeoJSONWriter` to emit empty coordinates array for empty point and linestring (#688)
 * Add `MaximumInscribedCircle` check for invalid tolerance, to avoid infinite loops (#696)
 * Add `GeoJsonWriter.setForceCCW` method to emit polygons with CCW orientation, as per GeoJSON specification (#694)
@@ -111,7 +112,7 @@ Distributions for older JTS versions can be obtained at the
 * Ensure `Densifier` creates `Coordinate`s with same class as input (#637)
 * Fix Relate for cases with closed linear geometry and empty geometry (#671)
 * Fix `Densifier` to avoid splitting segments with length equal to distance tolerance (#676)
-* Fix `Geometry.compareTo` to test polygon holes (#678) 
+* Fix `Geometry.compareTo` to test polygon holes (#678)
 * Fix OverlayNG handling of polygons with interior flat lines (#685)
 * Fix `Polygonizer` to avoid NPE on invalid input (#692)
 
@@ -209,7 +210,7 @@ Distributions for older JTS versions can be obtained at the
 * Enhance `-geomfunc` to load multiple function classes
 * Fix function registry to replace matching loaded functions (#569)
 
-## JtsOp 
+## JtsOp
 
 * Added `-limit` and `-offset` options for reading from file inputs (#617)
 
@@ -224,7 +225,7 @@ Distributions for older JTS versions can be obtained at the
 
 ### API Changes
 
-* Change `Polygon` `getExteriorRing` and `getInteriorRingN` accessors to return `LinearRing`. 
+* Change `Polygon` `getExteriorRing` and `getInteriorRingN` accessors to return `LinearRing`.
   * *This is a binary incompatible change to the method signature.  Recompilation is necessary. No source code changes are required.*
 
 ### Functionality Improvements
@@ -261,10 +262,10 @@ Distributions for older JTS versions can be obtained at the
 * Fix bug in `HalfEdge.insert` method which caused CCW order not to be preserved in some cases
 * Fix generation of Voronoi diagrams for cases with sites in a square (#447)
 * Fix use of clipping envelope in `VoronoiDiagramBuilder`
-* Fix infinite loop on empty input in `IndexedPointInAreaLocator` and `SortedPackedIntervalRTree` (#462) 
+* Fix infinite loop on empty input in `IndexedPointInAreaLocator` and `SortedPackedIntervalRTree` (#462)
 * Fix WKT parsing in Turkish locale (#456)
 * Improve accuracy of `LineSegment.lineIntersection` (#468)
-* Fix `Distance3DOp` coordinate ordering (#480) 
+* Fix `Distance3DOp` coordinate ordering (#480)
 * Fix `Geometry.reverse()` to have consistent behaviour and to copy all fields (#513)
 * Fix `MinimumBoundingCircle.farthestPoints` to work correctly (#522 and #533)
 * Fix `DistanceOp` handling of geometry collections with empty components (#524)
@@ -287,7 +288,7 @@ Distributions for older JTS versions can be obtained at the
 * Allow test files/dirs to be specified as free args
 * Only load `.xml` files from directories
 
-## JtsOp 
+## JtsOp
 
 * Added command-line utility to run JTS operations
 

diff --git a/modules/core/src/main/java/org/locationtech/jts/operation/buffer/BufferBuilder.java b/modules/core/src/main/java/org/locationtech/jts/operation/buffer/BufferBuilder.java
@@ -35,6 +35,7 @@
 import org.locationtech.jts.geomgraph.Label;
 import org.locationtech.jts.geomgraph.Node;
 import org.locationtech.jts.geomgraph.PlanarGraph;
+import org.locationtech.jts.noding.FastNodingValidator;
 import org.locationtech.jts.noding.IntersectionAdder;
 import org.locationtech.jts.noding.MCIndexNoder;
 import org.locationtech.jts.noding.Noder;
@@ -157,7 +158,15 @@ public Geometry buffer(Geometry g, double distance)
 //wktWriter.setMaxCoordinatesPerLine(10);
 //System.out.println(wktWriter.writeFormatted(convertSegStrings(bufferSegStrList.iterator())));
 
-    computeNodedEdges(bufferSegStrList, precisionModel);
+    /**
+     * Currently only zero-distance buffers are validated, 
+     * to avoid reducing performance for other buffers.
+     * This fixes some noding failure cases found via GeometryFixer
+     * (see JTS-852).
+     */
+    boolean isNodingValidated = distance == 0.0;
+    computeNodedEdges(bufferSegStrList, precisionModel, isNodingValidated);
+
     graph = new PlanarGraph(new OverlayNodeFactory());
     graph.addEdges(edgeList.getEdges());
 
@@ -192,11 +201,17 @@ private Noder getNoder(PrecisionModel precisionModel)
 //                                  precisionModel.getScale());
   }
 
-  private void computeNodedEdges(List bufferSegStrList, PrecisionModel precisionModel)
+  private void computeNodedEdges(List bufferSegStrList, PrecisionModel precisionModel, boolean isNodingValidated)
   {
     Noder noder = getNoder(precisionModel);
     noder.computeNodes(bufferSegStrList);
     Collection nodedSegStrings = noder.getNodedSubstrings();
+
+    if (isNodingValidated) {
+      FastNodingValidator nv = new FastNodingValidator(nodedSegStrings);
+      nv.checkValid();
+    }
+
 // DEBUGGING ONLY
 //BufferDebug.saveEdges(nodedEdges, "run" + BufferDebug.runCount + "_nodedEdges");
 

diff --git a/modules/core/src/main/java/org/locationtech/jts/operation/union/CascadedPolygonUnion.java b/modules/core/src/main/java/org/locationtech/jts/operation/union/CascadedPolygonUnion.java
@@ -25,6 +25,8 @@
 import org.locationtech.jts.geom.util.PolygonExtracter;
 import org.locationtech.jts.index.strtree.STRtree;
 import org.locationtech.jts.operation.overlay.snap.SnapIfNeededOverlayOp;
+import org.locationtech.jts.operation.overlayng.OverlayNG;
+import org.locationtech.jts.operation.overlayng.OverlayNGRobust;
 import org.locationtech.jts.util.Debug;
 
 
@@ -41,17 +43,6 @@
  * This algorithm is faster and more robust than
  * the simple iterated approach of
  * repeatedly unioning each polygon to a result geometry.
- * <p>
- * The <tt>buffer(0)</tt> trick is sometimes faster, but can be less robust and
- * can sometimes take a long time to complete.
- * This is particularly the case where there is a high degree of overlap
- * between the polygons.  In this case, <tt>buffer(0)</tt> is forced to compute
- * with <i>all</i> line segments from the outset,
- * whereas cascading can eliminate many segments
- * at each stage of processing.
- * The best situation for using <tt>buffer(0)</tt> is the trivial case
- * where there is <i>no</i> overlap between the input geometries.
- * However, this case is likely rare in practice.
  *
  * @author Martin Davis
  *
@@ -60,41 +51,22 @@ public class CascadedPolygonUnion
 {
   /**
    * A union strategy that uses the classic JTS {@link SnapIfNeededOverlayOp},
-   * and for polygonal geometries a robustness fallback using <cod>buffer(0)</code>.
+   * with a robustness fallback to OverlayNG.
    */
   final static  UnionStrategy CLASSIC_UNION = new UnionStrategy() {
     public Geometry union(Geometry g0, Geometry g1) {
       try {
         return SnapIfNeededOverlayOp.union(g0, g1);
       }
       catch (TopologyException ex) {
-        // union-by-buffer only works for polygons
-        if (g0.getDimension() != 2 || g1.getDimension() != 2)
-          throw ex;
-        return unionPolygonsByBuffer(g0, g1);
+        return OverlayNGRobust.overlay(g0, g1, OverlayNG.UNION);
       }
     }
 
     @Override
     public boolean isFloatingPrecision() {
       return true;
     }
-
-    /**
-     * An alternative way of unioning polygonal geometries 
-     * by using <code>bufer(0)</code>.
-     * Only worth using if regular overlay union fails.
-     * 
-     * @param g0 a polygonal geometry
-     * @param g1 a polygonal geometry
-     * @return the union of the geometries
-     */
-    private Geometry unionPolygonsByBuffer(Geometry g0, Geometry g1) {
-      //System.out.println("Unioning by buffer");
-      GeometryCollection coll = g0.getFactory().createGeometryCollection(
-          new Geometry[] { g0, g1 });
-      return coll.buffer(0);
    }
   };
 
 

diff --git a/modules/core/src/test/java/org/locationtech/jts/geom/util/GeometryFixerTest.java b/modules/core/src/test/java/org/locationtech/jts/geom/util/GeometryFixerTest.java
@@ -333,8 +333,25 @@ public void testMultiLineStringZKeepCollapse() {
         "GEOMETRYCOLLECTION Z (POINT (10 10 1), LINESTRING (10 10 1, 90 90 9))");
   }
 
+  //----------------------------------------
+
+  // see https://github.com/locationtech/jts/issues/852
+  public void testIssue852Case1() {
+    checkFix("POLYGON ((42.565844354657436 -72.61247966084643, 42.56484510561062 -72.61202938126273, 42.56384585656381 -72.61247966084643, 42.563637679679054 -72.61276108558623, 42.562055535354936 -72.61366164475362, 42.5631796905326 -72.61259223074235, 42.565844354657436 -72.61214195115866, 42.566510520688645 -72.61259223074235, 42.565844354657436 -72.61247966084643))");
+  }
+
+  public void testIssue852Case2() {
+    checkFix("POLYGON ((50.69544005538049 4.587126197745181, 50.699035986722194 4.592752502415541, 50.699395579856365 4.592049214331746, 50.699125885005735 4.590501980547397, 50.69867639358802 4.591064611014433, 50.69795720731968 4.591064611014433, 50.69759761418551 4.590501980547397, 50.69759761418551 4.589376719613325, 50.69831680045385 4.588251458679252, 50.69723802105134 4.586563567278144, 50.69579964851466 4.586563567278144, 50.69544005538049 4.587126197745181))");
+  }
+
+
   //================================================
 
+  private void checkFix(String wkt) {
+    Geometry geom = read(wkt);
+    Geometry fix = GeometryFixer.fix(geom);
+    assertTrue("Result is invalid", fix.isValid());
+  }
 
   private void checkFix(String wkt, String wktExpected) {
     Geometry geom = read(wkt);