Алгоритм завершения частичной триангуляции (Ограниченная триангуляция)

Question

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

ОБНОВЛЕНИЕ "Вы получили выпуклую оболочку из набора точек R ^ 2, который в основном является многоугольником с некоторыми точками внутри него. Мы хотим триангулировать множество точек, что само по себе является простым вопросом, но вы Вам также даны некоторые ребра, что любая триангуляция, которую вы придумали, должна использовать эти ребра. "

Answer 1

Возможно, это наивный ответ, но вы не можете просто использовать ограниченную триангуляцию Делоне?Добавьте известные ребра в качестве ограничений.

CGAL имеет хорошую реализацию .Инструмент треугольник имеет аналогичные функции и с ним легче начать работу, но имеет (возможно) немного меньшую гибкость.

Answer 2

Я обнаружил, что в книге «Вычислительная геометрия: введение» подробно рассматривается этот предмет, хотя он не дает готового к реализации псевдокода.

Самый простой алгоритм - это жадный алгоритм, который перечисляет все возможные ребра и затем добавляет их один за другим, избегая пересечения с ранее добавленными возрастами. В книге долго обсуждается, как сократить время работы до O (n ^ 2 log n).

Затем существует алгоритм O (n log n), который сначала регулирует выпуклую оболочку с заданными ребрами, а затем индивидуально триангулирует каждый монотонный многоугольник.