Question

Find the nearest neighbor of a nearest neighbor of a nearest neighbor of...


Badge +1

Hello there! I have spent, no joke, over 5 entire work days trying to achieve this result, and....... I still haven't. Considering it's not actually a priority in the slightest and that I clearly can't leave well enough alone, I'm finally giving in and joined this community to see if one of y'all can do it for me (in much less time)...

I am trying to create... a network of neighboring points. The input is a shapefile of buildings' center points (with a starting point designated via parameter); the desired output is these same points, with an attribute putting them in an order that is essentially:

A) Point A

B) The nearest point to point A

C) The nearest point to point B, excluding A

D) The nearest point to point C, excluding A and B

E) The nearest point to point D, excluding A, B, and C

...and so on. Find the nearest neighbors, with exclusion -- the nearest point that is not already the nearest point to one earlier up the chain.

I actually made a looping custom transformer that did almost exactly this for me -- however, it leaned heavily on the NeighborFinder transformer, which is a blocking transformer and became way too slow way too quickly. I know how I could make this work using python, but all my ideas for that also require more flexibility in looping than I can get with FME (because I'd want to loop through all the features more than once, but not in a way that python inside a looping transformer would do....)

Even as I type this I'm having more ideas of approaches to try, but, again, I've spent way too much time on this and I have to give up. If anyone else has any thoughts on how to do this with the fewest manual steps within the process.... I'd love to hear 'em! Thanks! :)


10 replies

Userlevel 4
Badge +13

Hi @jdmiller95 How similar is your question to https://knowledge.safe.com/questions/45800/finding-neighbours-with-1-to-1-relationship.html ? Are the points in a particular order already? Could the nearest point to point A be point B? Is the overall goal to pair points together or to create a single network of every point, where point A is the seed point?

Userlevel 4

To try and understand the question, I did a small prototype using a PythonCaller. Given 20 random points and the blue point as a starting point, it returned the following "topology":

Does this fit your requirement?

Badge +1

To try and understand the question, I did a small prototype using a PythonCaller. Given 20 random points and the blue point as a starting point, it returned the following "topology":

Does this fit your requirement?

Yes!! I absolutely recognize that it will cause connections between points that appear comically farther apart than expected... but given the data I'm working with, it's highly like that that is not a bit deal. It does look that you've created exactly what I've been desperately trying to...!

Userlevel 4

We can use scipy to do something very similar to the NeighborhoodFinder, making it possible to "customize" the behavior and loop over the list of nodes while eliminating previous matches. Here's the code from the PythonCaller:

from scipy.spatial import distanceimport fmeobjectsdef get_closest_node_index(node, nodes):    return distance.cdist([node], nodes).argmin()class CreatePointTopology():        def __init__(self):        self.nodes = []            def input(self, feature):        node = feature.getCoordinate(0)        self.nodes.append(node)            def close(self):        current_node = self.nodes.pop(0)        while len(self.nodes) >= 1:            output = fmeobjects.FMEFeature()            idx = get_closest_node_index(current_node, self.nodes)            output.addCoordinate(current_node[0], current_node[1])            output.addCoordinate(self.nodes[idx][0], self.nodes[idx][1])            current_node = self.nodes.pop(idx)            self.pyoutput(output)

The main assumptions are that all points are 2D and that the first point will be the starting point. You will want to make sure that you have at least two input points.

I've also attached a test workspace (FME 2019.0.2.0) to show the code in context: createpointtopology.fmwt

Userlevel 4
Badge +13

Yes!! I absolutely recognize that it will cause connections between points that appear comically farther apart than expected... but given the data I'm working with, it's highly like that that is not a bit deal. It does look that you've created exactly what I've been desperately trying to...!

@jdmiller95 Maybe the ShortestPathFinder will suffice? Use the 'By Straight Line Distance (No Network)' cost type. Each point won't necessarily connect to the closest points but they will be shortest overall.

Badge +1

We can use scipy to do something very similar to the NeighborhoodFinder, making it possible to "customize" the behavior and loop over the list of nodes while eliminating previous matches. Here's the code from the PythonCaller:

from scipy.spatial import distanceimport fmeobjectsdef get_closest_node_index(node, nodes):    return distance.cdist([node], nodes).argmin()class CreatePointTopology():        def __init__(self):        self.nodes = []            def input(self, feature):        node = feature.getCoordinate(0)        self.nodes.append(node)            def close(self):        current_node = self.nodes.pop(0)        while len(self.nodes) >= 1:            output = fmeobjects.FMEFeature()            idx = get_closest_node_index(current_node, self.nodes)            output.addCoordinate(current_node[0], current_node[1])            output.addCoordinate(self.nodes[idx][0], self.nodes[idx][1])            current_node = self.nodes.pop(idx)            self.pyoutput(output)

The main assumptions are that all points are 2D and that the first point will be the starting point. You will want to make sure that you have at least two input points.

I've also attached a test workspace (FME 2019.0.2.0) to show the code in context: createpointtopology.fmwt

