Полигоны из сегментов линии

Question

У меня есть список сегментов линий в определенном порядке.

Я хочу найти все замкнутые пространства (многоугольники), образованные сегментами. Есть ли эффективный алгоритм или метод, который я мог бы использовать для этого?

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

Answer 1

Одним из способов было бы построить график следующим образом:

• узлы являются точками пересечения ребер

• существует ребро между узлами я и j iff points i и j находятся на том же краю

После того, как вы построили график:

• Запускаем Connected Components Algorithm на нем, и проверьте компонент связности размера> 2

• побегать convex hull в точках пересечения внутри такого компонента

Редактировать изменен из оригинала из-за отличной точки от FooBar.