GeometryException: internal error from within GeometryEngine.Difference(...)

[DavidHollman]

I've been using the project https://github.com/EchoParkLabs/geometry-api-cs which seems to be derived from here. I ran into the error GeometryException: internal error in a specific case.

The error occurs from running the following:

com.epl.geometry.GeometryEngine.Difference(p1, p2, null)

where p1 and p2are specified below. The exception is thrown here within TopologicalOperations.RestorePolylineParts_():

int fromEdgeTwinNext = m_topo_graph.GetHalfEdgeNext(fromEdgeTwin);
if (m_topo_graph.GetHalfEdgeTwin(toEdge) != fromEdgeTwinNext)
{
	// Crossroads is here. Pass through the crossroad.
	toEdge = TryMoveThroughCrossroadBackwards_(fromEdge);
	if (toEdge == -1)
	{
		throw com.epl.geometry.GeometryException.GeometryInternalError(); // ⁂⁂⁂⁂⁂
	}
}

with the full stack trace below.

Using OperatorDifference.Local()... does the same thing.

I'd be happy to provide any other information that might be helpful. I've tried step-tracing the code but really don't have enough context to understand where it's going wrong.

I'm looking for a workaround, if possible, and also just wanted to report the potential problem in this repository. (Despite this code coming from the other repo as noted above, it could be that the same issue exists here).

Thank you!

---

p1 is:

