Как разделить сложный многоугольник на простые многоугольники?

Question

Как разделить сложный многоугольник на простые многоугольники?

У меня проблема со сложными многоугольниками, мне нужен алгоритм для разделения (или поиска) простого многоугольника, образованного через сложный многоугольник.

Например:

Комплекс полигонов с точками, пронумерованными в том порядке, в котором они были нарисованы. В результате мы получим 4 простых полигона:
http://i1338.photobucket.com/albums/o699/ssbb91/poly1_zps9e7888a5.png?t=1379653091

Здесь другой случай более сложный:
http://i1338.photobucket.com/albums/o699/ssbb91/poly2_zps1e9753ca.png

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

1

algorithm math geometry polygon freeware

Источник

user2797749 20 сен '13 в 05:08

1 ответ

Решение

Другие вопросы по тегам algorithm math geometry polygon freeware

user359538 20 сен '13 в 15:16 2013-09-20 15:16 · Accepted Answer · 2013-09-20 15:16

Моя библиотека Clipper преобразует самопересекающиеся многоугольники в простые.
Смотрите документацию здесь.

Примечание: это значительно улучшено в (скоро будет выпущен) версии Clipper 6, которую можно скачать из репозитория SourceForge здесь.

Изменить: документация для версии 6 здесь