Эффективно разрезать триангуляцию (найти субтриангуляцию)

Question

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

Красный квадрат изображает область вырезать из исходной триангуляции, то есть найти суб триангуляцию, который имеет те же точки, что и исходные триангуляции плюс точек на границе каре.

Есть ли какой-либо эффективный алгоритм для выполнения такого разреза?

Answer 1

Вам необходимо использовать constrained Delaunay triangulation.

Библиотека CGAL, например, предоставляет implementation в C++. Когда вы говорите о местности, вы также должны посмотреть на это example.

Если вас интересует реализация java или python, некоторые привязки, написанные с помощью SWIG, доступны here.