search

locationtech / jts

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

Conforming Delaunay Triangulation does not respect constraint #407

Open kurtzmarc opened 5 years ago

kurtzmarc commented 5 years ago

I am seeing a Delaunay conforming triangulation produce unexpected results where it produces two triangles that are outside the constraints.

I start with Input A: POLYGON ((153213000 204697900, 153240900 204697900, 153240900 204671200, 153213000 204671200, 153213000 204697900), (153223840 204689616, 153228864 204689616, 153231376 204689616, 153231376 204687104, 153226352 204687104, 153226352 204682080, 153228864 204682080, 153228864 204684592, 153231376 204684592, 153231376 204679568, 153223840 204679568, 153223840 204689616)) InputA

and Input B: POLYGON ((153223840 204689616, 153228864 204689616, 153231376 204689616, 153231376 204687104, 153226352 204687104, 153226352 204682080, 153228864 204682080, 153228864 204684592, 153231376 204684592, 153231376 204679568, 153223840 204679568, 153223840 204689616)) InputB

Then I perform a ConformingDelaunayTriangles function:

GEOMETRYCOLLECTION (POLYGON ((153213000 204697900, 153213000 204671200, 153223840 204683587.2, 153213000 204697900)),   POLYGON ((153213000 204697900, 153223840 204683587.2, 153223840 204686601.6, 153213000 204697900)),   POLYGON ((153213000 204697900, 153223840 204686601.6, 153223840 204689616, 153213000 204697900)),   POLYGON ((153213000 204697900, 153223840 204689616, 153228864 204689616, 153213000 204697900)),   POLYGON ((153213000 204697900, 153228864 204689616, 153240900 204697900, 153213000 204697900)),   POLYGON ((153240900 204697900, 153228864 204689616, 153231376 204689616, 153240900 204697900)),   POLYGON ((153240900 204697900, 153231376 204689616, 153231376 204687104, 153240900 204697900)),   POLYGON ((153240900 204697900, 153231376 204687104, 153231376 204684592, 153240900 204697900)), 
  POLYGON ((153240900 204697900, 153231376 204684592, 153240900 204671200, 153240900 204697900)),   POLYGON ((153213000 204671200, 153240900 204671200, 153227608 204679568, 153213000 204671200)),   POLYGON ((153213000 204671200, 153227608 204679568, 153223840 204679568, 153213000 204671200)),   POLYGON ((153213000 204671200, 153223840 204679568, 153223840 204683587.2, 153213000 204671200)),   POLYGON ((153223840 204683587.2, 153223840 204679568, 153226352 204682080, 153223840 204683587.2)),   POLYGON ((153223840 204683587.2, 153226352 204682080, 153226352 204687104, 153223840 204683587.2)),   POLYGON ((153223840 204683587.2, 153226352 204687104, 153223840 204686601.6, 153223840 204683587.2)),   POLYGON ((153223840 204686601.6, 153226352 204687104, 153223840 204689616, 153223840 204686601.6)),
  POLYGON ((153223840 204689616, 153226352 204687104, 153228864 204689616, 153223840 204689616)),   POLYGON ((153228864 204689616, 153226352 204687104, 153228864 204684592, 153228864 204689616)),   POLYGON ((153228864 204689616, 153228864 204684592, 153231376 204687104, 153228864 204689616)),   POLYGON ((153228864 204689616, 153231376 204687104, 153231376 204689616, 153228864 204689616)),   POLYGON ((153231376 204687104, 153228864 204684592, 153231376 204684592, 153231376 204687104)),   POLYGON ((153231376 204684592, 153228864 204684592, 153228864 204682080, 153231376 204684592)),   POLYGON ((153231376 204684592, 153228864 204682080, 153231376 204679568, 153231376 204684592)),   POLYGON ((153231376 204684592, 153231376 204679568, 153240900 204671200, 153231376 204684592)),
  POLYGON ((153240900 204671200, 153231376 204679568, 153227608 204679568, 153240900 204671200)),   POLYGON ((153227608 204679568, 153231376 204679568, 153228864 204682080, 153227608 204679568)),   POLYGON ((153227608 204679568, 153228864 204682080, 153226352 204682080, 153227608 204679568)),   POLYGON ((153227608 204679568, 153226352 204682080, 153223840 204679568, 153227608 204679568)),   POLYGON ((153226352 204682080, 153228864 204682080, 153228864 204684592, 153226352 204682080)),   POLYGON ((153226352 204682080, 153228864 204684592, 153226352 204687104, 153226352 204682080)))

result

There are two triangles in the upper right corner that don't appear to conform to the constraints and "cross" from the outside to the inside of the polygon. Highlighted in red here is what I expect the result to be: expected_result

Is this a bug or am I applying the function incorrectly? Ultimately I want to triangulate a polygon with holes.

kurtzmarc commented 5 years ago

Does it have something to do with the fact that point 1 and 7 are collinear? If I remove point 1 it produces expected results.

dr-jts commented 5 years ago

I think it may have to do with the fact that hole vertices 1,3,4 and 7 form a regular diamond shape (a tilted square). The Delaunay triangulation of squares is non-deterministic, since either diagonal satisfies the Delaunay criterion. (Note that if vertex 1 is moved 1 unit either way the CDT is computed correctly.)

Not sure what the fix would be, if any.

kurtzmarc commented 5 years ago

Confirmed this also happens when using regular (not conforming) Delaunay triangulation. This geometry also exhibits this behavior:

POLYGON ((156155856 201334288, 156153280 201334288, 156153280 201331712, 156150704 201331712, 156150704 201329136, 156155856 201329136, 156155856 201326560, 156153280 201326560, 156153280 201323968, 156153280 201323968, 156153280 201321392, 156171328 201321392, 156171328 201323968, 156168752 201323968, 156168752 201326560, 156166160 201326560, 156166160 201329136, 156163584 201329136, 156163584 201331712, 156161008 201331712, 156161008 201334288, 156158432 201334288, 156158432 201336864, 156155856 201336864, 156155856 201334288))

Which produces this to the left side: image

dr-jts commented 5 years ago

Confirmed this also happens when using regular (not conforming) Delaunay triangulation.

Yes, it's the core DT algorithm which is non-deterministic.

Are you saying this is a problem? Isn't the output properly Delaunay, in spite of being non-deterministic?

kurtzmarc commented 5 years ago

From my perspective, I am trying to do polygon triangulation akin to ear-clipping triangulation. My expectation is that the result will be triangles that respect the edges of the polygon. It may be proper Delaunay, but it doesn't seem like triangulation in the traditional (or correct) sense. Perhaps Delaunay triangulation is a bad choice for what I am trying to do, but it seems like it's sold as a proper solution (everywhere, not just in JTS). Is this a universal limitation to Delaunay triangulation that is just not talked about? I assume triangulation of squares or diamonds would be a common application, so I am surprised to not have heard of this limitation before.

dr-jts commented 5 years ago

The classic Delaunay Triangulation algorithm works only on points (vertices). So yes, DT cannot be used directly for polygon triangulation. That's why there's extensions for Conforming and Constrained DT - and why Ear-Clipping is still popular for polygon triangulation. (One problem with ear-clipping is that it produces lousy triangles - see my blog post for an idea about how to improve that).

Given that DT isn't expected to respect edges, the non-determinism can't really be considered as a issue. But I agree that this is an limitation which isn't often made explicit in discussions of Delaunay Triangulation. (Perhaps one reason is that a Constrained DT isn't actually Delauany in general...)

It's a bug that the JTS CDT doesn't detect diamond diagonals which cross edges. That could probably be fixed somehow.