[R-sig-Geo] shortest path

[Barry Rowlingson]

On Fri, Aug 31, 2012 at 9:39 AM, Mathieu Rajerison
<mathieu.rajerison at gmail.com> wrote:
> Hi,
>
>
> I've got a question which is graph-related.
>
> Let's suppose I have a linear network.
>
> I cut the lines at the intersections and get some vertexes and edges
> connecting them
>
> How can I turn this into a graph that I could treat in igraph?
>
> I've put a line sample as attached file if any geohacker is interested in
> facing the challenge ;)

 For complex geometry you'd probably want to feed this to one of the
GRASS modules that builds topologies. I have a hacky method which I'll
outline...

 * read lines using readOGR
 * use package rgeos to intersect the lines with themselves
 * that gives you a single object containing line segments that are
only two points.
 * create a label for each point based on the x and y coordinate,
suitably rounded
 * that gives you a node label for each point. hence the graph.

I think this will work for data that is relatively clean. It won't fix
certain data errors, for example if a point from one line is very
close to the middle of another line, since no intersection will be
found. Other topology build solutions might notice that point X is
1e-10 from the line from A to B and create an extra node there, thus
'snapping' X to that location and causing a new node in the graph...

 If I didn't have to be on a train in three hours I'd code this up...

Barry