Sorting and grouping array of line segments that describes polygons

Question

I'm parsing some data, given as an array of line segments that describe several closed, arbitrary shapes/polygons. These shapes can be concave. Here's a simplified example of what I'm looking at:

However, the data I'm provided has the segments in arbitrary order. Per the example, my data would be something like {V,E,D,X,U,A,Z,C,B,W,Y}. So, plotting the segments displays the correct shapes, but doing any operations on the shapes doesn't get any easier.

I am trying to sort the array above so that each closed shape's segments follow in connecting order, and each shape's segments are grouped together.

So

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

would become

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

The ordering of each group of line segments doesn't matter to me, only that the individual segments are in order. I also do not care about the particular starting segment of each group.

So that

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

is an equally valid outcome.

I'm not experienced with traversing geometry, and my rudimentary attempts and cursory online searches didn't yield any quick solutions. I looked into concave hulls, but that seems overkill given the data already knows the connections between the points.

Look at my answer (edit section) here: http://stackoverflow.com/questions/41245408/ — MBo, Dec 26 '16 at 14:27

score 2 · Accepted Answer · answered Dec 27 '16 at 13:38

After a day of head-wrangling, experimenting with suggestions here, and writing some helper classes, I came up with something pretty conventional. In rough pseudo-code, my solution is:

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

The code relies on the assumptions that my data contains only closed shapes (i.e. each shape's data neatly terminates on the same exact coordinates), and that all data creates shapes, not just orphan lines. I'm not sure how efficient this is, but given that this is used once as a pre-processing step, it's sufficient.

score 1 · Answer 2 · answered Dec 26 '16 at 12:40

If I can assume that you know the starting point and the end point of each segment (let's call them nodes), and that a polygon never has a common node with another one, then you can do the following:

make a list of the nodes: each node is defined by the two segments it connects. e.g. node 1 is the node that connects segment A and E, node 2 the node that connects A and B, etc.
group the nodes to polygons, i.e. put all nodes together which share a common segment.
you're done

Sorting and grouping array of line segments that describes polygons

2 Answers2