Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I hava a very interessting problem, which I'm working on right now. I hava a dataset with a few points, and I'd like to know the shortest LINE to interconnect every point. No needs for routing etc. The result should be a sorted list with points or a linestring...

I'd realy appreciate your input, I have an idea about the concept but I don't know where to start. This nut is hard to crack. It's like a dijkstra-one-to-many problem, but without the routing, so should be easier and faster....

Thank you! Martin


edit:

Picture

share|improve this question
    
You just need to connect all the points? Could you post a graphic to illustrate your problem and objective? –  R.K. Oct 11 '12 at 10:27
    
Added a picture, it's for something like a microrouting to get en estimate idea. pgRouting will not work with this problem, as there are no nodes there... –  Styp Oct 11 '12 at 12:10
3  
Sounds like the traveling salesman without start = end node. –  underdark Oct 11 '12 at 12:30
    
Thought about that! But how to do it in postgis, otherwise it will have unfortunate performance... –  Styp Oct 11 '12 at 12:40
2  
Of course this problem can be modeled as a network of nodes and edges and pgRouting can solve TSP pgrouting.org/docs/1.x/tsp.html –  underdark Oct 11 '12 at 15:30
show 2 more comments

2 Answers 2

It would seem that what you want to accomplish is a Hamiltonian path.

In the mathematical field of graph theory, a Hamiltonian path (or traceable path), is a path in an undirected graph which visits each vertex exactly once.

enter image description here

PostGIS 2.0 has topology support so maybe you can implement it with that. Not sure if there are out of the box solutions though. Be warned that this is an NP-complete problem. Finding the path is a challenge in itself, let alone the shortest. Though if your points aren't that many then should be able to manage. Good luck.

share|improve this answer
    
The image in the question certainly shows no minimum spanning tree –  underdark Oct 11 '12 at 15:28
    
Noted. Will find a better one. –  R.K. Oct 11 '12 at 15:31
1  
What I meant is that Martin seems to be looking for a solution that gives an ordered list rather than a tree. –  underdark Oct 11 '12 at 15:58
    
Oh that. He just wants a line to to connect all nodes. x_x –  R.K. Oct 11 '12 at 16:15
1  
R has a PairViz package that has functions zigzag and hpaths. Might be useful. –  klewis Oct 11 '12 at 18:53
show 1 more comment

Thank you for the input! I appreciate that. I found my solution and it works! For everyone else, who has a similar problem - read these articles on Wikipedia and start your research there:

And tbh the nearest neighbour is already a strong solution, with k-opt you can optimize, but to optimize 5% further down - you need a lot of time. I tested with my 'raw' data and had 10ms to get a nearest neighbour solution on 100 way points. But furtherdown the k-opt is running for several minutes...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.