ConformingDelaunayTriangulationBuilder poor triangulation for single-triangle input, possibly for any already-Delaunay set of constraints.

[palisades-lakes]

Starting from a single triangle, passing the 3 vertices as sites with empty constraints reproduces the same triangle.

No constraint result, same as original triangle:

Adding the triangle's 3 edges as constraints nominally succeeds, but produces 3 unnecessary and incorrect triangles, one of which has zero area.

I have seen similar issues with constraints that happen to correspond to a triangulation of the sites which is already Delaunay.
I could add some multiple triangle examples if that would helpful.

Code:
https://github.com/palisades-lakes/jts-issues/blob/main/src/main/java/jts/CDTBIssues.java

[palisades-lakes]

https://github.com/palisades-lakes/jts-issues/blob/main/src/main/java/jts/RandomCDTB.java

Creates random points, then a Delaunay triangulation of those points, then passes the triangles to
ConformingDelaunayTriangulationBuilder as constraints, with the points as the sites.
About 9/10 times, ConformingDelaunayTriangulationBuilder claims to succeed, but returns an unnecessarily refined version of the input triangles, often with singular, zero-area faces in the new triangulation.
Rarely, it gives the correct answer. About as frequently, it fails to converge.

[dr-jts]

This seems like pretty pathological input, and well outside the design parameters of the Conforming Delaunay algorithm. I suggest that providing constraints which constitute a triangulation of the input sites is simply invalid input.

Including a check for this would create an unwanted performance burden, so this should be done by the client prior to calling ConformingDelaunayTriangulationBuilder.

[palisades-lakes]

I agree that it doesn't make sense to test inputs for the unreasonable case that they are already Delaunay.
But the "already Delaunay" part of this is perhaps a red herring.

Consider the single triangle example.

I was surprised that ConformingDelaunayTriangulationBuilder refined the triangle, but that's probably my ignorance.

However, the fact that it returns a triangulation that isn't Delaunay, because it includes a singular, zero area triangle, does seem like a problem worth investigating.

[palisades-lakes]

If it's any help, Tinfour does what I would have expected with a single triangle:

https://github.com/palisades-lakes/jts-issues/blob/main/src/main/java/tinfour/OneTriangle.java

[palisades-lakes]

Also in 2 triangle case:
https://github.com/palisades-lakes/jts-issues/blob/main/src/main/java/tinfour/TwoTriangles.java

[dr-jts]

The problem may be caused by including constraint lines which lie on the convex hull of the input sites. For the 3 and 4 point cases above, removing these allows computing a correct triangulation. @palisades-lakes Does this work for other cases you've tried?

[palisades-lakes]

Tried variations on a hexagon, maybe evidence against simple convex hull constraint theory:

(1) Empty hexagon, as both sites and constraints, triangulates successfully. That is, all the edges of the convex hull of the sites are included as constraints.
Resulting triangulation:

(2) Adding the 3 edges of the internal triangle in the above as constraints fails, or maybe "poor triangulation" is fairer, since there are no zero area triangles for this case:

(3) Removing the convex hull edges from the triangulation, so the only constraints are the 3 internal edges from the initial triangulation, also produces a poor triangulation (unnecessary refinement, but no singular triangles):

[dr-jts]

Hexagon case 2 illustrates that including convex hull edges as constraints produces a poor quality triangulation.

Hexagon case 3 just demonstrates that a Conforming Delaunay Triangulation is not guaranteed to be an optimal triangulation. a A Conforming Delaunay Triangulation is only guaranteed to be Delaunay and to include edges which approximate the constraints closely.

As mentioned, it should be possible to remove constraint edges in the convex hull either a priori or as part of the CDT algorithm. It might be possible to detect constraint edges which are already part of the triangulation, and prevent them from being split.

[palisades-lakes]

I am able to use Tinfour (https://github.com/gwlucastrig/Tinfour) for my original problem: taking an existing triangulation and adding features. It behaves as I expected: a no-op on already Delaunay triangulations, minimal additional refinements.

If I have a chance to dig into the JTS and can suggest anything specific, I'll let you know.
I've gotten a lot of value from JTS over the years and I'd like to help when possible.

[dr-jts]

I am able to use Tinfour (https://github.com/gwlucastrig/Tinfour) for my original problem: taking an existing triangulation and adding features. It behaves as I expected: a no-op on already Delaunay triangulations, minimal additional refinements.

TinFour computes Constrained Delaunay Triangulations, with an option to convert a non-Delaunay result into a Conforming DT. Have you checked to see if you are computing only a Constrained DT - which if passed the vertex DT as constraints would probably produce the kind of results you're seeing.

As mentioned, the simplest way I can see to avoid the problem you have is to remove all constraint edges which lie in the DT of the input sites. Of course, this costs performance, which is why I'm reluctant to suggest including this in the current algorithm. If your use case for some reason requires handling DT edges as constraints, it would be best to do this as a pre-processing step.