Delaunay三角剖分：太多三角形 [英] Delaunay triangulation : too many triangles

问题描述

我正在尝试在C ++中实现Delaunay三角剖分。目前可以使用，但是我没有获得正确数量的三角形。
我尝试用4点以正方形模式进行尝试：（0,0），（1,0），（0,1），（1,1）。

I'm trying to implement the Delaunay triangulation in C++. Currently it's working, but I'm not getting the correct amount of triangles. I try it with 4 points in a square pattern : (0,0), (1,0), (0,1), (1,1).

这是我使用的算法：

std::vector<Triangle> Delaunay::triangulate(std::vector<Vec2f> &vertices) {

// Determinate the super triangle
float minX = vertices[0].getX();
float minY = vertices[0].getY();
float maxX = minX;
float maxY = minY;

for(std::size_t i = 0; i < vertices.size(); ++i) {
    if (vertices[i].getX() < minX) minX = vertices[i].getX();
    if (vertices[i].getY() < minY) minY = vertices[i].getY();
    if (vertices[i].getX() > maxX) maxX = vertices[i].getX();
    if (vertices[i].getY() > maxY) maxY = vertices[i].getY();
}

float dx = maxX - minX;
float dy = maxY - minY;
float deltaMax = std::max(dx, dy);
float midx = (minX + maxX) / 2.f;
float midy = (minY + maxY) / 2.f;

Vec2f p1(midx - 20 * deltaMax, midy - deltaMax);
Vec2f p2(midx, midy + 20 * deltaMax);
Vec2f p3(midx + 20 * deltaMax, midy - deltaMax);    

// Add the super triangle vertices to the end of the vertex list
vertices.push_back(p1);
vertices.push_back(p2);
vertices.push_back(p3);

// Add the super triangle to the triangle list
std::vector<Triangle> triangleList = {Triangle(p1, p2, p3)};

// For each point in the vertex list
for(auto point = begin(vertices); point != end(vertices); point++) 
{
    // Initialize the edges buffer
    std::vector<Edge> edgesBuff;

    // For each triangles currently in the triangle list    
    for(auto triangle = begin(triangleList); triangle != end(triangleList);) 
    {
        if(triangle->inCircumCircle(*point))
        {
            Edge tmp[3] = {triangle->getE1(), triangle->getE2(), triangle->getE3()};
            edgesBuff.insert(end(edgesBuff), tmp, tmp + 3); 
            triangle = triangleList.erase(triangle);
        }
        else
        {
            triangle++;
        }
    }

    // Delete all doubly specified edges from the edge buffer
    // Black magic by https://github.com/MechaRage 
    auto ite = begin(edgesBuff), last = end(edgesBuff);

    while(ite != last) {
        // Search for at least one duplicate of the current element
        auto twin = std::find(ite + 1, last, *ite);
        if(twin != last)
            // If one is found, push them all to the end.
            last = std::partition(ite, last, [&ite](auto const &o){ return !(o == *ite); });
        else
            ++ite;
    }

    // Remove all the duplicates, which have been shoved past "last".
    edgesBuff.erase(last, end(edgesBuff));

    // Add the triangle to the list
    for(auto edge = begin(edgesBuff); edge != end(edgesBuff); edge++)
        triangleList.push_back(Triangle(edge->getP1(), edge->getP2(), *point));


}

// Remove any triangles from the triangle list that use the supertriangle vertices
triangleList.erase(std::remove_if(begin(triangleList), end(triangleList), [p1, p2, p3](auto t){
    return t.containsVertex(p1) || t.containsVertex(p2) || t.containsVertex(p3);
}), end(triangleList));

return triangleList;

}

这就是我得到的：

Triangle:
 Point x: 1 y: 0
 Point x: 0 y: 0
 Point x: 1 y: 1

Triangle:
 Point x: 1 y: 0
 Point x: 1 y: 1
 Point x: 0 y: 1

Triangle:
 Point x: 0 y: 0
 Point x: 1 y: 1
 Point x: 0 y: 1

这是正确的输出：

Triangle:
 Point x: 1 y: 0
 Point x: 0 y: 0
 Point x: 0 y: 1

Triangle:
 Point x: 1 y: 0
 Point x: 1 y: 1
 Point x: 0 y: 1

我不知道为什么会有一个带有（0，0）和（1，1）的三角形。
我需要一个外在的眼光来审查代码，找出问题所在。

I have no idea why there is a triangle with the (0, 0) and the (1, 1). I need an outside eye to review the code and find out what's going wrong.

所有来源都在我的 Github存储库。

谢谢！

推荐答案

很可能您没有删除所有双边缘，尤其是没有删除相同三角形的边缘，但顶点仅以其他顺序删除。正确的功能在@cMinor的答案中。

Most likely you didn't delete all the double edges, especially not the edges from same triangles but with vertices only in another order. The correct function is in the answer from @cMinor.

这篇关于Delaunay三角剖分：太多三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！