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
Sounds much like the travelling salesman problem, there may be some hints here:
https://www.safe.com/blog/2016/11/fmeevangelist158/
Sounds much like the travelling salesman problem, there may be some hints here:
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.
Here's a simplistic sketch to illustrate my problem:
Here's a simplistic sketch to illustrate my problem:
Just use a neighbour finder than draw a line from the candidate coordinates to the base coordinates
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/
There is a LineBuilder for that. You just need to input the points and FME will create a Line in the order they enter.
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.
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):
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.
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.
Iterations of doing what? The amount is tens of thousands, maybe more.
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.
What I did:
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.
What I did:
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.
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.
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.
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.
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.
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?