Выявление триангуляции многоугольника в результате ограничивающей триангуляции Делоне

Question

У меня есть набор полигонов, которые могут иметь общие ребра и узлы. Все эти многоугольники строго не перекрываются, хотя могут иметь общую вершину или ребро.

Я хочу триангулировать все эти многоугольники в пакете, поэтому решение, которое я могу придумать, - это триангуляция Делоне с ограничением. Но выходные данные Constraint Delaunay Triangulation будут генерировать треугольники, которых нет в исходных многоугольниках.

Есть ли способ идентифицировать эти треугольники вне полигона?

Редактировать: У Matlab есть способ сделать это через inOutStatus; Я ищу такой алгоритм, независимый от языка.

Answer 1

Многие пакеты триангуляции Делоне (такие как Треугольник , которые я бы порекомендовал) обычно включают в себя возможность автоматического удаления «внешних» треугольников из триангуляции. Ознакомьтесь с документацией.

Если это не так для вашего алгоритма, вы должны быть в состоянии обрезать внешние треугольники, проверяя, находится ли центроид каждого треугольника в пределах полигона (ов), которые вы указали в качестве ограничений, через точку в тесте полигонов, например. Это всегда должно работать, так как ограниченная триангуляция Делоне будет гарантировать, что никакие ребра треугольника не пересекают ребра полигонального ограничения (нет шансов на частичный треугольник входа / выхода).

Еще одно соображение для вашей проблемы - пакетная обработка, которую вы описываете. Сложность большинства (если не всех) алгоритмов триангуляции Делоне является нелинейной (Triangle достигает O(n*log(n))), поэтому я думаю, что вы на самом деле достигнете ускорения, обрабатывая полигоны один за другим, а не все сразу .