Алгоритм для получения многоугольной триангуляции с фиксированными внутренними ребрами?

Question

У меня есть два набора данных ребер, один из которых - внешние края (образуют замкнутый путь или многоугольник), другой - внутренние края внутри многоугольника (а не отверстия).

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

Answer 1

CGAL library обеспечивает constrained Delaunay triangulation класс, который должен делать то, что вам нужно. Кроме того, если вам нужно иметь меньшие элементы, вы можете попробовать 2D Meshing algorithm, который разделит ваши края, сохранив их форму.