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

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

введите здесь описание изображения

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

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

So

{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} ]

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

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


arrays sorting geometry language-agnostic line-segment
person interloper    schedule 26.12.2016    source источник
comment
Посмотрите мой ответ (раздел редактирования) здесь: stackoverflow.com/questions/41245408   -  person MBo    schedule 26.12.2016

Ответы (2)


arrow_upward
2
arrow_downward

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

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;
}

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

person interloper    schedule 27.12.2016

arrow_upward
1
arrow_downward

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

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

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

  • ты закончил

person user7291698    schedule 26.12.2016