Missing some triangles about tinfour HOT 7 CLOSED

Thank you for finding this issue. I have not tried constructing triangles very much. The countTriangles method is only a diagnostic. So I have not given it a lot of attention. This issue is something new to me. I will look into it later today.

Would it be possible to provide the code you are using to build triangles?

from tinfour.

Following code reproduce the missing triangles. It is another location that in screenshot above.
vertexList, constraintI, constraintO are attached in ZIP as CSV files.
Data are city walls around Vyšehrad

`
IIncrementalTin tin = new IncrementalTin(0.005483625000000001);
tin.add(vertexList, null);
tin.addConstraints(Arrays.asList(constraintI, constraintO), false);

private static List<Triangle> getTriangles(final IIncrementalTin tin) {
    Objects.requireNonNull(tin, "tin");

    if (!tin.isBootstrapped()) return Collections.emptyList();

    List<IQuadEdge> edgePool = tin.getEdges();
    int maxIndex = edgePool.stream().mapToInt(IQuadEdge::getIndex).max().getAsInt();
    int maxMapIndex = maxIndex * N_SIDES + 1;
    int mapSize = (maxMapIndex + INT_BITS - 1) / INT_BITS;
    int[] map = new int[mapSize];

    int count = 0;
    List<Triangle> list = new ArrayList<>();

    for (final IQuadEdge e : edgePool) {
        if (e.getA() == null || e.getB() == null) continue;
        if (e.getA() == null || e.getB() == null || getMarkBit(map, e) != 0) continue;
        setMarkBit(map, e);

        IQuadEdge f = e.getForward();
        if (f.getB() == null) continue; // ghost triangle, not tabulated

        IQuadEdge r = e.getReverse();
        if ((getMarkBit(map, f) | getMarkBit(map, r)) != 0) continue;
        count++;

        Vertex triangleA = e.getA();
        Vertex triangleB = f.getA();
        Vertex triangleC = r.getA();

        list.add(new Triangle(toCoordinate(triangleA), toCoordinate(triangleB), toCoordinate(triangleC)));
    }
    return list;
}

`
data.zip

from tinfour.

from tinfour.

I have updated the library adding the getSide() method to the IQuadEdge class. An example of some code to collect triangles is attached for your inspection. The key to fixing the bug you encountered was that the collection of triangles must inspect both an edge and its dual. When the countTriangles() method in IncrementalTin was written, it was only necessary to inspect the "base side" of an edge. But that was actually an accident of the way I implemented the code, and there was no reason to expect that it would always be so. When constraints are added to the TIN, the rules change. So you will note that the attached code looks at both an edge and its dual.

You caught me in the middle of making a number of changes to support the new Constrained Delaunay Triangulation feature, so there's a bunch of unrelated code in this commit... It's all pretty well tested, so I do not anticipate that being a problem.

Also, the sample data you sent me uses geographic coordinates. Make sure that when you instantiate your TIN using geographic coordinates you make an appropriately small nominal point spacing value (typically 0.001) to reflect the fact that the significant digits for a geographic coordinate are so far down into the decimal points.

TriangleCollector.zip

from tinfour.

Thank you very much. TriangleCollector works. For this sample I use WGS84 coordinate system. It's just for testing purposes. I'm trying to evaluate your library in various scenarios. So far it is great. Thank you.

from tinfour.

I am glad that Tinfour is working out for you. Also, I am grateful for the two issues you identified. Both of them gave me opportunities to improve the software.

I am going to leave this issue open for a few days. I still have to clean up the countTriangles() methods in both the standard and semi-virtual Incremental TIN classes. If you don't encounter any additional problems with the triangle collection, I will close the issue when I turn in the next round of updates.

from tinfour.

Problem addressed. Also, the logic for counting triangles was moved into the TriangleCount class and the same logic is now shared by both the standard and semi-virtual implementations.

from tinfour.