Janda,
Some more information about my point #2 below. If you look at
SegmentStringDissolver you will see an implementation which uses a
simple Map with a comparator based on a canonical orientation of a
Coordinate array to detect identical edges (up to orientation). This is
more recent code than the EdgeList code. I think this approach offers
the best performance, and could be ported into the EdgeList class. If
you tackle this, let me know how it turns out.
Martin
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
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
_______________________________________________
jts-devel mailing list
[email protected]
http://lists.refractions.net/mailman/listinfo/jts-devel
