Robust Algorithm to Order Parallel Polylines

In summary, the convex hull can be used to order a set of lines, which may be helpful in solving the problem you are facing.
  • #1
Kyudos
6
0
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!
 
Physics news on Phys.org
  • #2
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...
 
  • #3
I think this will work in most situations:

Lines
LineOrder.png


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
PolyOrder.png


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.
 
  • #4
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?
 
  • #5
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)
 
  • #6
Kyudos said:
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.
 
  • #7
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).
 
  • #8
Kyudos said:
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.
 
  • #9
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)
 

1. What is a robust algorithm for ordering parallel polylines?

A robust algorithm for ordering parallel polylines is a mathematical process that determines the optimal order in which to connect a set of lines that are parallel to each other. This is useful for creating efficient and organized polyline systems in various applications, such as computer graphics and routing systems.

2. How does the algorithm work?

The algorithm works by first identifying the endpoints of each polyline and then comparing their positions to determine the best order for connecting them. It takes into account the direction and proximity of the lines to create a smooth and efficient order.

3. What are the benefits of using this algorithm?

Using this algorithm can lead to more organized and efficient polyline systems, which can improve the overall performance and accuracy of applications that utilize them. It can also save time and effort in manually ordering the polylines.

4. Can this algorithm be applied to any type of parallel polylines?

Yes, this algorithm can be applied to any set of parallel polylines, regardless of their shape or orientation. It is designed to work with a variety of inputs and can handle both simple and complex polyline systems.

5. Are there any limitations to this algorithm?

Like any algorithm, there may be some limitations depending on the specific application and data being used. For example, if the polylines are very close together or overlap, the algorithm may not be as effective. It is important to test and fine-tune the algorithm for the specific use case to achieve the best results.

Similar threads

  • Differential Geometry
Replies
1
Views
2K
Replies
32
Views
2K
  • Electrical Engineering
Replies
30
Views
2K
  • Mechanics
Replies
18
Views
2K
Replies
44
Views
21K
  • Introductory Physics Homework Help
Replies
4
Views
1K
  • Electrical Engineering
Replies
2
Views
2K
Replies
5
Views
1K
Back
Top