Infinite loop in `insertVertex`

[Michael2109]

I've noticed that sometimes an infinite loop can occur in insertVertex. If I print out the triStack size it increases indefinitely. It seems that `isFlipNeeded is returning true and constantly pushing new elements.

I'm using your library for my game and it's procedurally generated so this occurs every now and again so I'm struggling to create test data for this. Is this likely something to do with me inserting incorrect data or a bug?

Here is my code for triangulation. The calculated polygon is a vector containing doubles.

CDT::Triangulation<double> cdt;
std::vector<CustomPoint2D> points;

for (int i = 0; i < calculatedPolygon.size(); i += 2) {
    points.push_back({calculatedPolygon[i], calculatedPolygon[i + 1]});
}

cdt.insertVertices(
        points.begin(),
        points.end(),
        [](const CustomPoint2D &p) { return p.data[0]; },
        [](const CustomPoint2D &p) { return p.data[1]; }
);

std::vector<CustomEdge> edges;

for(int i = 0; i < points.size()-1; i++){

    CustomEdge customEdge;
    customEdge.vertices.first = i;
    customEdge.vertices.second = i+1;
    edges.push_back(customEdge);
}

cdt.insertEdges(
        edges.begin(),
        edges.end(),
        [](const CustomEdge &e) { return e.vertices.first; },
        [](const CustomEdge &e) { return e.vertices.second; }
);

cdt.eraseOuterTrianglesAndHoles();

delaunator::Delaunator d(calculatedPolygon);

[artem-ogre]

Hi, Michael,

Thanks for creating the issue. The reason could be:

• You have duplicated vertices in your input: you insert a vertex into a triangulation that already contains a point with exactly the same coordinates. You can use CDT::FindDuplicates method to check for duplicates in your input.
• There is a bug in CDT. To fix this I would need an example of input that reproduces the issue. Perhaps you could break when the problem occurs and dump the content of points?

Provided code looks good to me at a quick glance. Except unless you have some other usages of CustomPoint2D you could use CDT::V2d without providing the getters. Also do you experience this issue on the latest master?

[Michael2109]

Thank you for the quick reply! I'll check for duplicates and if not I'll look into creating some data to reproduce the bug.

Yes I'm using master. I cloned it yesterday.

[Michael2109]

@artem-ogre It was duplicates! My algorithm that generated my polygon includes the end point which is the same as the start point.

Got to say that this library is amazing! Extremely fast and much easier to use then others I've seen.

Thank you for the quick response!

[artem-ogre]

Great! I'm happy that it works and you like it. :)