Endless loop and OOM while adding constraint to a IncrementalTin.

[Little5ive]

Here's the code to reproduce the ptoblem.

import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.io.ParseException;
import org.locationtech.jts.io.WKTReader;
import org.locationtech.jts.io.geojson.OrientationTransformer;
import org.tinfour.common.IConstraint;
import org.tinfour.common.IIncrementalTin;
import org.tinfour.common.PolygonConstraint;
import org.tinfour.common.Vertex;
import org.tinfour.standard.IncrementalTin;

import java.util.ArrayList;
import java.util.List;

public class TestTin {
    public static void main(String[] args) throws ParseException {
        WKTReader reader = new WKTReader();
        Geometry g = reader.read("POLYGON ((919798.50852 31160.84605, 919798.717973 31162.620991," +
                " 919798.711168 31162.73168, 919798.74691 31162.86622, 919798.952353 31164.607211," +
                " 919798.939163 31164.663351, 919798.97907 31164.83367, 919799.24533 31167.089978," +
                " 919799.23214 31167.146118, 919799.27143 31167.31118, 919799.53831 31169.572758," +
                " 919799.52512 31169.628898, 919799.56382 31169.7889, 919799.772693 31171.558971," +
                " 919799.759503 31171.615111, 919799.79774 31171.77127, 919800.06567 31174.041748," +
                " 919800.05248 31174.097888, 919800.09335 31174.26225, 919800.35864 31176.524518," +
                " 919800.34545 31176.580658, 919800.38891 31176.7528, 919800.38357 31176.7358," +
                " 919800.593023 31178.510741, 919800.579833 31178.566881, 919800.62497 31178.74355," +
                " 919800.61795 31178.722, 919800.827403 31180.496961, 919800.814213 31180.553101," +
                " 919800.874973 31180.788109, 919800.402477 31176.795971, 919800.40241 31176.79576," +
                " 919799.79775 31171.77129, 919799.817143 31171.850489, 919799.56387 31169.7891," +
                " 919799.582067 31169.864356, 919798.97913 31164.83392, 919798.994383 31164.899009," +
                " 919798.50852 31160.84605))");
        IIncrementalTin tries = createTin(g);
        System.out.println(tries.getConstraints().size());
    }

    public static IIncrementalTin createTin(Geometry geom){
        Geometry p = OrientationTransformer.transformCCW(geom);

        List<Vertex> vertices = new ArrayList<>();
        for (Coordinate c : p.getCoordinates()){
            vertices.add(new Vertex(c.x, c.y, 0));
        }
        Geometry bound = p.getBoundary();
        List<IConstraint> constraints = new ArrayList<>();
        for (int j = 0; j < bound.getNumGeometries(); j++) {
            Geometry geometry = bound.getGeometryN(j);
            List<Vertex> vertices1 = new ArrayList<>();
            for (Coordinate c : geometry.getCoordinates()){
                vertices1.add(new Vertex(c.x, c.y, 0));
            }
            if (vertices1.size() > 1) {
                PolygonConstraint constraint = new PolygonConstraint(vertices1);
                constraints.add(constraint);
            }
        }
        IIncrementalTin tin = new IncrementalTin();
        tin.add(vertices, null);
        try {
            tin.addConstraints(constraints, false);
        }catch (NullPointerException ignored){
            System.out.println("error while adding constraints");
        }
        return tin;
    }
}

I debugged and found that the code was stuck at org.tinfour.standard.IncrementalTin#processConstraint, in a for-loop:

Any suggestions on how to deal with such case?

[gwlucastrig]

I will look at this over the weekend. Sorry I can't jump on it right away. But your timing is good because I am getting ready to release a new version of the Tinfour library. I will delay the release until I fix the issue you've identified.

In the meantime, one thing you could try is to use the Tinfour LinearConstraint class rather than the PolygonConstraint. I realize that won't accomplish quite what you're trying to do here, but it may yield some insights into the problem.

A quick question... One of the features of JTS is the ability to check a polygon geometry for correctness. Do you know if the operations your code performs such a verification? In particular, Tinfour has no explicit protection from self-intersecting polygons. JTS is a pretty awesome package and their geometry checker ought to be able to find anything that would present a problem for Tinfour. Right now, my working hypothesis is that the input geometry is fine and that there is a bug in the Tinfour code. But if you have the means to do a check, it would help me moving forward.

Also, one other thing. I notice in the code snippet that you provide, there is an "++iSegment" operation. This puzzles me because I never use the pre-increment operator in my code (no important reason, just personal style). I also can't find a instance of it in the current code base. Would it be possible to download the latest Tinfour code and try processing your data with it?

[gwlucastrig]

Also, as I read the Javadoc, the OrientationTransform.transformCCW() call reorders your polygon so that it is oriented counterclockwise, rather than the clockwise order in which it is specified. Is that correct?

[gwlucastrig]

I copied out your data and coded your example without using the JTS. When I run the data in clockwise order (the order specified in the raw coordinate string), it works fine. However, when I run it in counter-clockwise order, I get the same infinite loop that you saw.

package test.constraint;

import java.util.ArrayList;
import java.util.List;
import org.tinfour.common.IConstraint;
import org.tinfour.common.IIncrementalTin;
import org.tinfour.common.PolygonConstraint;
import org.tinfour.common.Vertex;
import org.tinfour.standard.IncrementalTin;

public class EndlessLoop {

