TransWikia.com

Pairwise shortest distance between points in a road network

Geographic Information Systems Asked by cassianord on May 29, 2021

1. Problem

I have the coordinates for over 5000 points (cities) that lie over a road shape file, as partially illustrated below:

enter image description here

I’m working on R, and I need to find the shortest distance between all pairs of points along the roads.

2. What I’ve already tried, without success:

  • stplanr package: had a problem converting the full road shape file to a SpatialLinesNetwork object ("non finite line lengths");
  • osrm package: can’t compute all distance pairs (over 30 million) due to server restrictions (up to 10k pairs).

3. Sample data

I provide a sample data here: https://github.com/cassianord/example_data/blob/main/example_data.7z?raw=true

One Answer

At least one row of your roads is causing this error when SpatialLinesNetwork tries to get its length:

> SpatialLinesLengths(l[65403,])
Error in FUN(X[[i]], ...) : non-finite line lengths

This row appears to have zero length, which is messing up the length calculation when it is using lat-long coordinates:

> l[65403,]
class       : SpatialLinesDataFrame 
features    : 1 
extent      : -41.98302, -41.98302, -15.25437, -15.25437  (xmin, xmax, ymin, ymax)

I suspect a divide-by-zero somewhere when working out the distance on a sphere by lat-long.

The adjacent segments are fine:

> SpatialLinesLengths(l[65402,])
[1] 1.813751
> SpatialLinesLengths(l[65404,])
[1] 1.802447

You can trick it into not using lat-long coordinates - there is an option but I think having a CRS on the lines overrides this anyway. So set the CRS to nothing:

> proj4string(l) = ""

And then I can build a spatial lines network without errors:

> ln = SpatialLinesNetwork(l)
> 

But that will give you a spatial network based on euclidean lat-long distance which might not be very valid.

Or you could project to an appropriate cartesian grid system for your data and use that.

Alternatively you could try an eliminate these rows from your data, but in some cases it seems to be caused by zero-length segments within road segments, which is hard to track down.

Correct answer by Spacedman on May 29, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP