Повторяющиеся края не удаляются в конструкции треугольника Делоне

Question

Я пытаюсь реализовать триангуляцию Делоне. Однако у меня, похоже, проблема с краями, создающими перекрывающиеся треугольники:

Я основываю свою реализацию, как описано на этом сайте. Я просто использую петлю грубой силы, чтобы проверить, существует ли ребро в наборе.

v = vertex to be added
edgeBuffer = [];
for each triangle
    if v is in the triangle's circumscribed circle
        for each edge in the triangle
            check if it's already in edgeBuffer
            if not, add it
        remove triangle

Я подозреваю, что это еще одна часть моего алгоритма, которая идет не так и вызывает это, но я реализовал все довольно просто. Что не так с этим кодом? скрипка

Answer 1

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