MULTILINESTRING((113100 -141099, 113100 -153451, 113100 -208900, 78990 -208900, 78990 -153451), (146232 -155878, 147692 -155878), (78990 -153451, 87004 -153451, 87004 -142059), (78990 -153451, 78990 -142059), (78990 -142059, 82837 -142059), (78990 -142059, 78990 -133150), (82837 -142059, 87004 -142059), (82837 -142059, 82837 -133150, 78990 -133150), (87004 -142059, 90190 -142059, 90190 -133799, 90190 -133150), (108983 -133799, 93962 -133799, 93962 -141099, 108983 -141099), (108983 -141099, 113100 -141099), (108983 -141099, 108983 -133799), (123511 -141099, 113100 -141099), (130712 -141099, 123511 -141099), (123511 -133570, 123511 -141099), (134078 -141099, 130712 -141099), (130712 -141099, 130712 -133570, 134078 -133570), (138075 -141099, 134078 -141099), (134078 -141099, 134078 -133570), (152794 -141099, 138075 -141099), (138075 -141099, 138075 -133570, 134078 -133570), (152794 -141099, 160621 -141099, 160621 -133570, 163710 -133570), (152794 -133570, 152794 -141099), (163710 -141099, 163710 -133570), (181990 -141099, 167364 -141099, 167364 -133570, 163710 -133570), (185987 -141099, 181990 -141099), (181990 -141099, 181990 -133570, 185987 -133570, 185987 -141099), (193040 -141099, 185987 -141099), (196724 -141099, 193040 -141099), (193040 -141099, 193040 -133570, 196724 -133570, 196724 -141099), (211356 -141099, 196724 -141099), (218759 -141099, 211356 -141099), (211356 -141099, 211356 -133570, 218759 -133570), (222026 -141099, 218759 -141099), (218759 -141099, 218759 -133570), (225988 -141099, 222026 -141099), (222026 -141099, 222026 -133570), (240910 -141099, 225988 -141099), (225988 -141099, 225988 -133570, 222026 -133570), (108983 -133799, 108983 -130225), (218759 -133570, 222026 -133570), (239732 -111827, 240910 -111827, 240910 -133570), (78990 -133150, 78990 -119153), (82348 -130225, 108983 -130225), (108983 -130225, 108983 -123937), (82348 -126591, 85522 -126591, 104245 -126591), (104245 -123937, 108983 -123937), (108983 -123937, 108983 -119153, 108983 -108235), (78990 -119153, 82348 -119153), (78990 -119153, 78990 -108235), (85522 -119153, 85522 -108235), (78990 -108235, 85522 -108235), (78990 -108235, 78990 -100975, 78990 -89738, 78990 -82547, 86813 -82547), (85522 -108235, 108983 -108235), (108983 -108235, 108983 -100975, 108983 -74778), (78990 -79816, 78990 -72050, 78990 -60514), (86813 -74778, 108983 -74778), (108983 -74778, 108983 -66235), (240910 -46061, 240910 -67831, 238910 -67831), (108983 -62106, 104699 -62106, 104699 -66235, 108983 -66235), (108983 -66235, 108983 -62106), (82636 -60514, 82636 -63125, 94126 -63125, 94126 -64094, 101376 -64094, 101376 -59622), (108983 -62106, 108983 -59622), (78990 -60514, 82636 -60514), (78990 -60514, 73065 -59457, 79357 -24381, 110845 -29924, 109462 -37956), (82636 -60514, 82636 -59622, 86813 -59622, 101376 -59622), (101376 -59622, 108983 -59622), (108983 -59622, 108983 -53603), (91912 -53603, 91912 -56476, 86813 -56476, 86813 -52933), (86813 -52933, 91912 -52933, 91912 -53603), (91912 -53603, 104538 -53603), (104538 -53603, 108983 -53603), (104538 -53603, 104538 -48078, 108983 -48078), (108983 -53603, 108983 -48078), (92336 -45588, 92336 -50430), (95865 -47913, 95865 -50430, 102623 -50430, 102623 -47913), (108983 -48078, 108983 -45588), (95865 -47913, 102623 -47913), (95865 -47913, 95865 -45588), (102623 -47913, 102623 -45588, 101829 -45588), (123143 -46190, 123143 -37956), (130877 -37956, 130877 -46190, 134583 -46190), (134583 -46190, 138283 -46190, 138283 -37956), (134583 -46190, 134583 -37956), (152772 -37956, 152772 -46190, 156813 -46190, 156813 -37956), (167487 -37956, 167487 -46190), (181994 -37956, 181994 -46190, 189488 -46190, 189488 -37956), (192756 -37956, 192756 -46190, 196811 -46190, 196811 -37956), (211197 -37956, 211197 -46190, 215014 -46190), (215014 -46190, 218661 -46190, 218661 -37956), (215014 -46190, 215014 -37956), (221998 -37956, 221998 -46190, 226099 -46190, 226099 -37956), (240910 -46061, 239748 -46061), (226099 -37956, 240910 -37956, 240910 -46061), (87057 -37956, 81777 -37956, 81777 -45588, 87057 -45588), (87057 -45588, 92336 -45588), (87057 -45588, 87057 -37956), (92336 -45588, 95400 -45588), (95400 -45588, 95865 -45588), (95400 -45588, 95400 -37956), (95865 -45588, 98875 -45588), (98875 -45588, 101829 -45588), (98875 -45588, 98875 -37956), (101829 -45588, 101829 -37956, 98875 -37956), (108983 -37956, 104819 -37956, 104819 -45588, 108983 -45588), (108983 -45588, 108983 -37956), (87057 -37956, 95400 -37956), (95400 -37956, 98875 -37956), (108983 -37956, 109462 -37956), (109462 -37956, 123143 -37956), (123143 -37956, 130877 -37956), (130877 -37956, 134583 -37956), (134583 -37956, 138283 -37956), (138283 -37956, 152772 -37956), (152772 -37956, 156813 -37956), (156813 -37956, 167487 -37956), (167487 -37956, 181994 -37956), (181994 -37956, 189488 -37956), (189488 -37956, 192756 -37956), (192756 -37956, 196811 -37956), (196811 -37956, 211197 -37956), (211197 -37956, 215014 -37956), (215014 -37956, 218661 -37956), (218661 -37956, 221998 -37956), (221998 -37956, 226099 -37956))

and p2 is:

