Упрощение сетки половинного ребра — во вновь вставленной вершине найдено 0 соседних треугольников. ⇐ C++

[Anonymous]

Я новичок в мире кодирования, и у меня есть проект на C++, с которым я борюсь.
Я реализую алгоритм упрощения сетки ландшафта (Жадная вставка/TIN), используя комбинаторную карту половинного ребра на C++. В структуре используется навигация d->precedent()->oppose() для перемещения по грани и d->suivant() для вращения вокруг вершины.
Обзор алгоритма

• Триангуляция 4 угловых точек → 2 начальных треугольника
• Распределение всех точек на эти 2 треугольника
• Поддержание multiset, отсортированный по максимальной ошибке (сначала худшая точка)
• Каждая итерация: берём худший треугольник, вставляем его худшую точку, перераспределяем точки в новые треугольники, применяем локальный Делоне

Проблема
После вставки первой точки P в треугольник (с помощью вставкиDansFace) я пытаюсь найти новую создал треугольники вокруг P, вращая его с помощью suivant(). Однако обнаружено 0 треугольников, перераспределение завершается неудачно, и цикл завершается после 1 итерации вместо ~100 тыс.

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

// After inserting P:
DemiCote* dep = nouveau->demiCote();
DemiCote* cur = dep;
int guard = 0;
do {
DemiCote* d2 = cur->precedent()->oppose();
DemiCote* d3 = d2 ? d2->precedent()->oppose() : nullptr;
DemiCote* cands[3] = {cur, d2, d3};
for (DemiCote* c : cands) {
if (!c || c->marque() != 0) continue;
Triangle* nt = creerTriangle(c); // checks tour closes: d->prec()->opp() x3 == d
if (!nt) continue;
// redistribute points...
file.insert(nt);
break;
}
cur = cur->suivant();
if (!cur || ++guard > 30) break;
} while (cur != dep);
// Result: 0 triangles found

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

creerTriangle

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

Triangle* creerTriangle(DemiCote* d) {
if (!d || d->marque() != 0) return nullptr;
DemiCote* d2 = d->precedent()->oppose();
if (!d2) return nullptr;
DemiCote* d3 = d2->precedent()->oppose();
if (!d3) return nullptr;
if (d3->precedent()->oppose() != d) return nullptr; // tour must close
return new Triangle(d, d2, d3);
}

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

insererDansFace

(проверяется отдельно)

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

Sommet* Carte::insererDansFace(DemiCote* ab, const Point& p) {
DemiCote* bc = ab->precedent()->oppose();
DemiCote* ca = bc->precedent()->oppose();
DemiCote* pa = ajouteCote(p, ab->precedent());
DemiCote* pb = ajouteCote(pa, bc->precedent());
DemiCote* pc = ajouteCote(pb, ca->precedent());
return pa->sommet();
}

Что я подозреваю
После вставкиDansFace новые полуребра, полученные из P, могут не формировать действительные обходы закрытых граней через prec()->opp(), поэтому creerTriangle возвращает nullptr для всех из них. ИЛИ suivant() неправильно вращается вокруг P, пропуская некоторые соседние грани.
Вопросы

• После вставкиDansFace в треугольнике ABC, какова правильная навигация для перечисления трех новых треугольников вокруг P?
• Правильно ли suivant() вращаться вокруг вершины в этой полуреберной структуре, или вместо этого мне следует использовать прецедент()->oppose()?
• Можно ли применить Делоне (переворот ребер) перед перераспределением, чтобы сделать недействительными ссылки DC, хранящиеся в объектах Triangle?

Дополнительная информация

• Методы вставки (

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

  insererDansFace

  ,insererSurBord,insererSurInterne) проверены индивидуально

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

  marquerEnveloppeConvexe

  правильно отмечает граничные полуребра (marque=1) и внутренние (marque=0)
• Флип Делоне правильно обновляет мультимножество треугольников при возникновении флипа

Любая помощь приветствуется. При необходимости мы будем рады поделиться дополнительным кодом.

Подробнее: https://stackoverflow.com/questions/799 ... riangles-f