Как триангулировать комнату препятствий?

Question

Я хотел бы триангулировать комнату, полную полигональных препятствий.

Я особенно ищу простой алгоритм для реализации, так как я тестирую другую функциональность на данный момент. Эффективность (при условии, что она может обрабатывать несколько десятков вершин в течение минуты), а «качество» треугольников не будет рассматриваться. Прямо сейчас моя мысль состоит в том, чтобы перебирать каждую вершину, проверяя другие вершины, к которым она может подключиться, не пересекая ранее сделанные соединения. Существуют ли более простые решения или любые недостатки этого подхода?

Благодаря

Answer 1

Вы можете триангуляции всех вершин, а затем удалить самые длинные края, подобные альфа-форму. Вы можете посмотреть пример на моей домашней странице: http://www.phpdevpad.de/geofence.

Answer 2

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

Если вы ищете реализацию на C++, вы можете взглянуть на CGAL library и, в частности, на this example, который делает то, что вы хотите.