MULTILINESTRING((87004 -142059, 90190 -142059, 90190 -133799, 90190 -133150), (108983 -133799, 93962 -133799, 93962 -141099, 108983 -141099), (134078 -133570, 130712 -133570, 130712 -141099), (160621 -141099, 160621 -133570, 163710 -133570), (163710 -141099, 163710 -133570), (193040 -141099, 193040 -133570, 196724 -133570), (218759 -141099, 218759 -133570), (163710 -133570, 167364 -133570), (211356 -133570, 218759 -133570), (218759 -133570, 222026 -133570), (82348 -130225, 108983 -130225), (82348 -126591, 85522 -126591, 104245 -126591), (86813 -74778, 108983 -74778), (91912 -53603, 104538 -53603), (104538 -53603, 108983 -53603), (104538 -53603, 104538 -48078, 108983 -48078), (92336 -45588, 92336 -50430), (95865 -47913, 95865 -50430, 102623 -50430, 102623 -47913), (95865 -47913, 102623 -47913), (95865 -47913, 95865 -45588), (102623 -47913, 102623 -45588, 101829 -45588), (134583 -46190, 130877 -46190, 130877 -37956), (134583 -46190, 138283 -46190), (134583 -46190, 134583 -37956), (189488 -37956, 189488 -46190, 181994 -46190), (211197 -46190, 215014 -46190), (215014 -46190, 218661 -46190, 218661 -37956), (215014 -46190, 215014 -37956), (87057 -37956, 81777 -37956, 81777 -45588, 87057 -45588), (87057 -45588, 92336 -45588), (87057 -45588, 87057 -37956), (92336 -45588, 95400 -45588), (95400 -45588, 95865 -45588), (95400 -45588, 95400 -37956), (95865 -45588, 98875 -45588), (87057 -37956, 95400 -37956), (95400 -37956, 98875 -37956))

Stack trace:

   at com.epl.geometry.TopologicalOperations.RestorePolylineParts_(Int32 first_edge, Int32 newGeometry, Int32 visitedEdges, Int32 visitedClusters, Int32 geometry_dominant)
   at com.epl.geometry.TopologicalOperations.TopoOperationPolylinePolylineOrPolygon_(Int32 geometry_dominant)
   at com.epl.geometry.TopologicalOperations.Difference(Int32 geometry_a, Int32 geometry_b)
   at com.epl.geometry.TopologicalOperations.Difference(Geometry geometry_a, Geometry geometry_b, SpatialReference sr, ProgressTracker progress_tracker)
   at com.epl.geometry.OperatorDifferenceLocal.Difference(Geometry geometry_a, Geometry geometry_b, SpatialReference spatial_reference, ProgressTracker progress_tracker)
   at com.epl.geometry.OperatorDifferenceCursor.Next()
   at com.epl.geometry.OperatorDifferenceLocal.Execute(Geometry inputGeometry, Geometry subtractor, SpatialReference sr, ProgressTracker progressTracker)
   at com.epl.geometry.GeometryEngine.Difference(Geometry geometry1, Geometry substractor, SpatialReference spatialReference)

[DavidHollman]

I created what I think is a Java equivalent of this, but it does not throw any error.

Program pasted below and can be run online here: https://www.jdoodle.com/ia/Xwj

The program output is just MULTILINESTRING EMPTY;

I'm not sure what that means... either I have not reproduced this faithfully, or the issue does not happen in the Java 2.2.4 version of this library I guess.

I tried it as well with the 2.0.0 library version, since that's what the C# code may have derived from (same timeframe). Made no difference.

---

// Uses the Maven reference com.esri.geometry:esri-geometry-api:2.2.4

import com.esri.core.geometry.Geometry;
import com.esri.core.geometry.GeometryEngine;
import com.esri.core.geometry.OperatorExportToWkt;
import com.esri.core.geometry.OperatorImportFromWkt;
import com.esri.core.geometry.Polygon;

