Алгоритм завершения частичной триангуляции (Ограниченная триангуляция)
Учитывая набор точек на плоскости и неполную триангуляцию выпуклой оболочки точек (даны только некоторые ребра), я ищу алгоритм для завершения триангуляции (начальные заданные ребра должны оставаться фиксированными). Вы можете предположить, что можно выполнить частичную триангуляцию, но было бы неплохо, если бы вы также предложили алгоритм для проверки этого.
ОБНОВЛЕНИЕ "Вам дана выпуклая оболочка набора точек R^2, который в основном является многоугольником с некоторыми точками внутри него. Мы хотим триангулировать множество точек, что само по себе является простым вопросом, но вы также учитывая некоторые ребра, что любая триангуляция, которую вы придумали, должна использовать эти ребра."
2 ответа
Возможно, это наивный ответ, но вы не можете просто использовать ограниченную триангуляцию Делоне? Добавьте известные ребра в качестве ограничений.
CGAL имеет хорошую реализацию. Треугольник инструмента имеет схожие характеристики и с ним легче начать работу, но он (возможно) обладает меньшей гибкостью.
Я обнаружил, что в книге "Вычислительная геометрия: введение" подробно рассматривается этот предмет, хотя он не дает готового к реализации псевдокода.
Самый простой алгоритм - это жадный алгоритм, который перечисляет все возможные ребра и затем добавляет их один за другим, избегая пересечения с ранее добавленными возрастами. В книге долго обсуждается, как сократить время работы до O(n^2 log n).
Затем существует алгоритм O(n log n), который сначала регуляризует выпуклую оболочку с заданными ребрами, а затем индивидуально триангулирует каждый монотонный многоугольник.