Why does my Delaunay Triangulation using the Bowyer Watson algorithm not work?

Question

I am implementing delaunay triangulation on a random set generated points, making use of the Bowyer Watson algorithm.

I seem to be running into a issue where the output seems to be generating way too many triangles that all overlap.

My output drawn from the triangulation made from a random set of points

My attempt at the algorithm is below.

void Delaunay::BowyerWatson(const std::vector<glm::vec2>& _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<Edge> 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());
}

If you would like to see all of my relevant code on this issue you can here

I set up a basic small sample size of set points to test this, and it seems to work as id expect until complexity increases

I have tried reformating and changing calculations in my code in numerous different ways, just looking for guidance on what my issue may be.

Answer 1

When looking to 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());

This only removes one of the duplicate edges found and leaves an unwanted one. Which later is used to create extra triangles to fill the poly hole.

Here is the fixed code:

std::sort(polygonEdges.begin(), polygonEdges.end());
std::vector<Edge> uniqueEdges;
for (size_t i = 0; i < polygonEdges.size(); ++i) {
  if (i + 1 < polygonEdges.size() && polygonEdges[i] == 
      polygonEdges[i + 1]) 
  {
    ++i;
  }
  else {
    uniqueEdges.push_back(polygonEdges[i]);
  }
}
polygonEdges.swap(uniqueEdges);