Martin,
I have implemented a fix to EdgeList to improve how it finds equal
edges. This uses the OrientedCoordinateArray approach from the noding
package. It's a worthwhile improvement - a buffer test that I have goes
from 19 s down to 5 s.
This is a non-linear algorithm, so you may see even more relative
improvement in your case.
I'd still like to see your test case, and hear about whether this fix
helps you out. The updated file is attached (and will be in CVS soon)
Good catch!
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
/*
* The JTS Topology Suite is a collection of Java classes that
* implement the fundamental operations required to validate a given
* geo-spatial data set to a known topological specification.
*
* Copyright (C) 2001 Vivid Solutions
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
* For more information, contact:
*
* Vivid Solutions
* Suite #1A
* 2328 Government Street
* Victoria BC V8T 5G5
* Canada
*
* (250)385-6040
* www.vividsolutions.com
*/
package com.vividsolutions.jts.geomgraph;
import java.io.PrintStream;
import java.util.*;
import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.index.SpatialIndex;
import com.vividsolutions.jts.index.quadtree.Quadtree;
import com.vividsolutions.jts.noding.OrientedCoordinateArray;
import com.vividsolutions.jts.noding.SegmentString;
/**
* A EdgeList is a list of Edges. It supports locating edges
* that are pointwise equals to a target edge.
* @version 1.7
*/
public class EdgeList
{
private List edges = new ArrayList();
/**
* An index of the edges, for fast lookup.
*
* a Quadtree is used, because this index needs to be dynamic
* (e.g. allow insertions after queries).
* An alternative would be to use an ordered set based on the values
* of the edge coordinates
*
*/
// private SpatialIndex index = new Quadtree();
private Map ocaMap = new TreeMap();
public EdgeList() {
}
/**
* Insert an edge unless it is already in the list
*/
public void add(Edge e)
{
edges.add(e);
// index.insert(e.getEnvelope(), e);
OrientedCoordinateArray oca = new
OrientedCoordinateArray(e.getCoordinates());
ocaMap.put(oca, e);
}
public void addAll(Collection edgeColl)
{
for (Iterator i = edgeColl.iterator(); i.hasNext(); ) {
add((Edge) i.next());
}
}
public List getEdges() { return edges; }
// <FIX> fast lookup for edges
/**
* If there is an edge equal to e already in the list, return it.
* Otherwise return null.
* @return equal edge, if there is one already in the list
* null otherwise
*/
public Edge findEqualEdge(Edge e)
{
OrientedCoordinateArray oca = new
OrientedCoordinateArray(e.getCoordinates());
// will return null if no edge matches
Edge matchEdge = (Edge) ocaMap.get(oca);
return matchEdge;
}
/*
public Edge OLDfindEqualEdge(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;
}
*/
public Iterator iterator() { return edges.iterator(); }
public Edge get(int i) { return (Edge) edges.get(i); }
/**
* If the edge e is already in the list, return its index.
* @return index, if e is already in the list
* -1 otherwise
*/
public int findEdgeIndex(Edge e)
{
for (int i = 0; i < edges.size(); i++) {
if ( ((Edge) edges.get(i)).equals(e) ) return i;
}
return -1;
}
public void print(PrintStream out)
{
out.print("MULTILINESTRING ( ");
for (int j = 0; j < edges.size(); j++) {
Edge e = (Edge) edges.get(j);
if (j > 0) out.print(",");
out.print("(");
Coordinate[] pts = e.getCoordinates();
for (int i = 0; i < pts.length; i++) {
if (i > 0) out.print(",");
out.print(pts[i].x + " " + pts[i].y);
}
out.println(")");
}
out.print(") ");
}
}
_______________________________________________
jts-devel mailing list
[email protected]
http://lists.refractions.net/mailman/listinfo/jts-devel
