Обнаружение многоугольника из набора линий?

Question

У меня есть набор связанных, пересекающихся отрезков. Я хочу, чтобы обнаружить все полигоны, которые являются результатом пересечения этих отрезков прямых, а именно:

Я нашел документ, который представляет собой алгоритм для решения этой проблемы, но я на самом деле не компьютерная наука так что я не мог этого понять. Вот ссылка на paper. В этот момент мой план состоит в том, чтобы: 1) найти все пересечения и 2) каким-то образом использовать эти пересечения для идентификации многоугольников. Я могу решить (1) с помощью грубой силы, но (2) немного сложнее. Я бы предпочел решение в R или C++, но любой язык будет делать.

Answer 1

Предполагая, что у вас есть сегменты линии всегда как замкнутая многоугольная цепь, и у вас есть их в каком-то списке краев. И, как вы сказали, у вас уже вычисленные точки пересечения (грубая сила означает время O (n^2), в этом случае это оптимально, так как сегменты линии могут пересекаться n^2 раза).

Вы можете вставить точки пересечения из (1) в этот список, разделяющие пересекающиеся сегменты линии, пометить их как точки пересечения и ссылаться на все пересекающиеся сегменты линии в этой точке. Кроме того, на каждом сегменте линии падают два многоугольника, таким образом добавляя соответствующие опорные поля к каждому ребру. Затем просто возьмите левую верхнюю вершину в вашем входе и пройдите по краю списка. Добавьте к каждому ребру, на котором проходит ссылка на его левый многоугольник (в данном случае) многоугольник номер один. Если вы достигнете точки пересечения, поместите его в какой-то стек для последующего восстановления. Теперь проанализируйте эту точку и продолжайте движение по самому левому пути (между сегментом линии, по которому вы достигли точки пересечения и всех исходящих сегментов). В какой-то момент вы достигнете своей начальной точки, и у вас будет первый простой многоугольник.

Теперь возьмите первую точку пересечения из стека. Должно быть четное число сегментов линии, которые начинаются и заканчиваются там. Найдите сегмент линии, у которого есть не более одного инцидента, на который ссылается (пока), и используйте его как начальный сегмент для многоугольника номер два. Вы можете ходить вдоль своей цепи так же, как раньше. (Если вы ссылаетесь на многоугольник с правом инцидентом в сегменте линии, сделайте правый поворот в точке пересечения.) Когда ваш стек пуст, вы закончите.

---

Edit: После того, как я посмотрел еще раз на решение, которое я нашел implementation from Dan Sunday. Я предполагаю, что это более полезно, поскольку оно также уже реализовано.

Answer 2

Alfredo Ferreira разработал код C++ для обнаружения полигонов из набора перекрывающихся линий. Вы можете найти код на своей странице здесь: http://3dorus.ist.utl.pt/tools/PolygonDetector.html Надеюсь, что это поможет