1
我正试图在C++中实现Delaunay三角剖分。目前它正在工作，但我没有得到正确数量的三角形。 我用4点的方格式来尝试它：（0,0），（1,0），（0,1），（1,1）。Delaunay三角剖分：太多的三角形
这是我使用的算法：
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
我没有我dea为什么有一个与（0，0）和（1，1）的三角形。 我需要一个外部的眼睛来审查代码，并找出发生了什么问题。
所有来源都在我的Github repo上。随意分叉它，并PR您的代码。
谢谢！
欢迎so so！我马上发现的是，第一个，有缺陷的三角形的集合和预期结果的集合都是均匀的。 –
我真的不明白你在说什么（英语不是我的第一语言）。你在谈论我处理超级三角形或程序输出的方式？ – Bl4ckb0ne
输出。只需画一个正方形，标出点，然后用铅笔沿着点到点的路径“走”。 –