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