This is really awesome, thank you!! I'm wondering... is there a way to keep an attribute from the point(s) as attribute(s) of the line connecting them? ie, for my purposes, the ability to document/view that this particular line segment is connecting Adams House and Smith House? (I'd poke at the code to try and figure that out myself...but I'm just so close to my breaking point with brain power towards this project!) 

Userlevel 4

This is really awesome, thank you!! I'm wondering... is there a way to keep an attribute from the point(s) as attribute(s) of the line connecting them? ie, for my purposes, the ability to document/view that this particular line segment is connecting Adams House and Smith House? (I'd poke at the code to try and figure that out myself...but I'm just so close to my breaking point with brain power towards this project!) 

Sure, you can simply add the necessary attributes as dictionary in self.nodes. Example line 14:

my_attr1 = feature.getAttribute('my_attr1')
node_dict = {'node': node, 'my_attr1': my_attr1}
self.nodes.append(node_dict)

Then change the rest of the code accordingly.

Badge +1

Sure, you can simply add the necessary attributes as dictionary in self.nodes. Example line 14:

my_attr1 = feature.getAttribute('my_attr1')
node_dict = {'node': node, 'my_attr1': my_attr1}
self.nodes.append(node_dict)

Then change the rest of the code accordingly.

I hate to admit it....but I have no idea what to change in the rest of the code to make things work with these lines added in :/ turns out I'm not as comfortable with Python as I tend to think, and I just can't seem to sort out what to do with later parts of the code to make sure it's still calling the right part of the dictionary or whatever? Also just because I don't actually understand the rest of the code/what attribute it's calling/etc... would you be able to lend a bit more of a guided hand to getting the attributes added on?

Userlevel 4

Try using the following code in the PythonCaller to retain the point attributes:

from scipy.spatial import distance
import fmeobjects

def get_closest_node_index(node, nodes):
    return distance.cdist([node], nodes).argmin()

class CreatePointTopology():
    
    def __init__(self):
        self.nodes = []
        self.attribs = []
        
    def input(self, feature):
        node = feature.getCoordinate(0)
        self.nodes.append(node)
        attribs = {k:feature.getAttribute(k) for k in feature.getAllAttributeNames() if not k.startswith('fme_')}
        self.attribs.append(attribs)
        
    def close(self):
        from_node = self.nodes.pop(0)
        from_attribs = self.attribs.pop(0)
        while len(self.nodes) >= 1:
            output = fmeobjects.FMEFeature()
            to_node_idx = get_closest_node_index(from_node, self.nodes)
            to_node = self.nodes[to_node_idx]
            to_attribs = self.attribs[to_node_idx]
            for f in from_attribs.keys():
                output.setAttribute('from_'+f, from_attribs[f])
            for t in to_attribs.keys():
                output.setAttribute('to_'+t, to_attribs[t])
            output.addCoordinate(from_node[0], from_node[1])
            output.addCoordinate(to_node[0], to_node[1])
            from_node = self.nodes.pop(to_node_idx)
            from_attribs = self.attribs.pop(to_node_idx)
            self.pyoutput(output)            

Each output segment will retain the point attributes prefixed with either "from_" or "to_", e.g. a segment that goes from a point with attribute X=1 to a point with attribute X=2, will result in a segment with from_X=1 and to_X=2.

If you still want/need to use the LineCombiner, make sure to enable "Generate List" to avoid loosing the output attributes.

Userlevel 4

Try using the following code in the PythonCaller to retain the point attributes:

from scipy.spatial import distance
import fmeobjects

def get_closest_node_index(node, nodes):
    return distance.cdist([node], nodes).argmin()

class CreatePointTopology():
    
    def __init__(self):
        self.nodes = []
        self.attribs = []
        
    def input(self, feature):
        node = feature.getCoordinate(0)
        self.nodes.append(node)
        attribs = {k:feature.getAttribute(k) for k in feature.getAllAttributeNames() if not k.startswith('fme_')}
        self.attribs.append(attribs)
        
    def close(self):
        from_node = self.nodes.pop(0)
        from_attribs = self.attribs.pop(0)
        while len(self.nodes) >= 1:
            output = fmeobjects.FMEFeature()
            to_node_idx = get_closest_node_index(from_node, self.nodes)
            to_node = self.nodes[to_node_idx]
            to_attribs = self.attribs[to_node_idx]
            for f in from_attribs.keys():
                output.setAttribute('from_'+f, from_attribs[f])
            for t in to_attribs.keys():
                output.setAttribute('to_'+t, to_attribs[t])
            output.addCoordinate(from_node[0], from_node[1])
            output.addCoordinate(to_node[0], to_node[1])
            from_node = self.nodes.pop(to_node_idx)
            from_attribs = self.attribs.pop(to_node_idx)
            self.pyoutput(output)            

Each output segment will retain the point attributes prefixed with either "from_" or "to_", e.g. a segment that goes from a point with attribute X=1 to a point with attribute X=2, will result in a segment with from_X=1 and to_X=2.

If you still want/need to use the LineCombiner, make sure to enable "Generate List" to avoid loosing the output attributes.

FME Workspace template for version 2019.1 and up: createpointtopology.fmwt

Reply