As you have now experienced, the biggest speedup you will find comes
from using spatial indexes.
You may also find that using PreparedGeometry helps to reduce the time
even further, since it avoids recomputing topology for the input
polygons. To do this, store a PreparedGeometry in the spatial index,
rather than the original Polygons.
Please let the list know how this works out if you try it - this is
potentially of interest to lots of people.
Martin
Dorrington, Albert wrote:
Hello everyone,
I am involved with a project that is using the JTS package (currently
1.8) to implement some path finding algorithms.
As currently implemented, we have several layers, each of which
contains a List of Polygon objects. Our search algorithm
looks to see if our current location (a Point object) intersects with
any of the Polygons defined in each layer/list, if it does, a cost
associated with that intersection is returned.
Initially our code was rather inefficient, considering that once the
list of polygons is defined, it does not change for the duration
of our search.
For example most layers are implemented like this:
protected double calculateCost(Point point) {
ret = costValue;
for (Polygon polygon : polygons ) {
if (point.intersects(polygon)) {
ret = 0;
break;
}
}
return ret;
}
I refined this, trying to merge all of the polygons once, into a
Geometry class, so that we could query the intersections against the
geomerty collection, instead.
protected double calculateCost(Point point) {
if ( ! loaded ) {
loaded = true;
geom = new Geometry[ polygons.size()];
polygons.toArray(geom);
geoFact = geom[0].getFactory();
geomColl = geoFact.createGeometryCollection(geom);
union = geomColl.buffer(0);
buffColl = union.buffer(1);
}
if ( buffColl.intersects(point) ) { return 0; }
else { return costValue; }
}
These 'calculateCost' methods are being called hundreds of thousands,
if not millions of times in our application, so any refinement we can
get would be worthwhile.
The biggest problem I have had, is not being able to locate sources of
docmentation (other than the Javadoc) and examples. So I'm really not
sure what else is available within the API, although I've been reading
that the PreparedGeometry classes in 1.9/1.10 of JTS may help to
improve our performance (if I can understand how to use them) ;-)
If anyone can provide some suggestions/advice, I'd be greatful.
Thanks!
Al Dorrington
Embedded S/W Engineer Sr
Aerospace Simulation Software Development
Lockheed Martin, Systems Integration-Owego
------------------------------------------------------------------------
_______________________________________________
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
_______________________________________________
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
