Почему моя триангуляция Делоне с использованием алгоритма Бойера-Ватсона не работает? ⇐ C++

[Anonymous]

Я реализую триангуляцию Делоне для точек, сгенерированных случайным набором, используя алгоритм Бойера-Ватсона.
Похоже, я столкнулся с проблемой, из-за которой выходные данные генерируют путь слишком много треугольников, которые все перекрываются.
Мой результат получен на основе триангуляции, полученной из случайного набора точек.
Моя попытка реализации алгоритма приведена ниже.

Код: Выделить всё

void Delaunay::BowyerWatson(const std::vector& _points) {
glm::vec2 p1(-1000, -1000), p2(1000, -1000), p3(0, 1000);  // Large super triangle
Triangle superTriangle(p1, p2, p3);
m_triangles.push_back(superTriangle);

for (const auto& point : _points) {
std::vector polygonEdges;

// Identify and remove all bad triangles
auto it = m_triangles.begin();
while (it != m_triangles.end()) {
if (it->circumcircleContains(point)) {
Edge edges[3] = {
{it->vertices[0], it->vertices[1]},
{it->vertices[1], it->vertices[2]},
{it->vertices[2], it->vertices[0]}
};
for (const Edge& edge : edges) {
polygonEdges.push_back(edge);  // Collect edges of bad triangles
}
it = m_triangles.erase(it);  // Remove bad triangle
}
else {
++it;
}
}

// Remove duplicate edges
std::sort(polygonEdges.begin(), polygonEdges.end());
polygonEdges.erase(std::unique(polygonEdges.begin(), polygonEdges.end(),
[](const Edge& a, const Edge& b) {
return (a == b) || (a.m_start == b.m_end && a.m_end == b.m_start);
}), polygonEdges.end());

// Re-triangulate the polygonal hole
for (const Edge& edge : polygonEdges) {
Triangle newTriangle(edge.m_start, edge.m_end, point);
m_triangles.push_back(newTriangle);
}
}

// Remove triangles that contain vertices of the super triangle
m_triangles.erase(std::remove_if(m_triangles.begin(), m_triangles.end(),
[&p1, &p2, &p3](const Triangle& tri) {
return tri.containsVertex(p1) || tri.containsVertex(p2) || tri.containsVertex(p3);
}), m_triangles.end());
}

Если вы хотите увидеть весь мой соответствующий код по этой проблеме, вы можете здесь.
Я установил базовую небольшую выборку заданных значений. чтобы проверить это, и, похоже, он работает так, как и ожидалось, пока сложность не увеличится.
Я пробовал переформатировать и изменять вычисления в своем коде разными способами, просто ищу рекомендации о том, в чем может быть моя проблема. быть.

Подробнее здесь: https://stackoverflow.com/questions/787 ... m-not-work