Hi guys!!

I need to find an algorithm, independently from the language , that allow to order a sequence of points.

I try to explain. I have a sequence of points, of which i know the X,Y coordinates in a cartesian 2D space, like in the attached figure.

In this sequence the human eye can easily find a route, starting from one of the point. As following crumbs!

How can I order the points in this way? In other words how can I teach to a computer to recognaise a sequentiality in a series of points?
Of course just the human can see the points; the computer see only a table with the coordinates of each point.

Any suggestion? Please help

Thanks a lot.

Moving to Software Development.

The question is very abstract and vague. I know exactly what you mean, but you need to understand that different people can see different routes by looking at the same points. Probably the closest thing to solving such problem would be to take a point and put the closest point next to it. Then do the same thing for the second point (find the second closest point to it), etc....

Do you know what the route should be? If so, couldn't you just have a table with an index number which increments.
So:
1 10,10
2 20,10
3 20,15
etc..

So each coordinate will have an index number and you could just iterate through the list.
Or do you need something a bit more complex where you don't know the order?

Isn't this best done with a graph class?
Dijkstra's alg:
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

This post has been edited by sscheider: 27 Jul, 2009 - 09:16 AM

@ Neumann - I agree the Nearest Neighbor approach looks promising. couple of questions.. How would you determine the start of the path given all the coordinates at once. Also..this might not work if the specific case were to have a linear path that overlaps itself.. or runs closely parallel to itself.. . Any ideas what to do to make the Nearest Neighbor more robust for these typse of cases?

interested in your thoughts,

Aet

@Sscheider - I guess it would depend on whether the requirements meet the definition of the Dijkstra's algorithm. For instance.. the shortest path (Dijkstra) is not necessarily a complete iteration of all points..(traveling salesman).. I guess it depends on what the purpose of this path is..


Can the OP provide more information?

Aet

This post has been edited by Aeternalis: 27 Jul, 2009 - 10:50 AM

No. Graphs and Dijkstra's algorithm has absolutely nothing to do with this problem.


I would choose any point that lies on the border of the "point cloud". To do that you can simply choose a point with the greatest y-coordinate. If you have several points with the same greatest y-coordinates choose the one with the smallest x-coordinate.

About the distance algorithm. A brute-force approach would suffice for small cases. There is an efficient divide-and-conquer algorithm that you can check out - here.

Yes, my approach will not work for some basic cases. A simple solution would be to keep track of the last two points chosen and calculate the slope of the line that connects them. Then, when looking for a 3rd point, the slope of the line that connects a 3rd point to a 2nd point cannot deviate too much from the first slope. That will make sure that the algorithm does not take "sharp turns".

This post has been edited by Neumann: 27 Jul, 2009 - 12:50 PM

Noted. The applicability of Dijkstra's alg depends on how your set up the graph. I'm assuming the idea is:
1. You have a set of N points defined by coords.
2. One point is the start.
3. Each point must be visited once.

In this case, the graph is built on permutations of the points and ther relative distance between each of them. The end point handling must also be defined: is the end point nonspecific, specific, or a circuit back to the start point? All of these affect the graph layout. Once built, use Dijkstra.

Nonsense. Either you don't have a clear picture of the problem or you have no idea what graphs are and how to use them.

You are given a set of points. There are no edges, so this is not a graph. If you decide to add edges to turn it into a graph what will the edges represent? I can assure you that adding the edges that represent the distance between 2 points gives absolutely nothing to us.

But lets assume you've decided to waste time and memory and have made a complete graph. Then what are you going to do, use Dijkstra? Using Dijkstra on a complete graph with every 1-path being the shortest is absolutely useless. All it will do is check every other point and choose the closest one. Guess what, you're just doing a brute-force search that could've been done without graphs in the first place. Not only that, there's no easy way of modifying Dijkstra to implement some advanced filtering techniques that are used to make a more "natural" selection of the closest point so that it looks like a path.

Again, graphs have absolutely nothing to do with this problem.

This post has been edited by Neumann: 27 Jul, 2009 - 05:16 PM

@ alle77
Hey, did you find a solution?
I am interested in your problem since I have a comparable issue

see my recent post in this forum

This post has been edited by bertgertbert: 25 Aug, 2009 - 04:37 AM

Hi guys,

firts of all sorry if I reply this late but I worked on other topics and only now I came back on the routing problem.
Thanks a lot for the interest in try to solve my problem!!

Till now I implemented the solution suggested by Neumann:

[A simple solution would be to keep track of the last two points chosen and calculate the slope of the line that connects them. Then, when looking for a 3rd point, the slope of the line that connects a 3rd point to a 2nd point cannot deviate too much from the first slope. That will make sure that the algorithm does not take "sharp turns".
]

This solution works very well but only with the hypothesis that the points does not presents a route like that I show in the RoutingExample image. More exactly if there are not acute angles. In first instance I excluded this case but now I should consider it because in some cases it's present.

As you can see, following the route in one of the directions, or in the other, you have always the problem of the points in the angle !

With the solution I implemented the closest point of B is D! AND the line that connects the D point deviates very much from the slope of the one that connects the A -B - C points.

I'm afraid that this problem is not so easily solvable. Maybe it need a test condition that find the presence of an acute angle BEFORE launch the solution I implemented.

For find the first point of the series: it's not a trouble because generally I know the coordinates of the first point of the curve.
The routing sense (clockwise or counter) is not important.

I need to underline that I 'VE NOT A CLOUD of points, but a SEQUENCE of points, like a series of crumbs, which does not self-intersect.

Thanks a lot !!
Alle77

Just to make sure were not overlooking a very simple solution..

In your post you say you have a sequence of points. Are the points out of order?

The projection of a gear profile you provided can be solved with just the nearest neighbor approach it seems.

The acute angle problem might be solved by checking first for a slope that is similar to the last slope..(the line continuing on) and if not found then changing the slope iteratively until a point is found.

In your example of points it would calculate the slope of A-B. Then when looking for C would use A-B's slope and even though it finds D is closer, would choose C as it is still in proximity and is along the slope of A-B. So after it selects C it looks for D along the same slope.. doesn't find it within proximity, and so changes the slope a bit, continues to change the slope until it is pointing at D, and finds D within proximity. perhaps even continuing to change the slope until all points within proximity are found and then selecting the point that the difference in slope is the least.


EDIT :: Also within the process of selecting the point with the best matching slope, you could eliminate points that intersect a previous line as part of the selection.
Hope that helps!
Aet

This post has been edited by Aeternalis: 21 Sep, 2009 - 11:33 AM

If this was me, I would sort the points by the x-coordinate and graph them as such. When looking to the next point to graph, if there are multiple points with the same x-coordinate, look for the one with the y-coordinate closest to the current point. In some cases, you may need to look for a trend (ie,. if you have 1 point closer downward, but then a continually downward trend on the x-axis, it makes more sense to go up, then down).

Thanks a lot to all!

@Aeternalis

Yes, the points are completely out of order, fortunately they don't constitute a cloud but only "the perimeter of a cloud"

Now I will try to imlement Aeternalis 's idea for manage the acute angles problem, adding it to the algorithm previously suggested by Neumann.



Regards

Alle77