91 changes: 62 additions & 29 deletions modules/core/src/main/java/org/locationtech/jts/operation/overlayng/OverlayNG.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -97,14 +97,27 @@ public class OverlayNG
*/
public static final int SYMDIFFERENCE = OverlayOp.SYMDIFFERENCE;

/**
* Indicates whether the old overlay result semantics are used:
* - Intersection result can be mixed-dimension
* - Results can include lines caused by Area topology collapse
*/
private static final boolean USE_OLD_RESULT_SEMANTICS = true;

/**
* Indicates whether intersections are allowed to produce
* heterogeneous results.
* True provides the classic JTS semantics
* (for proper boundary touches only -
* touching along collapses are not output).
* heterogeneous results including proper boundary touches.
* This does not control inclusion of touches along collapses.
* True provides the original JTS semantics.
*/
static final boolean ALLOW_INT_MIXED_RESULT = USE_OLD_RESULT_SEMANTICS;

/**
* Allow lines created by area topology collapses
* to appear in the result.
* True provides the original JTS semantics.
*/
static final boolean ALLOW_INT_MIXED_RESULT = true;
static final boolean ALLOW_COLLAPSE_LINES = USE_OLD_RESULT_SEMANTICS;

/**
* Tests whether a point with a given topological {@link Label}
Expand Down Expand Up @@ -326,6 +339,7 @@ static Geometry union(Geometry geom, PrecisionModel pm, Noder noder)
private PrecisionModel pm;
private Noder noder;
private boolean isOptimized = true;
private boolean isAreaResultOnly = false;
private boolean isOutputEdges = false;
private boolean isOutputResultEdges = false;
private boolean isOutputNodedEdges = false;
Expand All @@ -338,7 +352,7 @@ static Geometry union(Geometry geom, PrecisionModel pm, Noder noder)
* The noding strategy is determined by the precision model.
*
* @param geom0 the A operand geometry
* @param geom1 the B operand geometry
* @param geom1 the B operand geometry (may be null)
* @param pm the precision model to use
* @param opCode the overlay opcode
*/
Expand All @@ -364,18 +378,21 @@ public OverlayNG(Geometry geom0, Geometry geom1, PrecisionModel pm, int opCode)
* </ul>
*
* @param geom0 the A operand geometry
* @param geom1 the B operand geometry
* @param geom1 the B operand geometry (may be null)
* @param opCode the overlay opcode
*/
public OverlayNG(Geometry geom0, Geometry geom1, int opCode) {
this(geom0, geom1, geom0.getFactory().getPrecisionModel(), opCode);
}