public class MyClass {
    public static void main(String args[]) {
               
        var s1 = "MULTILINESTRING ((87004 -142059, 90190 -142059, 90190 -133799, 90190 -133150), (108983 -133799, 93962 -133799, 93962 -141099, 108983 -141099), (134078 -133570, 130712 -133570, 130712 -141099), (160621 -141099, 160621 -133570, 163710 -133570), (163710 -141099, 163710 -133570), (193040 -141099, 193040 -133570, 196724 -133570), (218759 -141099, 218759 -133570), (163710 -133570, 167364 -133570), (211356 -133570, 218759 -133570), (218759 -133570, 222026 -133570), (82348 -130225, 108983 -130225), (82348 -126591, 85522 -126591, 104245 -126591), (86813 -74778, 108983 -74778), (91912 -53603, 104538 -53603), (104538 -53603, 108983 -53603), (104538 -53603, 104538 -48078, 108983 -48078), (92336 -45588, 92336 -50430), (95865 -47913, 95865 -50430, 102623 -50430, 102623 -47913), (95865 -47913, 102623 -47913), (95865 -47913, 95865 -45588), (102623 -47913, 102623 -45588, 101829 -45588), (134583 -46190, 130877 -46190, 130877 -37956), (134583 -46190, 138283 -46190), (134583 -46190, 134583 -37956), (189488 -37956, 189488 -46190, 181994 -46190), (211197 -46190, 215014 -46190), (215014 -46190, 218661 -46190, 218661 -37956), (215014 -46190, 215014 -37956), (87057 -37956, 81777 -37956, 81777 -45588, 87057 -45588), (87057 -45588, 92336 -45588), (87057 -45588, 87057 -37956), (92336 -45588, 95400 -45588), (95400 -45588, 95865 -45588), (95400 -45588, 95400 -37956), (95865 -45588, 98875 -45588), (87057 -37956, 95400 -37956), (95400 -37956, 98875 -37956))";
        var p1 = fromWkt(s1);
        
        var s2 = "MULTILINESTRING((113100 -141099, 113100 -153451, 113100 -208900, 78990 -208900, 78990 -153451), (146232 -155878, 147692 -155878), (78990 -153451, 87004 -153451, 87004 -142059), (78990 -153451, 78990 -142059), (78990 -142059, 82837 -142059), (78990 -142059, 78990 -133150), (82837 -142059, 87004 -142059), (82837 -142059, 82837 -133150, 78990 -133150), (87004 -142059, 90190 -142059, 90190 -133799, 90190 -133150), (108983 -133799, 93962 -133799, 93962 -141099, 108983 -141099), (108983 -141099, 113100 -141099), (108983 -141099, 108983 -133799), (123511 -141099, 113100 -141099), (130712 -141099, 123511 -141099), (123511 -133570, 123511 -141099), (134078 -141099, 130712 -141099), (130712 -141099, 130712 -133570, 134078 -133570), (138075 -141099, 134078 -141099), (134078 -141099, 134078 -133570), (152794 -141099, 138075 -141099), (138075 -141099, 138075 -133570, 134078 -133570), (152794 -141099, 160621 -141099, 160621 -133570, 163710 -133570), (152794 -133570, 152794 -141099), (163710 -141099, 163710 -133570), (181990 -141099, 167364 -141099, 167364 -133570, 163710 -133570), (185987 -141099, 181990 -141099), (181990 -141099, 181990 -133570, 185987 -133570, 185987 -141099), (193040 -141099, 185987 -141099), (196724 -141099, 193040 -141099), (193040 -141099, 193040 -133570, 196724 -133570, 196724 -141099), (211356 -141099, 196724 -141099), (218759 -141099, 211356 -141099), (211356 -141099, 211356 -133570, 218759 -133570), (222026 -141099, 218759 -141099), (218759 -141099, 218759 -133570), (225988 -141099, 222026 -141099), (222026 -141099, 222026 -133570), (240910 -141099, 225988 -141099), (225988 -141099, 225988 -133570, 222026 -133570), (108983 -133799, 108983 -130225), (218759 -133570, 222026 -133570), (239732 -111827, 240910 -111827, 240910 -133570), (78990 -133150, 78990 -119153), (82348 -130225, 108983 -130225), (108983 -130225, 108983 -123937), (82348 -126591, 85522 -126591, 104245 -126591), (104245 -123937, 108983 -123937), (108983 -123937, 108983 -119153, 108983 -108235), (78990 -119153, 82348 -119153), (78990 -119153, 78990 -108235), (85522 -119153, 85522 -108235), (78990 -108235, 85522 -108235), (78990 -108235, 78990 -100975, 78990 -89738, 78990 -82547, 86813 -82547), (85522 -108235, 108983 -108235), (108983 -108235, 108983 -100975, 108983 -74778), (78990 -79816, 78990 -72050, 78990 -60514), (86813 -74778, 108983 -74778), (108983 -74778, 108983 -66235), (240910 -46061, 240910 -67831, 238910 -67831), (108983 -62106, 104699 -62106, 104699 -66235, 108983 -66235), (108983 -66235, 108983 -62106), (82636 -60514, 82636 -63125, 94126 -63125, 94126 -64094, 101376 -64094, 101376 -59622), (108983 -62106, 108983 -59622), (78990 -60514, 82636 -60514), (78990 -60514, 73065 -59457, 79357 -24381, 110845 -29924, 109462 -37956), (82636 -60514, 82636 -59622, 86813 -59622, 101376 -59622), (101376 -59622, 108983 -59622), (108983 -59622, 108983 -53603), (91912 -53603, 91912 -56476, 86813 -56476, 86813 -52933), (86813 -52933, 91912 -52933, 91912 -53603), (91912 -53603, 104538 -53603), (104538 -53603, 108983 -53603), (104538 -53603, 104538 -48078, 108983 -48078), (108983 -53603, 108983 -48078), (92336 -45588, 92336 -50430), (95865 -47913, 95865 -50430, 102623 -50430, 102623 -47913), (108983 -48078, 108983 -45588), (95865 -47913, 102623 -47913), (95865 -47913, 95865 -45588), (102623 -47913, 102623 -45588, 101829 -45588), (123143 -46190, 123143 -37956), (130877 -37956, 130877 -46190, 134583 -46190), (134583 -46190, 138283 -46190, 138283 -37956), (134583 -46190, 134583 -37956), (152772 -37956, 152772 -46190, 156813 -46190, 156813 -37956), (167487 -37956, 167487 -46190), (181994 -37956, 181994 -46190, 189488 -46190, 189488 -37956), (192756 -37956, 192756 -46190, 196811 -46190, 196811 -37956), (211197 -37956, 211197 -46190, 215014 -46190), (215014 -46190, 218661 -46190, 218661 -37956), (215014 -46190, 215014 -37956), (221998 -37956, 221998 -46190, 226099 -46190, 226099 -37956), (240910 -46061, 239748 -46061), (226099 -37956, 240910 -37956, 240910 -46061), (87057 -37956, 81777 -37956, 81777 -45588, 87057 -45588), (87057 -45588, 92336 -45588), (87057 -45588, 87057 -37956), (92336 -45588, 95400 -45588), (95400 -45588, 95865 -45588), (95400 -45588, 95400 -37956), (95865 -45588, 98875 -45588), (98875 -45588, 101829 -45588), (98875 -45588, 98875 -37956), (101829 -45588, 101829 -37956, 98875 -37956), (108983 -37956, 104819 -37956, 104819 -45588, 108983 -45588), (108983 -45588, 108983 -37956), (87057 -37956, 95400 -37956), (95400 -37956, 98875 -37956), (108983 -37956, 109462 -37956), (109462 -37956, 123143 -37956), (123143 -37956, 130877 -37956), (130877 -37956, 134583 -37956), (134583 -37956, 138283 -37956), (138283 -37956, 152772 -37956), (152772 -37956, 156813 -37956), (156813 -37956, 167487 -37956), (167487 -37956, 181994 -37956), (181994 -37956, 189488 -37956), (189488 -37956, 192756 -37956), (192756 -37956, 196811 -37956), (196811 -37956, 211197 -37956), (211197 -37956, 215014 -37956), (215014 -37956, 218661 -37956), (218661 -37956, 221998 -37956), (221998 -37956, 226099 -37956))";
        var p2 = fromWkt(s2);
        
        var d = com.esri.core.geometry.GeometryEngine.difference(p1, p2, null);
        
        System.out.println(toWkt(d));
    }
    
    private static String toWkt(Geometry p)
    {
        var wkt = com.esri.core.geometry.OperatorExportToWkt.local().execute(0, p, null);
        return wkt;
    }
    
    private static Geometry fromWkt(String wkt)
    {
        var g = com.esri.core.geometry.OperatorImportFromWkt.local().execute(0, Geometry.Type.Polyline, wkt, null);
        return g;
    }
}

[stolstov]

@DaveInCaz Thank you for making a Java repro case. It seems that the expected output for this is indeed EMPTY. Visually inspecting this, the second polyline is larger than the first one and completely covers it. So the difference g1 - g2 should be zero.

[stolstov]

First polyline in blue:

Second polyline in red drawn on top of the first one (zoom level is different in this image):

So visually it completely cover blue.

[DavidHollman]

@stolstov agreed, EMPTY is a sensible result.

Curious, what tool did you use to generate those images?

[stolstov]

@DaveInCaz It's just some internal program.

Curious, what tool did you use to generate those images?