search

locationtech / jts

The JTS Topology Suite is a Java library for creating and manipulating vector geometry.
Other
1.94k stars 442 forks source link

"Unable to find a convex corner" in ConstrainedDelaunayTriangulator #1001

Closed TreufussMK closed 1 year ago

TreufussMK commented 1 year ago

Hey, I have a problem with the ConstrainedDelaunayTriangulator on a specific Polygon. I was able to simplify the Polygon down to a minimal example that reproduces the issue.

image

A code example that reproduces the Problem looks like this.

WKTReader reader = new WKTReader();

Geometry polygon;

try {
    polygon = reader.read("Polygon ((461527.55000000004656613 5638016.75, 461530.36926462681731209 5638011.81626623962074518, 461527.70430372917326167 5638009.52959428261965513, 461526.03410192765295506 5638015.73833885975182056, 461527.55000000004656613 5638016.75),(461529.30000000004656613 5638011.14999999944120646, 461528.95000000001164153 5638013.29999999981373549, 461527.55000000004656613 5638012.29999999981373549, 461529.30000000004656613 5638011.14999999944120646),(461527.70000000001164153 5638013, 461527.55000000004656613 5638012.75, 461528 5638012.94999999925494194, 461527.70000000001164153 5638013))");
} catch (ParseException e) {
    throw new RuntimeException(e);
}

try {
    ConstrainedDelaunayTriangulator.triangulate(polygon);
} catch (Exception e) {
    e.printStackTrace();
}

Demo Project: https://github.com/TreufussMK/TriangulationFail

It fails with an IllegalStateException "Unable to find a convex corner"

java.lang.IllegalStateException: Unable to find a convex corner
    at org.locationtech.jts.triangulate.polygon.PolygonEarClipper.compute(PolygonEarClipper.java:169)
    at org.locationtech.jts.triangulate.polygon.PolygonEarClipper.triangulate(PolygonEarClipper.java:61)
    at org.locationtech.jts.triangulate.polygon.ConstrainedDelaunayTriangulator.triangulatePolygon(ConstrainedDelaunayTriangulator.java:107)
    at org.locationtech.jts.triangulate.polygon.ConstrainedDelaunayTriangulator.compute(ConstrainedDelaunayTriangulator.java:87)
    at org.locationtech.jts.triangulate.polygon.ConstrainedDelaunayTriangulator.getResult(ConstrainedDelaunayTriangulator.java:67)
    at org.locationtech.jts.triangulate.polygon.ConstrainedDelaunayTriangulator.triangulate(ConstrainedDelaunayTriangulator.java:44)
    at de.example.Main.main(Main.java:22)

The Polygon does not look particularly complex to me, that could explain the issue. So I think it might be a bug in the library. I am using Version 1.19.0

dr-jts commented 1 year ago

This is fixed in the current code by #946.