How to combine a number of coordinates with one continuous line?

Hi all,

I was wondering whether there exists a solution/algorithm for my problem: I have a large number of coordinates, e.g. nodes, that I want to automatically link with one continuous line. The problems are my restrictions:

1. Each node must only be covered once
2. The lines must not overlap with other lines or coordinates
3. There's a maximum length for the lines
4. I want to feed in arbitrary structures

Are there any ideas on how I could solve this issue? Shown are some examples for the rules, they don't cover all of them though.

Thanks a lot in advance! Jay

[Walter Roberson]

In your second example you show a line of length 4, the one across the bottom. Given that, there is no obvious reason why the diagonal line of the third example should have been prohibited.

[Image Analyst]

I think it is considered as 4 lines of unit length going through each dot, though the drawing is not quite so perfect.

[Esteban]

Hi, Jay and Walter. I have the same problem with diagonal lines. You have already solved it ?. I am using Tabu Search and Simulated Annealing, and I have the same problem. I did not manage to limit the matrix of distances to avoid diagonals, I even placed inf. I wait for your comments

[Walter Roberson]

Esteban, are your points on a regular grid for which only immediate horizontal and vertical connections are possible?

Do you have the restriction against crossing lines?

[Image Analyst]

Esteban - that's ambiguous. Do you mean you have the problem where you have a square grid and diagonal lines are not allowed? Or do you mean that you have the grid problem but the lines are diagonal, like with diamond-shaped cells instead of square shaped cells? Please post a diagram in your own new question.

[João Rosas]

hi! i have that same problem, can you please give me the code? i don't know how to code :(

Answer 1

[Image Analyst]

Well, the easy one is step #3. Use pdist() (In the stats toolbox) to find distance from every point to every other point. Then take the max of that. If that max distance is more than your max allowable line length, then there is no solution.

Assuming it passes that test, then there could be multiple solutions. Imagine a rectangular grid. There are tons of ways you could draw a single line connecting them all: raster up/down, raster left right, raster diagonally, spiral inwards, spiral outwards, etc.

Is any solution okay? Or do you need the shortest path, like the famous "Traveling Salesman Problem"? Do you have any specified starting and ending points? Or can you start and stop on any point, and you need to find the endpoints that give you the shortest total path length?

[Jay Muller]

That's a fast reply, thank you so much. It might've even overlapped with my edits (sorry for that).

Is any solution okay? As long as it's withing the rules, yes. I only need one solution.

Or do you need the shortest path, like the famous "Traveling Salesman Problem"? That would be nice, and is actually the end-goal, but less important than the rules. Also, it is already partially covered by the requirements (e.g. in my drawn example I set the max. line length for example to the shortest distance between nodes, that prevents e.g. diagonal connections).

Do you have any specified starting and ending points? No, that's not a must.

Or can you start and stop on any point, and you need to find the endpoints that give you the shortest total path length? That's pretty much what I am searching for, and I was hoping to reach that through my rules.

I am familiar with the Travelling Salesman Problem and it is indeed similar to what I am looking for, but this starts one step ahead: How to create the lines for the salesman according to certain rules? I.e. the rules have higher priority than the shortest distance.

Thanks so much again!

[Image Analyst]

I've not really had to use the TSP myself but there are tons of posts on it. What you want is the TSP solution but for every possible pairing of start and end points. Then you want to take the shortest TSP solution. Do a search on tag:TSP and see what you can find.

[Image Analyst]

I think this should do what you want: http://www.mathworks.com/help/optim/examples/travelling-salesman-problem.html?s_tid=srchtitle

[Walter Roberson]

The problem has not yet been clearly enough defined to code.

If the selected locations form a grid or subset of a grid, then the task becomes easier to set up.

A key question is whether any of the Hamiltonian paths are acceptable, or if the shortest such path is required. The shortest such path takes a lot more work.

https://www.hindawi.com/journals/jam/2012/475087/

Answer 2

[Image Analyst]

There are a number of ways to attach the traveling salesman problem. See the Mathworks suggestions: http://www.mathworks.com/search/site_search.html?q=traveling+salesman&term=traveling+salesman&c[]=entire_site_en

Answer 3

[Walter Roberson]

This is mostly just a traveling salesman problem with just not adding in edges that are too long. The only thing that is not normal is checking that the lines do not cross: typically they do not cross (because uncrossing them would usually lower the energy.) If the example you show, if you only provide vertices to the nodes that are adjacent horizontally and vertically then you cannot end up with a crossing line.

[Jay Muller]

Thank you both very much. I'll have a closer look into the TSP, as you say, maybe I "just" need to modify the algorithm a bit, e.g. by deleting unwanted lines.

[Walter Roberson]

If you have a grid like you show in the examples, you cannot end up with unwanted lines provided you only populate edges between nodes that are horizontally or vertically connected. If the nodes are not on a regular grid then there could potentially be circumstances under which the edges crossed with a path that was otherwise valid.