  public static void main(String[] args) throws Exception {

        String input = "919798.50852 31160.84605, 919798.717973 31162.620991," +
                " 919798.711168 31162.73168, 919798.74691 31162.86622, 919798.952353 31164.607211," +
                " 919798.939163 31164.663351, 919798.97907 31164.83367, 919799.24533 31167.089978," +
                " 919799.23214 31167.146118, 919799.27143 31167.31118, 919799.53831 31169.572758," +
                " 919799.52512 31169.628898, 919799.56382 31169.7889, 919799.772693 31171.558971," +
                " 919799.759503 31171.615111, 919799.79774 31171.77127, 919800.06567 31174.041748," +
                " 919800.05248 31174.097888, 919800.09335 31174.26225, 919800.35864 31176.524518," +
                " 919800.34545 31176.580658, 919800.38891 31176.7528, 919800.38357 31176.7358," +
                " 919800.593023 31178.510741, 919800.579833 31178.566881, 919800.62497 31178.74355," +
                " 919800.61795 31178.722, 919800.827403 31180.496961, 919800.814213 31180.553101," +
                " 919800.874973 31180.788109, 919800.402477 31176.795971, 919800.40241 31176.79576," +
                " 919799.79775 31171.77129, 919799.817143 31171.850489, 919799.56387 31169.7891," +
                " 919799.582067 31169.864356, 919798.97913 31164.83392, 919798.994383 31164.899009," +
                " 919798.50852 31160.84605";

    String[] a = input.split(",");
    System.out.println("a.length=" + a.length);
    List<Vertex> vertices = new ArrayList();
    for (int i = a.length-1; i >0; i--) {
      String[] q = a[i].trim().split(" ");
      double x = Double.parseDouble(q[0]);
      double y = Double.parseDouble(q[1]);
      Vertex v = new Vertex(x, y, 0, i);
      vertices.add(v);
      System.out.format("%2d   %12.5f  %12.5f%n", i, x, y);
    }

    List<IConstraint> constraints = new ArrayList<>();
    PolygonConstraint constraint = new PolygonConstraint(vertices);
    constraint.complete();
       double area = constraint.getArea();
       System.out.println("Area = "+area + " "+(area<0 ? "clockwise": "counterclockwise"));
    constraints.add(constraint);


    IIncrementalTin tin = new IncrementalTin();
    tin.add(vertices, null);
    try {
      tin.addConstraints(constraints, false);
    } catch (NullPointerException ignored) {
      System.out.println("error while adding constraints");
    }
  }

}

[Little5ive]

Hi Mr. Lucas,

Thanks for replying. I think that you have reproduced the problem. The code above is a part extracted from my project, which is meant to perform triangulation over bounded polygons. The 'OrientationTransform.transformCCW() ' operation helps to filter those thiangles outside the boundary, since the Delaunay triangulation result is always convex. And I filter the result by following:

List<IConstraint> iConstraints = tin.getConstraints();
List<Vertex[]> triangles = new ArrayList<>();
for (IConstraint iConstraint : iConstraints) {
    PolygonConstraint polygonConstraint = (PolygonConstraint) iConstraint;
    double area = polygonConstraint.getArea();
    if (area <= 0) {
        continue;
    }
    TriangleCollector.visitTrianglesForConstrainedRegion(iConstraint, vertices -> {
        triangles.add(vertices);
    });
}

The project works fine for most cases. I got this bad case when I was tracking errors of my project.

I'm still confused about it. Could you explain why the orientation affect the triangulation result? Is there any ways to identify and dodge this exception? Many thanks!

[gwlucastrig]

I am still investigating this problem, so some of what I say here is speculation. I suspect that there is a bug in the code that is only triggered under unusual conditions. When I constructed the constraint in the order of the coordinates from your original example (clockwise), they did not trigger the bug. But when I reoriented them to the opposite order (counterclockwise), they did trigger the bug.

From your discussion, I'm pretty sure that counterclockwise is the desired ordering. Counterclockwise encloses an area with a polygon. Clockwise encodes a "hole" in a polygon. So what I need to do is to find the bug and fix it.

Do you have a picture of your polygon? That might help expedite my work.

Since this is a free, open-source project, I only have time to work on it when I am not at my job or doing family obligations. So I won't be able to work on the code until the weekend.

Finally, I feel that I am fortunate to have an example of a polygon that triggers the bug. It is the only way I can find (and fix) problems. So I am grateful to you for providing such an excellent example.

谢谢

Gary

[gwlucastrig]

I investigated further. Although the constraint polygon in your test is valid (not self-intersecting), it is challenging. Its shape is nearly flat. I've attached a picture of the vertices.

I am still working on the problem, but there is one change that you could make to your code that would give you a temporary solution. When you construct your TIN, try this variation:

IIncrementalTin tin = new IncrementalTin(0.1);

The Tinfour IncrementalTIN class uses a "nominal point spacing" value (in this case 0.1) to establish numerical thresholds for how to handle the limits of numerical precision in floating-point arithmetic. For example, we compute a distance threshold to tell the code when to treat two closely spaced vertices as a single vertex. When you construct IncrementalTIN with no arguments, it assumes a nominal point spacing of 1.0. But for your constraints, 1.0 is too large. The alternate 0.1 does work. 0.01 would work too.

I still consider this an open problem, but I hope this temporary solution will allow you to move forward with your work until I have a way for IncrementalTin to handle the problematic geometry.

The image below show views of the geometry for constraint polygon and the vertices from which it is formed.