Question

Shortest distance from all points to all points over a network layer

  • 29 September 2017
  • 10 replies
  • 41 views
S

I am trying to find shortest distance from all points to all other points in my dataset.

I have used a topology builder and a network topology calculator to verify my network data.

I don't get any features coming through the 'Path' output port. All of them exit via unused and no path found.

I have attached a screenshot of my workspace.

10 replies

danilo_fme
Rank
Userlevel 4
Badge +30

Hi @sahilbhouraskar,

Could you send a sample your data Reader ( Bearers_Route and Exchange_buffered_Location ) ?

 

Thanks,

Danilo

S

Hi @sahilbhouraskar,

Could you send a sample your data Reader ( Bearers_Route and Exchange_buffered_Location ) ?

 

Thanks,

Danilo

Hi Danilo,

 

 

Thanks for the prompt reply. You can access the files here.

 

 

https://drive.google.com/drive/folders/0B1z_tW09rn9ASFdNZV82TUpBejA

 

 

Both are in the same co-ordinate system- EPSG2193

 

 

owen
Badge +1

Hi @sahilbhouraskar I have had success with the shortestpathfinder when snapping the from-to points to the network first (neighbourfinder > vertexcreator (replace with closestcandidate x/y), and splitting the network at these points (pointonlineoverlayer). Owen

takashi
Rank
Userlevel 2
Badge +17

The NetworkTopologyCalculator detected two networks from your data. Naturally the ShortestPathFinder cannot find shortest paths for the from-to lines that connect between a node in the 1st network and a node in the 2nd network.

However, in my quick test using some from-to lines created from your data, the ShortestPathFinder found the shortest paths for the lines except ones connecting between the two different networks. There doesn't seem to be any problem in the ShortestPathFinder behavior.

danilo_fme
Rank
Userlevel 4
Badge +30
Hi Danilo,

 

 

Thanks for the prompt reply. You can access the files here.

 

 

https://drive.google.com/drive/folders/0B1z_tW09rn9ASFdNZV82TUpBejA

 

 

Both are in the same co-ordinate system- EPSG2193

 

 

Hi @sahilbhouraskar,

 

Thanks your files shared. I see that @takashi and @owen did give great answers about your case. Thanks you guys :)

 

 

Danilo
S

The NetworkTopologyCalculator detected two networks from your data. Naturally the ShortestPathFinder cannot find shortest paths for the from-to lines that connect between a node in the 1st network and a node in the 2nd network.

However, in my quick test using some from-to lines created from your data, the ShortestPathFinder found the shortest paths for the lines except ones connecting between the two different networks. There doesn't seem to be any problem in the ShortestPathFinder behavior.

Hi Takashi, Thanks for the assistance. I still have the same problem where the shortest path is not calculated. Did you have to snap the points to the network first like @owen suggested?

 

Also would it be possible to share the work bench that you created? I would be interested in seeing how it is different to one I created. Again, appreciate the effort to answer my questions.

 

takashi
Rank
Userlevel 2
Badge +17

I've modified your workspace on these points.

  • Replaced the source datasets with the sample data you've shared in this thread.
  • Inserted a Tester immediately after the ListExploder, in order to reduce the number of from-to lines for testing and also discard the from-to lines with no length (i.e. the from node is equal to the to node).
  • Removed the first VertexCreator and the FromToBuilder. You can just add the coordinates of TO point to FROM point to create a from-to line with a single VertexCreator, in this case.
  • Added some Inspectors to check the result.

I've never touched other transformers.

Result:

The blue and red indicate the two different networks which have been identified by the NetworkTopologyCalculator. The gray indicates the from-to lines for which the ShotestPathFinder didn't find shortest paths (i.e. the features output via the NoPath port).

There are these two types of the NoPath lines.

  • The FROM node and TO node belong to different networks (from blue to red, or from red to blue). No shortest paths can be found for them anyway, unless you modify the network lines in order to make a single connected network.
  • One or both end node of the from-to line has not been snapped to any network node. You could fix this if you surely snap every from-to point to the closest network node, as @owen suggested. This screenshot illustrates the method.

S

I've modified your workspace on these points.

  • Replaced the source datasets with the sample data you've shared in this thread.
  • Inserted a Tester immediately after the ListExploder, in order to reduce the number of from-to lines for testing and also discard the from-to lines with no length (i.e. the from node is equal to the to node).
  • Removed the first VertexCreator and the FromToBuilder. You can just add the coordinates of TO point to FROM point to create a from-to line with a single VertexCreator, in this case.
  • Added some Inspectors to check the result.

I've never touched other transformers.

Result:

The blue and red indicate the two different networks which have been identified by the NetworkTopologyCalculator. The gray indicates the from-to lines for which the ShotestPathFinder didn't find shortest paths (i.e. the features output via the NoPath port).

There are these two types of the NoPath lines.

  • The FROM node and TO node belong to different networks (from blue to red, or from red to blue). No shortest paths can be found for them anyway, unless you modify the network lines in order to make a single connected network.
  • One or both end node of the from-to line has not been snapped to any network node. You could fix this if you surely snap every from-to point to the closest network node, as @owen suggested. This screenshot illustrates the method.

Worked like a charm.

 

Thanks for the assistance Takashi.
bruceharold
Rank
Badge +16

Hi, your problem looks like an OD Cost Matrix one, not out of the box, maybe an Ideas candidate?

fmelizard
Rank
Userlevel 4
Badge +13

Hi @sahilbhouraskar If you have 380 points to connect to each other then you should want 72,010 From-To lines. (n * n-1)/2 I've added that to your workspace and also used a PointOnLineOverlayer as suggested by @owen. It uses the same tolerance as that in the ShortestPathFinder via a published parameter.

It's a known limitation that the ShortestPathFinder only snaps to the endpoints of network features. An enhancement request to also do segment snapping has been filed as PR43172.

Reply


Community Stats

28,669
Posts
109,357
Replies
36,531
Members
Terms & ConditionsCookie settings
A product of
Safe Software respectfully acknowledges that we live, learn and work on the traditional and unceded territories of the Kwantlen, Katzie, and Semiahmoo First Nations.