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
[email protected]
http://lists.refractions.net/mailman/listinfo/jts-devel
_______________________________________________
jts-devel mailing list
[email protected]
http://lists.refractions.net/mailman/listinfo/jts-devel
_______________________________________________
jts-devel mailing list
[email protected]
http://lists.refractions.net/mailman/listinfo/jts-devel
