Document that ConformingDelaunayTriangulator can fail if input points are closer than tolerance

[johnhultman]

Here's an example with a triangular polygon that have a very short edge in one of it's sides. It consists of 5 coordinate points, there's a test case snippet below. The length of the short edge is less than the tolerance used. In the figures the (input) polygon is shown in red, and we can see that the triangulation extends on the outside of it.

import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.triangulate.ConformingDelaunayTriangulator;
import org.locationtech.jts.triangulate.ConstraintVertex;
import org.locationtech.jts.triangulate.Segment;
import org.locationtech.jts.triangulate.quadedge.QuadEdgeSubdivision;
import org.testng.Assert;
import org.testng.annotations.Test;

import java.util.ArrayList;
import java.util.Collection;

@Test
public void testTriangulationOfPolygonWithShortEdge()
{
    final Coordinate c0 = new Coordinate(46.51, -188.20);
    final Coordinate c1 = new Coordinate(4.66, -141.67);
    final Coordinate c2 = new Coordinate(4.66 + 1E-8, -141.67 + 1E-8);
    final Coordinate c3 = new Coordinate(-6.48, -129.26);
    final Coordinate c4 = new Coordinate(0, -200);

    final ArrayList<Segment> segments = new ArrayList<>();
    segments.add(new Segment(c0, c1));
    segments.add(new Segment(c1, c2));
    segments.add(new Segment(c2, c3));
    segments.add(new Segment(c3, c4));
    segments.add(new Segment(c4, c0));

    final ArrayList vertices = new ArrayList<>();
    for (final Segment segment : segments)
    {
        vertices.add(new ConstraintVertex(segment.getStart()));
    }

    final ConformingDelaunayTriangulator cdt = new ConformingDelaunayTriangulator(new ArrayList<>(), 1E-5);
    cdt.setConstraints(segments, vertices);
    cdt.formInitialDelaunay();
    cdt.enforceConstraints();
    final QuadEdgeSubdivision subdivision = cdt.getSubdivision();

    final Collection subdivisionEdges = subdivision.getEdges();

    Assert.assertEquals(subdivisionEdges.size(), 3);
}

[johnhultman]

My assessment here is that it's not safe to have points separated by distances shorter than the tolerance, is that correct?

[dr-jts]

Yes, I think it's a requirement of the CDT that no two input points are closer than the constraint distance.

[johnhultman]

Perhaps, this isn't to be considered a bug then, but rather perhaps the JavaDoc should say something about input points should not be closer than the tolerance.

[dr-jts]

Yes, good point. Let's leave this issue open, and I'll change the title to refer to the actual task