[GRASS-user] Re: [GRASSLIST:1098] v.net.steiner

[Markus Neteler]

On Wed, Jun 14, 2006 at 08:52:37AM -0400, M S wrote:
> nice document!  this is great stuff.

Thanks. And note that data elaboration with the current
6.1-CVS is even easier...
 
> The v.net.steiner seems to be a realistic functional model by using an
> existing (road) network to know what physical routes it can follow to the
> given terminals.  this looks fantastic, and i cant wait to build some test
> data.

There should be a roads_net in spearfish6.0 which was recently
updated by Radim.
 
> is there a function (raster or vector) that would allow for building the
> network links/lines by inputting only the points without regards to an
> existing (road) network?  (using something like the minimum spanning tree
> example below).  This function would be great as a first cut in network
> analysis.

You could use v.hull and then v.type to make it lines or use
v.extract to only extract the boundaries, then v.type for
boundaries -> lines. (untested)

> the page below illustrates the minimum spanning tree, but if i understand
> right, just nodes are inputted.  then the algorithm does at a minimum 3
> things 1) identifies clusters of sites 2) builds the links to connect the
> clusters to each other, and 3) then finds from each cluster, the nearest
> point to other clusters.
> http://www.cs.sunysb.edu/~algorith/files/minimum-spanning-tree.shtml<http://www.cs.sunysb.edu/%7Ealgorith/files/minimum-spanning-tree.shtml>
> 
> i dont think the v.net.steiner function does what the steiner-tree function
> below illustrates, because the GRASS version uses an existing (road) network
> to realistically model the existing pathways (nice implementation!).

Kudos to Roberto Micarelli and Radim.

>  This was the steiner tree example from the same site.
> http://www.cs.sunysb.edu/~algorith/files/steiner-tree.shtml
> I'm working with a Network Engineer on using GRASS to solve the network
> analysis problems.  Using the NON-GRASS steiner tree (from example above)
> wont work becuase as it goes to build the links, but connects lines to
> lines, rather than given nodes.  in the network implementaion this would be
> a mid-span junction, or splicing the fiber at this junction to connect the
> lines.  the minimum spanning tree is more applicable.  However, i suspect
> that the GRASS minimum steiner tree is the most applicable and realistic
> model/function.

It would be great to have some examples online, for
 http://grass.itc.it/applications/index.php

> The GRASS minimum steiner tree is a realistic functional model that uses
> real network data in conjunction with the terminals.  this seems like a
> great deployment of the steiner tree in conjunction with consideration to
> the existing network such as roads.  I cant wait to have some fun with GRASS
> and give this a whirl!
> 
> as usual, keep up the great work, and thanks to everyone who makes GRASS GIS
> be all it can be!  feels great to find a GIS like this one which is fun to
> work with, and has such community invovlement.  truely a great environmant
> that makes GIS fun (again for me).

Welcome!

Markus

> 
> On 6/14/06, Markus Neteler <neteler at itc.it> wrote:
> >
> >M S wrote on 06/14/2006 03:13 AM:
> >
> >> The input parameter seems to be terminals.  Can they be points?
> >
> >They can be points (nodes) which have to be connected to the network.
> >You may take a look at:
> >http://mpa.itc.it/corso_dit2004/grass04_4_vector_network_neteler.pdf
> >slide 19
> >
> >Markus
> >
> >_______________________________________________
> >grassuser mailing list
> >grassuser at grass.itc.it
> >http://grass.itc.it/mailman/listinfo/grassuser
> >

-- 
Markus Neteler     <neteler itc it>       http://mpa.itc.it
ITC-irst -  Centro per la Ricerca Scientifica e Tecnologica
MPBA - Predictive Models for Biol. & Environ. Data Analysis
Via Sommarive, 18        -       38050 Povo (Trento), Italy