Quantcast

Re: Proper construction of a search graph from geometric, > objects

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Proper construction of a search graph from geometric, > objects

Stefan Steiniger
I think Michael Michaud also used JgraphT for his OpeJUMP Plugin:

http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-0.3.jar
http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-src-0.3.zip

but maybe it is already what you meant with JUMP plugin

stefan
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: Proper construction of a search graph from geometric, > objects

michaelm-2
Hi,

I have used JGraphT with JTS for a while and I can say it is *very* fast.
I use it to find nodes of a linear network, degree* of each node, cycles...
When using JTS+JGraphT, I consider linear features as the edges of the
graph and first and last coordinates of their geometry as the nodes. It
may not fit all needs as the graph has no node where features intersect
if intersection point is not already the extremity of those features.

I have to admit that I first tried to do this with pure JTS (avoiding to
add a 500kb jar), but it appeared much more complex to use.
Maybe some convenient methods around PlanarGraph class would have helped
me achieve the same goal in pure JTS, but now, I'm no more sure there
are much benefits working at the geometry level rather than at the
feature level.

My two cents

Michaël

* if you try to use it, note that I just discovered a bug which returns
a degree 4 node at the end of a single looping edge (should be degree 2)

Stefan Steiniger a écrit :

> I think Michael Michaud also used JgraphT for his OpeJUMP Plugin:
>
> http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-0.3.jar
> http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-src-0.3.zip
>
> but maybe it is already what you meant with JUMP plugin
>
> stefan
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>
>

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: Proper construction of a search graph from geometric, > objects

Martin Davis
Michael,

I agree with your experience that it's just as reasonable to work at the
feature level rather than the geometry level.  Graph-based algorithms
are pretty much orthogonal to geometric algorithms, so there's not much
to be gained from having the graph "know" about the geometry.  The one
exception is precisely for planar graphs - in this case, the geometry
implies an ordering of edges around each node, which is important for
various algorithms in JTS.

Perhaps this is why you're seeing JGraphT being faster that JTS?  There
is a cost to computing the edge ordering, of course.

Do you have some details of how JGraphT is easier to use than JTS?  It
would be nice for development if the JTS graph structures were as easy
to use as possible.


Michaël Michaud wrote:

> Hi,
>
> I have used JGraphT with JTS for a while and I can say it is *very* fast.
> I use it to find nodes of a linear network, degree* of each node,
> cycles...
> When using JTS+JGraphT, I consider linear features as the edges of the
> graph and first and last coordinates of their geometry as the nodes.
> It may not fit all needs as the graph has no node where features
> intersect if intersection point is not already the extremity of those
> features.
>
> I have to admit that I first tried to do this with pure JTS (avoiding
> to add a 500kb jar), but it appeared much more complex to use.
> Maybe some convenient methods around PlanarGraph class would have
> helped me achieve the same goal in pure JTS, but now, I'm no more sure
> there are much benefits working at the geometry level rather than at
> the feature level.
>
> My two cents
>
> Michaël
>
> * if you try to use it, note that I just discovered a bug which
> returns a degree 4 node at the end of a single looping edge (should be
> degree 2)
>
> Stefan Steiniger a écrit :
>> I think Michael Michaud also used JgraphT for his OpeJUMP Plugin:
>>
>> http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-0.3.jar
>> http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-src-0.3.zip
>>
>> but maybe it is already what you meant with JUMP plugin
>>
>> stefan
>> _______________________________________________
>> jts-devel mailing list
>> [hidden email]
>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>
>>
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: Proper construction of a search graph from geometric, > objects

michaelm-2
Hi Martin,

> I agree with your experience that it's just as reasonable to work at
> the feature level rather than the geometry level.  Graph-based
> algorithms are pretty much orthogonal to geometric algorithms, so
> there's not much to be gained from having the graph "know" about the
> geometry.  The one exception is precisely for planar graphs - in this
> case, the geometry implies an ordering of edges around each node,
> which is important for various algorithms in JTS.
Sure ! I cannot remember if JGraphT has any code to manage an ordered
list of incident edges, but It probably lack a lot of code to manage
PlanarGraphs as it is needed by a library like JTS.
> Perhaps this is why you're seeing JGraphT being faster that JTS?  
> There is a cost to computing the edge ordering, of course.
Indeed, I wrote it is very fast, but I cannot affirm it is faster than
JTS as I did not perform the same calculation with JTS. I just saw that
computing graphs of large datasets (30000 features) takes only 1 second
(I have a very new corei7) and do not need a lot of memory.
>
> Do you have some details of how JGraphT is easier to use than JTS?  It
> would be nice for development if the JTS graph structures were as easy
> to use as possible.
Here after is a small piece of code showing how I build a simple
weighted graph from a feature collection.
Stefan gave the adresse of the complete source code.
After a graph is built, I can use any algorithm of the JGraphT library,
then go back from the result (generally a set of nodes or a set of
edges) to the underlying features.

Michaël

