Calculate distance along a path

________________________________________
From: b.rowlingson at gmail.com [b.rowlingson at gmail.com] on behalf of Barry Rowlingson [b.rowlingson at lancaster.ac.uk]
Sent: 29 January 2014 09:14
To: Jacqueline Schweizer
Cc: Javier Garcia-Pintado; Rafael W?est; r-sig-geo at r-project.org
Subject: Re: [R-sig-Geo] Calculate distance along a path

On Wed, Jan 29, 2014 at 8:03 AM, Jacqueline Schweizer
<jacqueline.schweizer at wuestundpartner.com> wrote:
Good morning,

Thank you very much for the inputs!

As for the amount of stops and scale of the area: eventually I would like to
do this for the whole of Switzerland, probably in a 10m-Grid. That means
there are about 50 Million grid cells. As for the stops, there will be
around 24'000. As for the path-network I plan on using the
OpenStreetMap-Layer for roads and footpath, so that is a fairly  large as
well.

I would definitely look at the `osmar` package which can read
OpenStreetMap vector data and convert it to a graph network. But
yikes, thats going to be a big network and a big grid. Possibly too
big a road network for R to handle unless you have ginormous amounts
of RAM in your machine.

I think Javier's plan is as follows, and its a good one...

You don't do any routing. What you do is construct a graph that
includes path vertices and bus stop vertices. Then for each path
vertex, construct the distance to the nearest bus stop vertex (should
be code for this in igraph). This is done in reverse, by an algorithm
that sets off 'walkers' from each bus stop, marking off the distance
travelled, until two walkers meet up when they stop. Once all the
walkers have met or reached dead ends, the process stops. Now you have
a path network with the distance to the nearest bus stop written on
each path vertex.

[Note no routing is required, this is what's called a `breadth first`
traverse of the graph (essentially at every fork in the road you send
two people off walking and reporting back the distance) as opposed to
a 'depth first' search which is where a single walker keeps going
until the end of the road then backtracks and tries all the forks yet
to be visited.]

Now you have a path network with distances, and you only have to find
the nearest point on the path network for each grid cell, and read off
the distance.

There's some interpolation needed where grid cells are near the centre
of a line segment, and similarly for bus stops so its not totally
straightforward, but should be a lot quicker than 50,000,000 routing
calculations, which will take two days at a rate of 10 routes per
second, assuming you can build the thing in RAM. How much RAM can you
rent for two days from Amazon?

I'm not certain this algorithm exists in igraph or elsewhere for R,
but I do think its a standard distance algorithm. MIght have a look
later.

It will be very useful to know how far the nearest bus stop is when
I'm on top of a mountain in the alps....

Barry

_______________________________________________
R-sig-Geo mailing list
R-sig-Geo at r-project.org
https://stat.ethz.ch/mailman/listinfo/r-sig-geo