Сортировка и группировка массива сегментов линий, описывающих полигоны

Question

Я разбираю некоторые данные, заданные в виде массива сегментов линии, которые описывают несколько замкнутых произвольных фигур/полигонов. Эти формы могут быть вогнутыми. Вот упрощенный пример того, что я смотрю на:

Однако данные я предоставленные сегменты в произвольном порядке. Например, мои данные будут такими, как {V,E,D,X,U,A,Z,C,B,W,Y}. Таким образом, построение сегментов отображает правильные фигуры, но делать какие-либо операции с фигурами не легче.

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

Так

{V,E,D,X,U,A,Z,C,B,W,Y} 

станет

[ {A,B,C,D,E} , {X,Y,Z} , {U,V,W} ] 

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

Так что

[ {Y,Z,X} , {C,D,E,A,B} , {W,U,V} ] 

является столь же действительным результатом.

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

Answer 1

После дня головных пререканий, экспериментируя с предложениями здесь, и писать некоторые вспомогательные классы, я придумал что-то довольно обычным. В грубом псевдокоде, мое решение:

create group list; 

while (line segments exist in pool) 
{ 
    create new group; 
    remove one segment from pool and place into group; 

    while (endpoint of last line in group != startpoint of first line in group) 
    { 
     get the endpoint of the last line in group; 
     search pool for line segment whose startpoint = that endpoint; 
     remove that segment from the pool and place into group; 
    } 

    store group in group list; 
} 

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

Answer 2

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

• составить список узлов: каждый узел определяется двумя сегментами, которые он соединяет. например узел 1 - это узел, который соединяет сегменты A и E, узел 2 - узел, который соединяет A и B и т. д.

• группирует узлы к многоугольникам, т. е. объединяет все узлы, которые имеют общий сегмент.

• вы сделали