[R-sig-Geo] Calculate distance along a path

[Roger Bivand]

On Wed, 29 Jan 2014, Javier Garcia-Pintado wrote:

> Hi Barry.
>
> Thanks! Very good input!
>
> I completely agree. They need to think about their specific 
> requirements. In our case we needed to know the distance from any 
> location to all "buses" (out satellite info), for our data assimilation 
> problems.
>
> Jaqueline,
> I also dont know about any published function in R to obtain the closest 
> point [be it a node or in the middle of a segment] in a 
> SpatialLinesDataFrame to a given point/s, but it could be out there.

maptools::snapPointsToLines by Germán Carrillo - please use SVN 
revision 279 from R-Forge until the next maptools release.

library(sp)
library(rgeos)
l1 <- readWKT("LINESTRING(0 0, 1 1)")
set.seed(1)
pts <- SpatialPoints(cbind(runif(5), runif(5)))
plot(l1, axes=TRUE)
points(pts)
text(coordinates(pts), labels=row.names(pts), pos=4)
library(maptools)
res <- snapPointsToLines(pts, l1)
points(res, pch=16, col="red")
text(coordinates(res), labels=row.names(res), pos=4, col="red")

Roger


> FYI, the function I had to build for this relies on rotations of the 
> segments. Note for many intermediate steps you may store results in 
> binary matrices, and then access them later as required.
>
> Cheers,
> Javier
>
> ---
> Dr. Javier García-Pintado
> National Centre for Earth Observation (ESSC-NCEO)
> Data Assimilation Research Centre
> School of Mathematical and Physical Sciences
> University of Reading
> Tel: +44(0)1183787722
> j.garcia-pintado at reading.ac.uk
> http://www.nceo.ac.uk/
>
>
> ________________________________________
> 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
>

-- 
Roger Bivand
Department of Economics, Norwegian School of Economics,
Helleveien 30, N-5045 Bergen, Norway.
voice: +47 55 95 93 55; fax +47 55 95 95 43
e-mail: Roger.Bivand at nhh.no