Many to Many Point Connector

Hi,

I am trying to create From-To lines from every point in a shapefile to every other point. I have 45,989 points, so (in theory) each point should have 45,988 lines coming off and attaching to every other point.

I have attempted to use both the FromToBuilder and the LineBuilder, but neither seem to work.

Does anyone have any ideas that might work?

Thanks

Page 1 / 1

Hi @fchu274, I think this workflow should work theoretically. The point is CROSS JOIN in the SQL Query statement.

SQL Query: Enumerate 2-Permutation

select s.*, e._x, e._y
from node_s as s cross join node_e as e
on s._count <> e._count

SQL Query: Enumerate 2-Combination

select s.*, e._x, e._y
from node_s as s cross join node_e as e
on s._count < e._count

However, the number of 2-Permutation is about 2.1 billion (45,989 x 45,988), or the number of 2-Combination is about 1 billion (45,989 x 45,988 / 2). I suppose that the translation requires huge disk space for FME temporary folder, and I'm not sure if it could complete translation within your allowable time period.

Hi @fchu274

Here is a workspace that can do what you're after:

In this workspace I'm Sampling to prove it works (and process 25 points rather than 13597).

The NeighborFinder takes each input point, and compares it to every other point. This creates a list with an element for every point it finds (expressed as base which is the original point, and candidates which are the other points).

The ListExploder takes each list element and creates a new feature from it, giving you one feature for every possible line that you could have.

The VertexCreator is ADDING a point, making a line using the original point (base x and base y) and adding a point from the candidate x and y, which makes a line. Resulting in this:

I've uploaded the workspace so you can see the transformer parameters.

The source dataset is taken from the FME Training data, the addresses.gdb

manytomanypointconnector.fmw

Processing 13597 points, creating 339925 lines took 1 minute 36.3 seconds (sending to Inspector).

Hi @takashi,

This workflow worked perfectly for both of the options you suggested.

I attempted to use your workflow on a subset of 17 points. The 2-Permutation output 272 lines (17 x 16), and the 2-Combination output 136 lines (17 x 16 / 2), just as you suggested it would!

Thanks for your help!

Hi @jlutherthomas,

This also worked very well!

Thank you for uploading the workspace, this makes it very clear to see the logic.

Using a subset, this workflow output 272 lines (17 x 16), the same as Takashi's 2-Permutation method.

Many thanks!

Hi @jlutherthomas,

This also worked very well!

Thank you for uploading the workspace, this makes it very clear to see the logic.

Using a subset, this workflow output 272 lines (17 x 16), the same as Takashi's 2-Permutation method.

Many thanks!

It would be interesting to see how the performance differs between the two different methods using your larger dataset.

I can attempt to run both methods to see the differences in performance. Although both methods worked very quickly on a (very) small subset, the results might be useful for others in the future.

Hi @fchu274

Here is a workspace that can do what you're after:

In this workspace I'm Sampling to prove it works (and process 25 points rather than 13597).

The ListExploder takes each list element and creates a new feature from it, giving you one feature for every possible line that you could have.

The VertexCreator is ADDING a point, making a line using the original point (base x and base y) and adding a point from the candidate x and y, which makes a line. Resulting in this:

I've uploaded the workspace so you can see the transformer parameters.

The source dataset is taken from the FME Training data, the addresses.gdb

manytomanypointconnector.fmw

Processing 13597 points, creating 339925 lines took 1 minute 36.3 seconds (sending to Inspector).

> Processing 13597 points, creating 339925

339,925 = 13,597 x 25. You will have to change the Number of Neighbors to Find parameter if you intend to create every From-To line from the 13,597 points.

BTW, the NeighborFinder collects every candidate for each base if you leave the Number of Neighbors to Find blank or set 0. Surprisingly it works fine even if you leave the Maximum Distance blank, although the help says "A value must be specified for at least one of the Number of Neighbors to Find and Maximum Distance parameters."

If you would discuss about the performance, also try Python ;)

# PythonCaller Script Example: Enumerate 2-Permutations of All Points
# Assuming that the input feature has a point geometry.
from fmeobjects import FMELine
class FromToLineCreator1(object):
    def __init__(self):
        self.features = s]
        
    def input(self, feature):
        self.features.append(feature)
        
    def close(self):
        coords = tfeat.getCoordinate(0) for feat in self.features]
        rangeK = range(len(coords))
        for i, feat in enumerate(self.features):
            for k in rangeK:
                if k != i:
                    feat.setGeometry(FMELine(                    self.pyoutput(feat)

# PythonCaller Script Example: Enumerate 2-Combinations of All Points
# Assuming that the input feature has a point geometry.
from fmeobjects import FMELine
class FromToLineCreator2(object):
    def __init__(self):
        self.features = P]
        
    def input(self, feature):
        self.features.append(feature)
        
    def close(self):
        coords = rfeat.getCoordinate(0) for feat in self.features]
        for i, feat in enumerate(self.features>:-1]):
            for c in coords/i+1:]:
                feat.setGeometry(FMELine(�coords�i], c]))
                self.pyoutput(feat)

Very helpful solutions! Thank you! @Takashi Iijima @jlutherthomas @fchu274

Reply

Community Stats

Reply

Community Stats

Sign up

An FME Account is required to contribute

Login to the community

An FME Account is required to contribute

Scanning file for viruses.

This file cannot be downloaded