private OverlayNG(Geometry geom0, PrecisionModel pm) {
this.pm = pm;
this.opCode = UNION;
geomFact = geom0.getFactory();
inputGeom = new InputGeometry( geom0, null );
/**
* Creates a union of a single geometry with a given precision model.
*
* @param geom the geometry
* @param pm the precision model to use
*/
OverlayNG(Geometry geom, PrecisionModel pm) {
this(geom, null, pm, UNION);
}

/**
Expand All @@ -390,6 +407,15 @@ public void setOptimized(boolean isOptimized) {
this.isOptimized = isOptimized;
}

/**
* Sets whether the result can contain only {@link Polygon} components.
* This is used if it is known that the result must be an (possibly empty) area.
*
* @param isAreaResultOnly true if the result should contain only area components
*/
public void setAreaResultOnly(boolean isAreaResultOnly) {
this.isAreaResultOnly = isAreaResultOnly;
}
public void setOutputEdges(boolean isOutputEdges ) {
this.isOutputEdges = isOutputEdges;
}
Expand All @@ -407,6 +433,11 @@ private void setNoder(Noder noder) {
this.noder = noder;
}

/**
* Gets the result of the overlay operation.
*
* @return the result of the overlay operation.
*/
public Geometry getResult() {
if (OverlayUtil.isEmptyResult(opCode,
inputGeom.getGeometry(0),
Expand Down Expand Up @@ -518,25 +549,27 @@ private Geometry extractResult(int opCode, OverlayGraph graph) {
List<Polygon> resultPolyList = polyBuilder.getPolygons();
boolean hasResultAreaComponents = resultPolyList.size() > 0;

//--- Build lines
List<LineString> resultLineList = null;
boolean allowResultLines = ! hasResultAreaComponents || ALLOW_INT_MIXED_RESULT;
if ( allowResultLines ) {
LineBuilder lineBuilder = new LineBuilder(inputGeom, graph, hasResultAreaComponents, opCode, geomFact);
resultLineList = lineBuilder.getLines();
}
boolean hasResultComponents = hasResultAreaComponents || resultLineList.size() > 0;
/**
* Operations with point inputs are handled elsewhere.
* Only an intersection op can produce point results
* from non-point inputs.
*/
List<Point> resultPointList = null;
boolean allowResultPoints = ! hasResultComponents || ALLOW_INT_MIXED_RESULT;
if ( opCode == INTERSECTION && allowResultPoints ) {
//if (opCode == INTERSECTION) {
IntersectionPointBuilder pointBuilder = new IntersectionPointBuilder(graph, geomFact);
resultPointList = pointBuilder.getPoints();

if (! isAreaResultOnly) {
//--- Build lines
boolean allowResultLines = ! hasResultAreaComponents || ALLOW_INT_MIXED_RESULT;
if ( allowResultLines ) {
LineBuilder lineBuilder = new LineBuilder(inputGeom, graph, hasResultAreaComponents, opCode, geomFact);
resultLineList = lineBuilder.getLines();
}
/**
* Operations with point inputs are handled elsewhere.
* Only an Intersection op can produce point results
* from non-point inputs.
*/
boolean hasResultComponents = hasResultAreaComponents || resultLineList.size() > 0;
boolean allowResultPoints = ! hasResultComponents || ALLOW_INT_MIXED_RESULT;
if ( opCode == INTERSECTION && allowResultPoints ) {
IntersectionPointBuilder pointBuilder = new IntersectionPointBuilder(graph, geomFact);
resultPointList = pointBuilder.getPoints();
}
}

if (isEmpty(resultPolyList)
Expand Down
4 changes: 3 additions & 1 deletion modules/core/src/main/java/org/locationtech/jts/operation/overlayng/PrecisionReducer.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -41,7 +41,9 @@ public class PrecisionReducer {
* @return the precision-reduced geometry
*/
public static Geometry reducePrecision(Geometry geom, PrecisionModel pm) {
Geometry reduced = OverlayNG.union(geom, pm);
OverlayNG ov = new OverlayNG(geom, pm);
ov.setAreaResultOnly(true);
Geometry reduced = ov.getResult();
return reduced;
}

Expand Down
16 changes: 11 additions & 5 deletions modules/core/src/main/java/org/locationtech/jts/operation/overlayng/package.html
View file
Original file line number Diff line number Diff line change
Expand Up @@ -60,11 +60,17 @@ <h2>Semantics</h2>
<li>Linear results include all nodes (endpoints) present in the input.
In some cases more nodes will be present.
(If merged lines are required see {@link LineMerger}.)</li>
<li>Polygon edges which collapse completely due to rounding are not output.</li>
<li>The <code>intersection</code> operation may produce a heterogenous result.
The result contains all the dimensional components of the intersection.</li>
<li>The <code>difference</code> operation produces a homogeneous result.
The result dimension is that of the left-hand operand.</li>
<li>Polygon edges which undergo topology collapse to lines
(due to rounding or snapping) are included in the result.
This means that all operations may produce a heterogeneous result.
Generally this only occurs when using a fixed-precision model.
</li>
<li>The <code>intersection</code> operation result includes.
all the components of the intersection
for geometries which intersect in components of the same and/or lower dimension.</li>
<li>The <code>difference</code> operation produces a homogeneous result
if no topology collapses are present.
In this case the result dimension is equal to that of the left-hand operand.</li>
<li>The <code>union</code> and <code>symmetric difference</code> operations
may produce a heterogeneous result if the inputs are of mixed dimension.</li>
<li>Homogeneous results are output as <code>Multi</code> geometries.</li>
Expand Down
36 changes: 35 additions & 1 deletion modules/core/src/test/java/org/locationtech/jts/operation/overlayng/OverlayNGTestOne.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -28,6 +28,40 @@ public static void main(String args[]) {

public OverlayNGTestOne(String name) { super(name); }

//====== Tests for semantic of including collapsed edges as lines in result

public void xxtestCollapseTriBoxIntersection() {
Geometry a = read("POLYGON ((1 2, 1 1, 9 1, 1 2))");
Geometry b = read("POLYGON ((9 2, 9 1, 8 1, 8 2, 9 2))");
Geometry expected = read("LINESTRING (8 1, 9 1)");
Geometry actual = intersection(a, b, 1);
checkEqual(expected, actual);
}

public void testCollapseTriBoxesIntersection() {
Geometry a = read("MULTIPOLYGON (((1 4, 1 1, 2 1, 2 4, 1 4)), ((9 4, 9 1, 10 1, 10 4, 9 4)))");
Geometry b = read("POLYGON ((0 2, 11 3, 11 2, 0 2))");
Geometry expected = read("GEOMETRYCOLLECTION (LINESTRING (1 2, 2 2), POLYGON ((9 2, 9 3, 10 3, 10 2, 9 2)))");
Geometry actual = intersection(a, b, 1);
checkEqual(expected, actual);
}

public void xtestCollapseBoxCutByTriangleUnion() {
Geometry a = read("POLYGON ((100 10, 0 10, 100 11, 100 10))");
Geometry b = read("POLYGON ((20 20, 0 20, 0 0, 20 0, 20 20))");
Geometry expected = read("MULTIPOLYGON (((0 0, 0 10, 0 20, 20 20, 20 10, 20 0, 0 0)), ((20 10, 100 11, 100 10, 20 10)))");
checkEqual(expected, OverlayNGTest.union(a, b, 1));
}

public void xtestCollapseBoxTriangleUnion() {
Geometry a = read("POLYGON ((10 10, 100 10, 10 11, 10 10))");
Geometry b = read("POLYGON ((90 0, 200 0, 200 200, 90 200, 90 0))");
Geometry expected = read("MULTIPOLYGON (((90 10, 10 10, 10 11, 90 10)), ((90 10, 90 200, 200 200, 200 0, 90 0, 90 10)))");
checkEqual(expected, OverlayNGTest.union(a, b, 1));
}

//==============================================

public void xtestParallelSpikes() {
Geometry a = read("POLYGON ((1 3.3, 1.3 1.4, 3.1 1.4, 3.1 0.9, 1.3 0.9, 1 -0.2, 0.8 1.3, 1 3.3))");
Geometry b = read("POLYGON ((1 2.9, 2.9 2.9, 2.9 1.3, 1.7 1, 1.3 0.9, 1 0.4, 1 2.9))");
Expand All @@ -42,7 +76,7 @@ public void xtestBoxHoleCollapseAlongBEdgeDifference() {
checkEqual(expected, OverlayNGTest.difference(b, a, 1));
}

public void testPolyPolyTouchIntersection() {
public void xtestPolyPolyTouchIntersection() {
Geometry a = read("POLYGON ((300 0, 100 0, 100 100, 300 100, 300 0))");
Geometry b = read("POLYGON ((100 200, 300 200, 300 100, 200 100, 200 0, 100 0, 100 200))");
Geometry expected = read("GEOMETRYCOLLECTION (LINESTRING (200 100, 300 100), POLYGON ((200 0, 100 0, 100 100, 200 100, 200 0)))");
Expand Down
10 changes: 10 additions & 0 deletions ...les/core/src/test/java/org/locationtech/jts/operation/overlayng/PrecisionReducerTest.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -27,6 +27,16 @@ public PrecisionReducerTest(String name) {
super(name);
}

public void testPolygonBoxEmpty( ) {
checkReduce("POLYGON ((1 1.4, 7.3 1.4, 7.3 1.2, 1 1.2, 1 1.4))",
1, "POLYGON EMPTY");
}

public void testPolygonThinEmpty( ) {
checkReduce("POLYGON ((1 1.4, 3.05 1.4, 3 4.1, 6 5, 3.2 4, 3.2 1.4, 7.3 1.4, 7.3 1.2, 1 1.2, 1 1.4))",
1, "POLYGON EMPTY");
}

public void testPolygonGore( ) {
checkReduce("POLYGON ((2 1, 9 1, 9 5, 3 5, 9 5.3, 9 9, 2 9, 2 1))",
1, "POLYGON ((9 1, 2 1, 2 9, 9 9, 9 5, 9 1))");
Expand Down
56 changes: 48 additions & 8 deletions modules/tests/src/test/resources/testxml/general/TestNGOverlayAPrec.xml
View file
Original file line number Diff line number Diff line change
Expand Up @@ -16,7 +16,7 @@ POLYGON ((1 2, 1 1, 9 1, 1 2))
POLYGON ((9 2, 9 1, 8 1, 8 2, 9 2))
</b>
<test> <op name="intersectionSR" arg1="A" arg2="B" arg3="1">
POINT (8 1)
LINESTRING (8 1, 9 1)
</op></test>
<test> <op name="unionSR" arg1="A" arg2="B" arg3="1">
MULTIPOLYGON (((8 1, 8 2, 9 2, 9 1, 8 1)), ((1 2, 8 1, 1 1, 1 2)))
Expand All @@ -41,10 +41,11 @@ POLYGON ((0.9 1.7, 1.3 1.4, 2.1 1.4, 2.1 0.9, 1.3 0.9, 0.9 0, 0.9 1.7))
POLYGON ((1 3, 3 3, 3 1, 1.3 0.9, 1 0.4, 1 3))
</b>
<test> <op name="intersectionSR" arg1="A" arg2="B" arg3="1">
POLYGON EMPTY
MULTILINESTRING ((1 2, 1 1), (1 1, 2 1), (1 1, 1 0))
</op></test>
<test> <op name="unionSR" arg1="A" arg2="B" arg3="1">
POLYGON ((1 2, 1 3, 3 3, 3 1, 2 1, 1 1, 1 2))
GEOMETRYCOLLECTION (POLYGON ((1 2, 1 3, 3 3, 3 1, 2 1, 1 1, 1 2)),
LINESTRING (1 1, 1 0))
</op></test>
<test> <op name="differenceSR" arg1="A" arg2="B" arg3="1">
POLYGON EMPTY
Expand All @@ -66,10 +67,14 @@ POLYGON ((1 3.3, 1.3 1.4, 3.1 1.4, 3.1 0.9, 1.3 0.9, 1 -0.2, 0.8 1.3, 1 3.3))
POLYGON ((1 2.9, 2.9 2.9, 2.9 1.3, 1.7 1, 1.3 0.9, 1 0.4, 1 2.9))
</b>
<test> <op name="intersectionSR" arg1="A" arg2="B" arg3="1">
POLYGON EMPTY
MULTILINESTRING ((1 1, 2 1),
(1 1, 1 0),
(1 3, 1 1),
(2 1, 3 1))
</op></test>
<test> <op name="unionSR" arg1="A" arg2="B" arg3="1">
POLYGON ((1 1, 1 3, 3 3, 3 1, 2 1, 1 1))
GEOMETRYCOLLECTION (POLYGON ((1 1, 1 3, 3 3, 3 1, 2 1, 1 1)),
LINESTRING (1 1, 1 0))
</op></test>
<test> <op name="differenceSR" arg1="A" arg2="B" arg3="1">
POLYGON EMPTY
Expand Down Expand Up @@ -171,16 +176,26 @@ GEOMETRYCOLLECTION (POLYGON ((0 7, 9 7, 9 5, 8 5, 8 6, 6 6, 7 1, 8 1, 8 2, 9 2,
LINESTRING (8 5, 8 2))
</op></test>
<test> <op name="unionSR" arg1="A" arg2="B" arg3="1">
POLYGON ((0 7, 9 7, 10 7, 10 5, 9 5, 9 2, 10 2, 10 0, 9 0, 0 0, 0 7))
GEOMETRYCOLLECTION (POLYGON ((0 7, 9 7, 10 7, 10 5, 9 5, 9 2, 10 2, 10 0, 9 0, 0 0, 0 7)),
LINESTRING (10 5, 10 2))
</op></test>
<test> <op name="differenceSR" arg1="A" arg2="B" arg3="1">
POLYGON ((8 2, 8 5, 9 5, 9 2, 8 2))
</op></test>
<test> <op name="differenceSR" arg1="B" arg2="A" arg3="1">
MULTIPOLYGON (((2 6, 4 1, 1 1, 1 6, 2 6)), ((10 7, 10 5, 9 5, 9 7, 10 7)), ((7 1, 6 6, 8 6, 8 5, 8 2, 8 1, 7 1)), ((9 2, 10 2, 10 0, 9 0, 9 2)))
GEOMETRYCOLLECTION (POLYGON ((2 6, 4 1, 1 1, 1 6, 2 6)),
POLYGON ((9 2, 10 2, 10 0, 9 0, 9 2)),
POLYGON ((10 7, 10 5, 9 5, 9 7, 10 7)),
POLYGON ((8 6, 8 5, 8 2, 8 1, 7 1, 6 6, 8 6)),
LINESTRING (10 5, 10 2))
</op></test>
<test> <op name="symDifferenceSR" arg1="A" arg2="B" arg3="1">
MULTIPOLYGON (((2 6, 4 1, 1 1, 1 6, 2 6)), ((10 7, 10 5, 9 5, 9 7, 10 7)), ((7 1, 6 6, 8 6, 8 5, 9 5, 9 2, 8 2, 8 1, 7 1)), ((9 2, 10 2, 10 0, 9 0, 9 2))) </op></test>
GEOMETRYCOLLECTION (POLYGON ((2 6, 4 1, 1 1, 1 6, 2 6)),
POLYGON ((9 2, 10 2, 10 0, 9 0, 9 2)),
POLYGON ((10 7, 10 5, 9 5, 9 7, 10 7)),
POLYGON ((8 6, 8 5, 9 5, 9 2, 8 2, 8 1, 7 1, 6 6, 8 6)),
LINESTRING (10 5, 10 2))
</op></test>
</case>

<case>
Expand Down Expand Up @@ -283,4 +298,29 @@ MULTIPOLYGON (((0 1, 0 3, 1 3, 1 1, 0 1)), ((4 4, 4 1, 3 1, 3 3, 1 3, 1 4, 4 4))
</op></test>
</case>

<case>
<desc>AA - partially overlapping spikes collapsing to lines</desc>
<a>
POLYGON ((1 1, 1 4, 3 4, 3 1.3, 7 1, 1 1))
</a>
<b>
POLYGON ((8 4, 9 4, 9 1, 4 1, 8 1.3, 8 4))
</b>
<test> <op name="intersectionSR" arg1="A" arg2="B" arg3="1">
MULTILINESTRING ((6 1, 7 1), (4 1, 6 1))
</op></test>
<test> <op name="unionSR" arg1="A" arg2="B" arg3="1">
GEOMETRYCOLLECTION (POLYGON ((9 4, 9 1, 8 1, 8 4, 9 4)), POLYGON ((1 4, 3 4, 3 1, 1 1, 1 4)), LINESTRING (8 1, 7 1), LINESTRING (6 1, 7 1), LINESTRING (3 1, 4 1), LINESTRING (4 1, 6 1))
</op></test>
<test> <op name="differenceSR" arg1="A" arg2="B" arg3="1">
GEOMETRYCOLLECTION (POLYGON ((1 4, 3 4, 3 1, 1 1, 1 4)), LINESTRING (3 1, 4 1))
</op></test>
<test> <op name="differenceSR" arg1="B" arg2="A" arg3="1">
GEOMETRYCOLLECTION (POLYGON ((9 4, 9 1, 8 1, 8 4, 9 4)), LINESTRING (8 1, 7 1))
</op></test>
<test> <op name="symDifferenceSR" arg1="A" arg2="B" arg3="1">
GEOMETRYCOLLECTION (POLYGON ((9 4, 9 1, 8 1, 8 4, 9 4)), POLYGON ((1 4, 3 4, 3 1, 1 1, 1 4)), LINESTRING (8 1, 7 1), LINESTRING (3 1, 4 1))
</op></test>
</case>

</run>