Martin,
I would love it if you could add the option for a visitor for both kinds
(planar and geometry) of graph to short circuit the query. This can have
drastic improvements for certain algorithms.
On a slightly different topic, one of the other things I've done as well
is implement a CreateArrayVisitor which is designed to be used by other
visitors. You could then have an OverlapsVisitor which would take
another visitor as a parameter. The OverlapsVisitor would invoke the
other visitor if the item geometry overlapped. If you used the
CreateArrayVisitor you would get an array back just of those items which
overlapped.
Paul
*Paul Austin*
/President/CEO/
Revolution Systems Inc.
+1 (604) 288-4304 x201
www.revolsys.com <http://www.revolsys.com>
Martin Davis wrote:
Janda,
Yes, I'm definitely interested in your improvements. It certainly
sounds like this is a good area to try and improve.
A couple of comments:
- Have you tested your enhancement on a case which shows clear
improvement in the timing? I realize that the profiling is a good
indication that this is a hotspot, but the ultimate test is to have a
geometry case which runs faster.
- What do you think about possibly replacing the QuadTree lookup with
an index based on the values of the coordinates of the edges? This
is mentioned in the comments in the EdgeList class. The index would
have to index both the forward direction of the edge and the backward
direction, to ensure that all possible matches are found. It seems
like this might be even faster.
- If the Quadtree is used, it's definitely a good idea to allow
ItemVisitor to short-circuit the query. I think the easiest way to do
this is to allow it to return a boolean, which would be true if the
query was complete.
Look forward to seeing the results of your timings. Can you post your
test cases & code as well?
Martin
Janda Martin wrote:
Hallo everybody,
I'm new to this list. I would like to use JTS in my project. I tried
BufferOp on polygon with 4000 (cca 30second) and 80 000 (totaly
unusable) coordinates. It's tooooo slow.
I found that there are many allocations and I find some hot spots
with my profiler.
I found that ~85% of BufferOp is spent in
geomgraph.EdgeList.findEqualEdge. It visites spatial index (Quadtree)
to generate ArrayList of Edges and then iterates through them to find
equal edge.
I didn't profile modified JTS. But I believe that the modification
can improve performance.
I would like to help you improve JTS. If you are interesting in my
solution please let me know and I will test it in my profiler and i
will send you the final version.
I would like to cooperate with you in JTS improvement. Mainly in
performance.
Martin JANDA [EMAIL PROTECTED]
CRC Data spol. s .r o.
Prague, Czech Republic
http://www.crcdata.cz (only in Czech)
PS I'm sorry. I'm not used to speak or write in english.
I have two solutions:
a) modify method findEqualEdge in EdgeList
ORIGINAL:
public Edge findEqualEdge(Edge e)
{
Collection testEdges = index.query(e.getEnvelope());
for (Iterator i = testEdges.iterator(); i.hasNext(); ) {
Edge testEdge = (Edge) i.next();
if (testEdge.equals(e) ) return testEdge;
}
return null;
}
MODIFIED:
// This method uses own ItemVisitor
// it doesn't allocate ArrayList
// there is no iteration through list
public Edge findEqualEdge(Edge e)
{
EdgeItemVisitor visitor = new EdgeItemVisitor(e);
index.query(e.getEnvelope(), visitor);
return visitor.getFoundEdge();
}
// inner class of EdgeList
private static class EdgeItemVisitor implements ItemVisitor {
private final Edge edge;
private Edge foundEdge = null;
public EdgeItemVisitor(final Edge edge) {
this.edge = edge;
}
public void visitItem(Object object) {
if(foundEdge == null && object instanceof Edge &&
edge.equals(object)) foundEdge = (Edge) object;
}
public Edge getFoundEdge() {
return foundEdge;
}
}
b) user solution a) with modified SpatialIndex.query that can be
terminated when the Edge is found. It is necessary to extends
SpatialIndex to support termination of query
_______________________________________________
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
