<html dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style id="owaParaStyle" type="text/css">P {margin-top:0;margin-bottom:0;}</style>
</head>
<body ocsi="0" fpstyle="1" style="word-wrap:break-word">
<div style="direction: ltr;font-family: Verdana;color: #000000;font-size: 10pt;">
Hi Jaqueline. <br>
<br>
<br>
I used igraph as the routing system. As I said, I made a distiction between a 'vertices' [points in your routes that do pertain to a junction between paths or are the starting/end point of a polyline], and 'nodes' [the remaining points in your paths]. With
this approach you may obtain a graph-equivalent of your spatial network, and use igraph to obtain the optimal between-vertex routes, which serve as a base to later obtain the optimal between-nodes routes [not in igraph, so you'll need to do this yourself]<br>
<br>
The approach I used is not highly different from the one you may see at Barry's example [although I did not know about it until yesterday]. I also had to do a good set of functions [map points -e.g. your raster- into polyline chainages, automatically create
the topology and vertices in a way not very dissimilar to what Barry shows but considering a certain tolerance between crosses...] , and think carefully about the approach for our specific requirements.<br>
<br>
Thus I used the igraph routes as input information to another function which actually obtains the along-network distance between points [nodes existing in the polylines, or the mapping of your raster into your network]. You'll find that the optimal between-vertex
routes provide you with a few alternatives to obtain between-nodes distances. But it is not difficult to create a function to select from these few alternatives, using as input the ouput you may have from igraph.<br>
<br>
In fact, I found it convenient to create what I called a SpatialGraph S4 object, which basically is composed of a @v slot with vertices information [a SPatialPointsDataFrame, with at least a number of predefined fields ---i.e. named columns---], an @e slot
[a SpatialLinesDataFrame] with the topology information in the corresponding data.frame, and including all the source polylines, a @graph slot containing the equivalent igraph object, and something else...<br>
<br>
Basically, if you are using OpenStreetMap, you may find that the hints I mentioned may be highly useful to avoid, as I said, an enormous igraph-equivalent of your
<br>
network, to obtain the optimal routes.<br>
<br>
FYI, you also have igraph and GEOS as C libraries, but obviously you'll loose the speed/facilities of setting up the system in R. Perhaps you could build your prototype in R, and then decide about the operational strategy?<br>
<div><br>
Cheers,<br>
Javier<br>
<br>
<div style="font-family:Tahoma; font-size:13px">
<div style="font-family:Tahoma; font-size:13px">
<div style="font-family:Tahoma; font-size:13px">
<div style="font-family:Tahoma; font-size:13px"><font size="2"><span style="font-size:10pt"><font face="Verdana"><br>
---<br>
Dr. Javier Garc<font size="2">í</font>a-Pintado<br>
National Centre for Earth Observation (ESSC-NCEO)<br>
Data Assimilation Research Centre<br>
<font size="2">School of Math<font size="2">e</font>matic<font size="2">al and Physical Sciences</font></font><br>
University of Reading<br>
Tel: +44(0)1183787722<br>
j.garcia-pintado@reading.ac.uk<br>
http://www.nceo.ac.uk/<br>
</font><br>
</span></font></div>
</div>
</div>
</div>
</div>
<div style="font-family: Times New Roman; color: #000000; font-size: 16px">
<hr tabindex="-1">
<div style="direction: ltr;" id="divRpF263351"><font color="#000000" face="Tahoma" size="2"><b>From:</b> Jacqueline Schweizer [jacqueline.schweizer@wuestundpartner.com]<br>
<b>Sent:</b> 29 January 2014 08:03<br>
<b>To:</b> Javier Garcia-Pintado<br>
<b>Cc:</b> Barry Rowlingson; Rafael Wüest; r-sig-geo@r-project.org<br>
<b>Subject:</b> Re: [R-sig-Geo] Calculate distance along a path<br>
</font><br>
</div>
<div></div>
<div>Good morning,
<div><br>
</div>
<div>Thank you very much for the inputs!</div>
<div><br>
</div>
<div>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. </div>
<div><br>
</div>
<div>But if I understand correctly, Javier, you did this all without using a routing-system?</div>
<div>I will dive into it very soon, might come back to you guys when I encounter some difficulties :)</div>
<div><br>
</div>
<div>Thank you again,</div>
<div><br>
</div>
<div>Jacqueline extense</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
<div>
<div>Am 28.01.2014 um 18:31 schrieb Javier Garcia-Pintado <<a href="mailto:j.garcia-pintado@reading.ac.uk" target="_blank">j.garcia-pintado@reading.ac.uk</a>>:</div>
<br class="Apple-interchange-newline">
<blockquote type="cite">Hi Jaqueline,<br>
<br>
Yes, as Barry indicates this can be well done in R. I've done that [using rgeos, sp & igraph] for assimilation of sparse selected satellite info [your busses] into 2d flood models in braided systems [your cells] which follow a predefined skeleton of connectivity
(e.g. urban areas of a network of rural channels).<br>
<br>
<blockquote type="cite">From my experience the only I can add on top of what has been said is that building a graph including all points in the polylines you may have, may result in a daunting graph. I believe it will result in a much faster calculation to
assume that each polyline is an edge bounded by two vertices [junctions between polylines], and embed the length of the polyline into the properties of the associated graph to obtain the shortest path between vertices as a preprocessing step. If, e.g. we say
a node is any point in a polyline, and a vertex is just the starting or ending point of that polyline, then we would be further interested in getting between-node distances.<br>
</blockquote>
<br>
Specifically, you can obtain the nearest point in a path to your cells [this nearest point is not neccesarily an explicit node in an existing polyline, but could faill in a segment between consecutive points]. Then, this nearest point has a "chainage" [a along-polyline
distance from its starting vertex]. You can use that chainage to obtain the shortest along-network distance for points wich are not vertices in the graph, by using the previously igraph-calculated between-vertex shortest distances, and adding the "chainages".
Note in this step there is a little more to think about the 4 or 5 possible shortest paths, but surely you'll come across it when you reach this point.<br>
<br>
I've done all this in R and works beautifully.<br>
<br>
Good luck,<br>
<br>
Javier<br>
<br>
---<br>
Dr. Javier García-Pintado<br>
National Centre for Earth Observation (ESSC-NCEO)<br>
Data Assimilation Research Centre<br>
School of Mathematical and Physical Sciences<br>
University of Reading<br>
Tel: +44(0)1183787722<br>
<a href="mailto:j.garcia-pintado@reading.ac.uk" target="_blank">j.garcia-pintado@reading.ac.uk</a><br>
http://www.nceo.ac.uk/<br>
<br>
<br>
________________________________________<br>
From: r-sig-geo-bounces@r-project.org [r-sig-geo-bounces@r-project.org] on behalf of Barry Rowlingson [b.rowlingson@lancaster.ac.uk]<br>
Sent: 28 January 2014 16:23<br>
To: Rafael Wüest<br>
Cc: r-sig-geo@r-project.org<br>
Subject: Re: [R-sig-Geo] Calculate distance along a path<br>
<br>
On Tue, Jan 28, 2014 at 3:14 PM, Rafael Wüest <rafael.wueest@gmail.com> wrote:<br>
<blockquote type="cite">http://rpubs.com/geospacedman/routing<br>
<br>
could be a start...<br>
<br>
Hope this helps,<br>
</blockquote>
<br>
Looks good.<br>
<br>
You need three data sets - a line data set of the paths, a point data<br>
set of the bus stops, and a point data set of the grids.<br>
<br>
From line data set you build a topological graph with distance as edge weights.<br>
<br>
Snap the bus stop and grid centres to the nearest point on a path.<br>
<br>
Do shortest-distance path search between grid cells and bus stops.<br>
<br>
It would be useful to know how complex your path network is, and how<br>
many grid cells you want to do, and how many bus stops you have. But<br>
in principle all the functions are there in the igraph, sp, and rgeos<br>
packages (and a few others).<br>
<br>
R is a construction kit....<br>
<br>
Barry<br>
<br>
_______________________________________________<br>
R-sig-Geo mailing list<br>
R-sig-Geo@r-project.org<br>
https://stat.ethz.ch/mailman/listinfo/r-sig-geo<br>
<br>
_______________________________________________<br>
R-sig-Geo mailing list<br>
R-sig-Geo@r-project.org<br>
https://stat.ethz.ch/mailman/listinfo/r-sig-geo<br>
</blockquote>
</div>
<br>
<div>
<div style="color:rgb(0,0,0); font-family:Helvetica; font-size:medium; font-style:normal; font-variant:normal; font-weight:normal; letter-spacing:normal; line-height:normal; orphans:2; text-indent:0px; text-transform:none; white-space:normal; widows:2; word-spacing:0px; word-wrap:break-word">
<div style="color:rgb(0,0,0); font-style:normal; font-variant:normal; font-weight:normal; letter-spacing:normal; orphans:2; text-indent:0px; text-transform:none; white-space:normal; widows:2; word-spacing:0px; word-wrap:break-word">
<span class="Apple-style-span" style="border-collapse:separate; border-spacing:0px">
<div style="word-wrap:break-word"><span class="Apple-style-span" style="border-collapse:separate; color:rgb(0,0,0); font-style:normal; font-variant:normal; font-weight:normal; letter-spacing:normal; orphans:2; text-indent:0px; text-transform:none; white-space:normal; widows:2; word-spacing:0px; border-spacing:0px">
<div><font face="Verdana, Geneva, Arial, sans-serif"><span style="line-height:18px"><br class="Apple-interchange-newline">
<br class="Apple-interchange-newline">
</span></font>–––––––––––––––––––––––––––––––––––</div>
<div style="font-family:Helvetica; font-size:medium; line-height:normal"><span style="font-family:Verdana,Geneva,Arial,sans-serif; font-size:12px; background-color:rgb(255,255,255)">Jacqueline Schweizer </span></div>
<div style="font-family:Helvetica; font-size:medium; line-height:normal">
<div id="_mcePaste" style="font-family:Verdana,Geneva,Arial,sans-serif; font-size:12px; background-color:rgb(255,255,255)">
MSc Geographie </div>
<div id="_mcePaste" style="font-family:Verdana,Geneva,Arial,sans-serif; font-size:12px; background-color:rgb(255,255,255)">
Consultant</div>
<div id="_mcePaste" style="font-family:Verdana,Geneva,Arial,sans-serif; font-size:12px; background-color:rgb(255,255,255)">
<div>Tel. +41 44 289 9016</div>
<div><a href="mailto:jacqueline.schweizer@wuestundpartner.com" style="font-family:Helvetica; font-size:medium" target="_blank">jacqueline.schweizer@wuestundpartner.com</a></div>
</div>
<div id="_mcePaste" style="font-family:Verdana,Geneva,Arial,sans-serif; font-size:12px; background-color:rgb(255,255,255)">
<br>
</div>
<div style="font-family:Verdana,Geneva,Arial,sans-serif; font-size:12px; background-color:rgb(255,255,255)">
Wüest & Partner AG</div>
<div id="_mcePaste" style="font-family:Verdana,Geneva,Arial,sans-serif; font-size:12px; background-color:rgb(255,255,255)">
Alte Börse ▪ Bleicherweg 5 ▪ CH-8001 Zürich</div>
<div id="_mcePaste" style="font-family:Verdana,Geneva,Arial,sans-serif; font-size:12px; background-color:rgb(255,255,255)">
Tel. +41 44 289 90 00 ▪ Fax +41 44 289 90 01</div>
</div>
<div style="font-family:Helvetica; font-size:medium; line-height:normal"><a href="http://www.wuestundpartner.com/" target="_blank">www.wuestundpartner.com</a><br>
–––––––––––––––––––––––––––––––––––</div>
<div style="font-family:Helvetica; font-size:medium; line-height:normal"><br>
</div>
</span></div>
</span></div>
</div>
<br class="Apple-interchange-newline" style="color:rgb(0,0,0); font-family:Helvetica; font-size:medium; font-style:normal; font-variant:normal; font-weight:normal; letter-spacing:normal; line-height:normal; orphans:2; text-indent:0px; text-transform:none; white-space:normal; widows:2; word-spacing:0px">
<br class="Apple-interchange-newline">
</div>
<br>
</div>
<br>
<br>
<font color="#808080">Disclaimer<br>
<br>
Die in dieser E-Mail enthaltenen Informationen sind für den ausschliesslichen Gebrauch durch den Empfänger bestimmt und beinhalten möglicherweise vertrauliche oder gesetzlich geschützte Daten. Wenn Sie diese E-Mail irrtümlicherweise erhalten haben, bitten wir
Sie, uns dies so schnell wie möglich per E-Mail oder telefonisch mitzuteilen und die E-Mail sowie allfällige Anhänge dazu unter Ausschluss jeder Reproduktion zu löschen. Besten Dank.<br>
<br>
This message is intended only for the recipient and may contain confidential and privileged information. Please notify the sender immediately by e-mail or telephone if you have received it in error and delete the message and any attachments from your system.
If your are not the intended recipient, retention, dissemination, distribution, copying or otherwise making use of this message is strictly prohibited.
<br>
<br>
Les informations contenues dans cet email sont réservées à l'usage exclusif du destinataire et peuvent contenir des informations confidentielles ou protégées par la loi. Si vous recevez cet email par erreur, veuillez s'il vous plaît nous en informer au plus
tôt, par téléphone ou par courriel. Dans tous les cas toute reproduction est interdite et l'email doit être effacé. En vous remerciant.</font><br>
</div>
</div>
</div>
</body>
</html>