Robust Algorithm to Order Parallel Polylines

[Kyudos]

I'm trying to come up with a way to order 'random' (poly) lines, knowing only the coordinates of the vertices (and, obviously, which vertices belong to any given line).

I'm not a mathematician or geometrician, but I have a feeling there must be an 'easy' way to do this!

Would probably have to break down the problem something like this:

1) Somehow, calculate a 'direction' for the ordering (e.g., vertical lines could be ordered left-to-right or right-to-left, horizontal lines top-to-bottom or bottom-to-top, polygons inside-to-outside etc.)

2) Decompose the lines to some simplified property (the centroid?) that will put them "in order" along the direction from 1).

Any suggestions gratefully received!

 

[Kyudos]

Thinking more about this, if I can draw a (poly) line through all the other (poly) lines, finding the intersections from one end to the other would given me the order I'm after.

Now, how to figure that out...

 

[Kyudos]

I think this will work in most situations:

Lines

1) Draw the bounding rectangle (red).
2) Extend the lines to the boundary (blue).
3) Draw diagonal that has largest angle to lines (green)
4) Order is given by distance of intersections along diagonal.

Polylines

1) Draw the bounding rectangle of line ends(red).
2) Connect line ends and extend to the boundary (blue).
3) Draw diagonal that has largest angle to lines (green)
4) Order is given by distance of intersections along diagonal.

I'm sure there are some configurations of polylines where this will break down, but this might just do for my purposes.

 

[chiro]

Hey Kyudos and welcome to the forums.

I'm interested in what you are doing: how are you trying to classify your lines? Also what is the background for this kind of investigation of exercise?

 

[Kyudos]

Hi Chiro and thanks for the welcome.

I'm trying to draw (literally, in a CAD program) an operating region (a polygon) defined by two points on each line. In order to draw the polygon, I need to add the points in the correct order. If the lines themselves are "in order" this is simply a case of adding Line 1, Point 1 to the start of my polygon, and Line 2 Point 2 at the end and so on.

Ordering is just the first part of the problem. Since my lines may have been drawn either way round, Point 1 on a given line might actually be 'at the other end' compared to Point 1 on the previous or next line, so I'd have to determine that too.

In the end it might just be simpler to take all my points and throw them at a traveling salesman routine.

(The 'real' problem is actually from irrigation. Each line represents a drip feed irrigator, on which there are two points between which you can feed water into the system and still have enough pressure to operate properly at both ends of the line)

 

[chiro]

Hi Chiro and thanks for the welcome.

I'm trying to draw (literally, in a CAD program) an operating region (a polygon) defined by two points on each line. In order to draw the polygon, I need to add the points in the correct order. If the lines themselves are "in order" this is simply a case of adding Line 1, Point 1 to the start of my polygon, and Line 2 Point 2 at the end and so on.

Ordering is just the first part of the problem. Since my lines may have been drawn either way round, Point 1 on a given line might actually be 'at the other end' compared to Point 1 on the previous or next line, so I'd have to determine that too.

In the end it might just be simpler to take all my points and throw them at a traveling salesman routine.

(The 'real' problem is actually from irrigation. Each line represents a drip feed irrigator, on which there are two points between which you can feed water into the system and still have enough pressure to operate properly at both ends of the line)

I think I know something that will help you:

http://en.wikipedia.org/wiki/Convex_hull

http://en.wikipedia.org/wiki/Convex_hull_algorithms

The convex hull creates an ordered, oriented set of polytypes (lines for 2D, planes for 3D, others for higher) in a way that the list corresponds to a specific orientation that is "counter-clockwise" (This is hard to state for three or higher dimensional spaces).

You can recognize the 2D by specifying a set of lines and the interior of all of the lines denotes the two dimensional polygon enclosed within the region.

Because of the natural ordering of the structure, it will probably help you in your application since you can a) use a universal algorithm to reorder if the structure changes and b) use existing structural information to create optimizations if you are doing some specific that has highly local changes as opposed to global changes.

This information has to be used in the context of your problem, but the structure of the convex hull might give you ideas to help you solve your problem and due to the nature of the ordered properties of the hull, it might be adapted into something else that might be useful.

 

[Kyudos]

I considered the convex hull, but it doesn't necessarily include all the points does it? I know that each of the two points on each line are on the boundary of my desired polygon. They all need to be included, that's why I thought a TSP would be the simplest solution, if ordering turned out to be complicated (as it seems to be).

 

[chiro]

I considered the convex hull, but it doesn't necessarily include all the points does it? I know that each of the two points on each line are on the boundary of my desired polygon. They all need to be included, that's why I thought a TSP would be the simplest solution, if ordering turned out to be complicated (as it seems to be).

Yes you are right it does not, but more or less the intention of my post was to just throw some ideas your way and see if you can make use of them.

Also with TSP the run-time is going to be humongous but if you have a fairly limited sized graph then you might as well use it.

Also maybe you could consider some kind of transform that you could use in cojunction with the convex hull. You might for instance modify the hull algorithm so that you can adapt it to easily add points where they need to be using your own spatial classification scheme.

The implementation could be using the hull algorithm but adding some 'extra code' in where it determines the next point in the list. The hull basically uses a minimization of angle to get the next polytype but you could some extra code to do your own stuff to create the next entry in the list which is the mechanism that 'orders' the data.

 

[Kyudos]

Yeah, ordering is straightforward for a group of parallel single lines - rotate them to vertical or horizontal and use the coordinates, rotate them back again. But since the set of lines I'm working on is user selected, I'd have to first try and determine if this was my situation

I was hoping for a generic solution for lines and polylines that is as independent as possible from the way users create the input. TSP still seems like the best choice, if I can make it fast enough (and things like LKH seem pretty fast)