Skip to main content
  • EN
I want to find the shortest path between points over a network (streetwork). The points have to be projected on the network.

 

The workbench is quit simple I think: read the from- and to-nodes, use FromToBuilder and the ShortestPathFinder (in which I activate From-To and Network Snapping with a certain tolerance) and go.

 

Below a screenhot of the result:

 

 

- red lines and text being the network (with ID's as a label)

 

- green circles being the end-nodes of the network segments

 

- cyan points and text are the from-nodes, with the blue circle representing the tolerance used for snapping

 

- the big red dot is the to-node

 

For none of the From-nodes a shortest route is been found. The straight orange lines represent the unused output from ShortestPathFinder. I expected though that e.g. node 1078 would be projected on segment 257, so the shortest path for that node would be 257-352-240. Or for nodes 1355 and 1390 a shortest path 284-240.

 

Is my expectation wrong or do I just don't understand the working of the shortest path finder?
Hi,

 

 

The snapping type of the "From-To and Network Snapping" parameter in the ShortestPathFinder seems to be "End Point Snapping". i.e., in your screenshot, 1237 and 1253 points would be snapped to the closest network nodes (green points), but others including the red big point will not be snapped to anywhere. Therefore, the ShortestPathFinder will not generate the shortest paths for the From-To lines.

 

 

If you are trying to create the shortest paths between the closest points which are located on the network lines for each FROM/TO-point, you will have to add network nodes that represent those points beforehand. In that case, the NeighborFinder and the PointOnLineOverlayer might help you. 

 

 

Takashi
Hi Takashi,

 

 

Thanks for the quick and clear response. I'll work that out, i.e. first project the points on the network-segments, insert the projection as a (new) network-node and then run the ShortestPathFinder.

 

Regards.

 

 

Hans
Hi,

 

I've added a NeighborFinder with the option "Insert Vertex On Base Feature" activated. So I expected that a vertex on the projected location would be insterted. But it's not.

 

 

 

The orange points are adresses projected on the network, which looks good (although 355 (bottom right corner) seems not to be projected). And though specified to find only 1 Neighbour, it sometimes find more than 1 (e.g. 237).

 

According this last observation: maybe it looks for 1 Neighbour per section found with the tolerance specified, but then I would assume that for adress 78 it would find 2 Neighbours as well (which it doesn't).
The "Insert Vertex On Base Feature" option inserts vertices onto the Base lines, but the vertices will not be nodes of the network. You should create network nodes with splitting the lines at the closest points.

 

 

My intention was this procedure.

 

(1) Add a NeighborFinder; send the end points of the FROM/TO lines to the Base port; send the network lines to the Candidate port.

 

(2) Create the closest points on the lines based on _closest_candidate_x and _closest_candidate_y of the Matched features, using a VertexCreator (Mode Replace with Point).

 

(3) Add a PointOnLineOverlayer; send the points to the Point port; send the original network lines to the Line port.

 

(4) You can then use the lines from the Line port of the PointOnLinOverlayer to find shortest paths.
Still can't get it to work. I think I'm close by though. The only problem (I think) is to split the segment on the location of the projection of the from-node to the network (this is _closest_base_x and _closest_base_y from the NeighborFinder. Maybe you like to take a look at the workbench so far:

 

https://dl.dropboxusercontent.com/u/24062076/ShortestPath/ADRESSES.xlsx

 

https://dl.dropboxusercontent.com/u/24062076/ShortestPath/Network.dgn

 

https://dl.dropboxusercontent.com/u/24062076/ShortestPath/ShortestPath.fmw

 

There you can see the FROM-NODES are projected correctly on the network, so now what's left is to split the network there in order to make the ShortestPathFinder to work.

 

Some other strange things:

 

- there's no projection of the FROM-NODES 1423, 1430 and 1355

 

- FROM-NODE1237 gets 3 projections!!
This is a workspace example including your datasets. (https://drive.google.com/file/d/0B0ufVP2t0eApblE4V3R6c25EVjQ/view?usp=sharing)

 

 

To insert nodes that are closest to ADDRESS/SCHOOL points onto the network, use the points as Base features in the NeighborFinder and apply the PointOnLineOverlayer after creating the closest points.
There are some address points those distances from the closest road line are greater than the specified tolerance. If you need to find shortest paths for every point regardless of tolerance, you can create From-To lines based on the inserted nodes.

 

An example is here. (https://drive.google.com/file/d/0B0ufVP2t0eApVlNZVndyRHZ0Wjg/view?usp=sharing)
Hi

 

 

On a general basis I would recommend passing your data through a Snapper (Vertex or Segment snapping) and then a TopologyBuilder before using the ShortestPathFinder. This will assure that your data is properly connected and usable by the ShortestPathFinder.

 

 

You might even want to snap your From-To line using the Snapper rather than using the snapping function in the ShortestPathFinder, for some reason this seems to work better for me.

 

 

David
Hi Takashi,

 

 

Solved I think. You helped me a lot.

 

Thanks very much!!

 

 

Hans
Hi David,

 

 

Thanks for your comment. I'd found out that a topologycally correct network is crucial to be used with the ShortestPathFinder, so it's a good tip to upfront check/clean the network.

 

Thanks!!

 

 

Hans

Reply


Community Stats

30,108
Posts
114,295
Replies
37,745
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.