Skip to main content
Solved

Connecting multiple points by shortest lines possible ?


lifalin2016
Contributor
Forum|alt.badge.img+29

I have a large number of points, which I would like to join by simple lines (point-to-point), minimizing the overall summed length of the generated lines. There's no preferred path, but all points must be connected to each other by a single network of lines.

My output just needs to be a set of simple lines.

Do anyone have an idea on how to accomplish that, other than grinding it out in a PythonCaller ?

Cheers

Lars I

Best answer by jkr_wrk

nielsgerrits wrote:

What is a large number of points? 10? 1000? 1.000.000? I think I got it to work with 100 points in 4 iterations, 8 iterations with a 1000. My loop-fu is a bit under developed.

100

1000

Because i realy like the effect this question makes on a random dataset i made the custom transformer that does what you want.

 

Give this transformer a set of points and the output will be a single network with many lines. See my PointConnectorShortestDistance Custom Transformer.

 

View original
Did this help you find an answer to your question?

14 replies

david_r
Evangelist
  • September 11, 2020

Sounds much like the travelling salesman problem, there may be some hints here:

https://www.safe.com/blog/2016/11/fmeevangelist158/


lifalin2016
Contributor
Forum|alt.badge.img+29
  • Author
  • Contributor
  • September 11, 2020
david_r wrote:

Sounds much like the travelling salesman problem, there may be some hints here:

https://www.safe.com/blog/2016/11/fmeevangelist158/

It's NOT a travelling salesman problem, as the points just need to be connected, not visited in any sort of order. A single point may even connect to multiple other points, if they are closest together.


lifalin2016
Contributor
Forum|alt.badge.img+29
  • Author
  • Contributor
  • September 11, 2020

Here's a simplistic sketch to illustrate my problem:

2020-09-11 11_35_09-Window


caracadrian
Contributor
Forum|alt.badge.img+22
  • Contributor
  • September 11, 2020
lifalin2016 wrote:

Here's a simplistic sketch to illustrate my problem:

2020-09-11 11_35_09-Window

Just use a neighbour finder than draw a line from the candidate coordinates to the base coordinates


anhphuongt
Forum|alt.badge.img
  • September 14, 2020

There is a LineBuilder for that. You just need to input the points and FME will create a Line in the order they enter.

https://www.safe.com/transformers/line-builder/


lifalin2016
Contributor
Forum|alt.badge.img+29
  • Author
  • Contributor
  • September 15, 2020
anhphuongt wrote:

There is a LineBuilder for that. You just need to input the points and FME will create a Line in the order they enter.

https://www.safe.com/transformers/line-builder/

No, LineBuilder will just connect all input points as they are entered/sorted into a single polyline. I do not know the order in advance, and a single point may be connected to 3+ other points, as per my illustration above.


lifalin2016
Contributor
Forum|alt.badge.img+29
  • Author
  • Contributor
  • September 15, 2020
caracadrian wrote:

Just use a neighbour finder than draw a line from the candidate coordinates to the base coordinates

Unfortunately that only solves part of my problem. I need all points to be connected, even those that are not immidiate neighbours. I end up with something like this, that's far from my intent (as per my drawing above):

2020-09-15 08_11_15-Start


nielsgerrits
VIP
Forum|alt.badge.img+52

What is a large number of points? 10? 1000? 1.000.000? I think I got it to work with 100 points in 4 iterations, 8 iterations with a 1000. My loop-fu is a bit under developed.

100

1000


lifalin2016
Contributor
Forum|alt.badge.img+29
  • Author
  • Contributor
  • September 15, 2020
nielsgerrits wrote:

What is a large number of points? 10? 1000? 1.000.000? I think I got it to work with 100 points in 4 iterations, 8 iterations with a 1000. My loop-fu is a bit under developed.

100

1000

Iterations of doing what? The amount is tens of thousands, maybe more.


nielsgerrits
VIP
Forum|alt.badge.img+52
nielsgerrits wrote:

What is a large number of points? 10? 1000? 1.000.000? I think I got it to work with 100 points in 4 iterations, 8 iterations with a 1000. My loop-fu is a bit under developed.

100

1000

What I did:

  • Find unique shortest lines between points (Neighborfinder Candidates Only).
  • Find clusters (lines already connecting)
  • Find shortest unique lines between clusters and add these to previous results.
  • Iterate through this until only one cluster remains.

Using a sample set of 100.000 points it took 35 minutes and 9 iterations.

In an earlier version I had some "donuts", this is now fixed. I know the iteration stopper does not work, but I'm done for today.

100000


jkr_wrk
Influencer
Forum|alt.badge.img+28
  • September 16, 2020
nielsgerrits wrote:

What I did:

  • Find unique shortest lines between points (Neighborfinder Candidates Only).
  • Find clusters (lines already connecting)
  • Find shortest unique lines between clusters and add these to previous results.
  • Iterate through this until only one cluster remains.

Using a sample set of 100.000 points it took 35 minutes and 9 iterations.

In an earlier version I had some "donuts", this is now fixed. I know the iteration stopper does not work, but I'm done for today.

100000

You could write the result down to a file and run this like a workspaceRunner (over and over). And stop the workspacerunner when there is one giant networkTopology.


jkr_wrk
Influencer
Forum|alt.badge.img+28
  • Best Answer
  • September 21, 2020
nielsgerrits wrote:

What is a large number of points? 10? 1000? 1.000.000? I think I got it to work with 100 points in 4 iterations, 8 iterations with a 1000. My loop-fu is a bit under developed.

100

1000

Because i realy like the effect this question makes on a random dataset i made the custom transformer that does what you want.

 

Give this transformer a set of points and the output will be a single network with many lines. See my PointConnectorShortestDistance Custom Transformer.

 


lifalin2016
Contributor
Forum|alt.badge.img+29
  • Author
  • Contributor
  • September 22, 2020
jkr_da wrote:

Because i realy like the effect this question makes on a random dataset i made the custom transformer that does what you want.

 

Give this transformer a set of points and the output will be a single network with many lines. See my PointConnectorShortestDistance Custom Transformer.

 

This is brilliant. I didn't expect it to be solveable using only standard transformers, and in a simple package like this, but I stand corrected.

Thank you for providing your solution.

Yes, sometimes the output of a process resembles pure art.


polomayo
Forum|alt.badge.img
  • November 7, 2024
lifalin2016 wrote:
jkr_da wrote:

Because i realy like the effect this question makes on a random dataset i made the custom transformer that does what you want.

 

Give this transformer a set of points and the output will be a single network with many lines. See my PointConnectorShortestDistance Custom Transformer.

 

This is brilliant. I didn't expect it to be solveable using only standard transformers, and in a simple package like this, but I stand corrected.

Thank you for providing your solution.

Yes, sometimes the output of a process resembles pure art.

Hello I hope this finds you all well! How do I use this custom transformer? 


Reply


Cookie policy

We use cookies to enhance and personalize your experience. If you accept you agree to our full cookie policy. Learn more about our cookies.

 
Cookie settings