У меня есть плоское множество точек P. Я уже знаю, какие точки p в P принадлежат границе B(p). Указанная граница может быть выпуклой или невыпуклой. Теперь я хотел бы найти триангуляцию P с границей B (p). Мои вопросы:
Есть ли алгоритм, который достигает этого напрямую? Близким кандидатом может быть триангуляция Делоне с ограничениями (CDT). Однако я не думаю, что CDT здесь применим: я мог бы ввести все ребра в B(p) в качестве ограничения, чтобы все ребра содержались в триангуляции. Однако это не обязательно означает, что это будет граница триангуляции. Поправьте меня, если я ошибаюсь здесь.
Если вы знаете такой алгоритм, можете ли вы указать мне (облегченную) библиотеку C, которая обеспечивает реализацию?
В качестве альтернативы: я мог бы, конечно, просто триангулировать P, используя стандартную триангуляцию Делоне из GTS. Затем мне нужно было бы обрезать все грани с вершиной за пределами B (p). Возможно ли это с ГТС?