private static WeightedGraph<INode,FeatureAsEdge>
        add(WeightedGraph<INode,FeatureAsEdge> graph, Collection
features, boolean dim3) {
        Coordinate[] cc;
        for (Iterator it = features.iterator() ; it.hasNext() ; ) {
            Feature f = (Feature)it.next();
            Geometry g = f.getGeometry();
            cc = f.getGeometry().getCoordinates();
            INode node1 = dim3? new Node3D(cc[0]) : new Node2D(cc[0]);
            INode node2 = dim3? new Node3D(cc[cc.length-1]) : new
Node2D(cc[cc.length-1]);
            graph.addVertex(node1);
            graph.addVertex(node2);
            FeatureAsEdge edge = new FeatureAsEdge(f);
            graph.addEdge(node1, node2, edge);
            graph.setEdgeWeight(edge, g.getLength());
        }
        return graph;
    }

>
>
> Michaël Michaud wrote:
>> Hi,
>>
>> I have used JGraphT with JTS for a while and I can say it is *very*
>> fast.
>> I use it to find nodes of a linear network, degree* of each node,
>> cycles...
>> When using JTS+JGraphT, I consider linear features as the edges of
>> the graph and first and last coordinates of their geometry as the
>> nodes. It may not fit all needs as the graph has no node where
>> features intersect if intersection point is not already the extremity
>> of those features.
>>
>> I have to admit that I first tried to do this with pure JTS (avoiding
>> to add a 500kb jar), but it appeared much more complex to use.
>> Maybe some convenient methods around PlanarGraph class would have
>> helped me achieve the same goal in pure JTS, but now, I'm no more
>> sure there are much benefits working at the geometry level rather
>> than at the feature level.
>>
>> My two cents
>>
>> Michaël
>>
>> * if you try to use it, note that I just discovered a bug which
>> returns a degree 4 node at the end of a single looping edge (should
>> be degree 2)
>>
>> Stefan Steiniger a écrit :
>>> I think Michael Michaud also used JgraphT for his OpeJUMP Plugin:
>>>
>>> http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-0.3.jar
>>> http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-src-0.3.zip
>>>
>>> but maybe it is already what you meant with JUMP plugin
>>>
>>> stefan
>>> _______________________________________________
>>> jts-devel mailing list
>>> [hidden email]
>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>
>>>
>>
>> _______________________________________________
>> jts-devel mailing list
>> [hidden email]
>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>
>

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: Proper construction of a search graph from geometric, > objects

Martin Davis
Thanks, Michael.

I'm not sure there's any easy lesson for JTS here - except maybe that
generics are a nice thing to have for graph libraries!

Michaël Michaud wrote:

> Hi Martin,
>
>> I agree with your experience that it's just as reasonable to work at
>> the feature level rather than the geometry level.  Graph-based
>> algorithms are pretty much orthogonal to geometric algorithms, so
>> there's not much to be gained from having the graph "know" about the
>> geometry.  The one exception is precisely for planar graphs - in this
>> case, the geometry implies an ordering of edges around each node,
>> which is important for various algorithms in JTS.
> Sure ! I cannot remember if JGraphT has any code to manage an ordered
> list of incident edges, but It probably lack a lot of code to manage
> PlanarGraphs as it is needed by a library like JTS.
>> Perhaps this is why you're seeing JGraphT being faster that JTS?  
>> There is a cost to computing the edge ordering, of course.
> Indeed, I wrote it is very fast, but I cannot affirm it is faster than
> JTS as I did not perform the same calculation with JTS. I just saw
> that computing graphs of large datasets (30000 features) takes only 1
> second (I have a very new corei7) and do not need a lot of memory.
>>
>> Do you have some details of how JGraphT is easier to use than JTS?  
>> It would be nice for development if the JTS graph structures were as
>> easy to use as possible.
> Here after is a small piece of code showing how I build a simple
> weighted graph from a feature collection.
> Stefan gave the adresse of the complete source code.
> After a graph is built, I can use any algorithm of the JGraphT
> library, then go back from the result (generally a set of nodes or a
> set of edges) to the underlying features.
>
> Michaël
>
> private static WeightedGraph<INode,FeatureAsEdge>
>        add(WeightedGraph<INode,FeatureAsEdge> graph, Collection
> features, boolean dim3) {
>        Coordinate[] cc;
>        for (Iterator it = features.iterator() ; it.hasNext() ; ) {
>            Feature f = (Feature)it.next();
>            Geometry g = f.getGeometry();
>            cc = f.getGeometry().getCoordinates();
>            INode node1 = dim3? new Node3D(cc[0]) : new Node2D(cc[0]);
>            INode node2 = dim3? new Node3D(cc[cc.length-1]) : new
> Node2D(cc[cc.length-1]);
>            graph.addVertex(node1);
>            graph.addVertex(node2);
>            FeatureAsEdge edge = new FeatureAsEdge(f);
>            graph.addEdge(node1, node2, edge);
>            graph.setEdgeWeight(edge, g.getLength());
>        }
>        return graph;
>    }
>

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Loading...