Re: [jts-devel] Efficient searching - point in list of polygons
Merging into one index *might* produce better performance - you'd have to try it and see. Using userData to store ancillary data (like cost) is a reasonable approach. Alternatively, the objects that are entered into the spatial index don't have to be Geometries - they can be any Object as long as it can provide an Envelope for its extent. So you could store custom Feature objects which contain a Geometry and some ancillary data. Im a bit surprised that PreparedGeometry isn't making any performance difference - but it's possible that the difference is not enough to be worth bothering about. If only a few points are being compared against any individual polygon, the overhead of building the PreparedGeometry would swamp any gain from caching. Another option - don't use Geometry.intersects() for your predicate, but use SimplePointInAreaLocator. Or, you could use IndexedPointInAreaLocator, but this would only be worth doing if you cached the index object (saving it either in the custom object you are storing in the spatial index, or in an external map) Dorrington, Albert wrote: I needed to upgrade our jts.jar from the 1.8 version to 1.10. I tried using the PreparedGeometry/PreparePolygon classes to see if there was any noticable change in performance, but the numbers looked about the same for each run. The problem I think I'm starting to run into tho, is I am not encountering more overhead from the profiling tool, than I am gaining from the code optimizations, so I'm no longer getting completely accurate timing results. For instance it takes about 45 seconds for the routine to run while being profiles, and about 2 seconds to run normally. I think we may need to alter our design approach in order to gain some more performance. From what I've been reading about the Geometry class, I'm thinking instead of maintaining four different layers, that we could use the Geometry's setUserData() method to store our 'cost' values for the layer and merge all polygon's as geometry objects, into one index. Maybe the prepared geometry approach would work better with that? Not sure, very new to JTS at this point :) -Original Message- 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 ___ 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
Re: [jts-devel] Efficient searching - point in list of polygons
Dorrington, Albert wrote:
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.
You might want to construct a geometry index that can be used to speed
up point-in-polygon tests. JTS has R-trees and Quadtrees.
protected double calculateCost(Point point) {
ret = costValue;
for (Polygon polygon : polygons ) {
if (point.intersects(polygon)) {
ret = 0;
break;
}
}
return ret;
}
The code would look something like:
protected double calculateCost(Point point) {
final Envelope searchEnvelope = new Envelope(point):
for (final Object o : spatialIndex.query(searchEnvelope)) {
final Polygon p = (Polygon)o;
if (point.intersects(p) {
return 0;
}
}
return costValue;
}
where spatialIndex is something like:
final SpatialIndex spatialIndex = new STRTree();
for (final Polygon p : polygons) {
spatialIndex.insert(p);
}
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Efficient searching - point in list of polygons
Tuure Laurinolli wrote:
Dorrington, Albert wrote:
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.
You might want to construct a geometry index that can be used to speed
up point-in-polygon tests.
JTS has R-trees and Quadtrees.
protected double calculateCost(Point point) {
ret = costValue;
for (Polygon polygon : polygons ) {
if (point.intersects(polygon)) {
ret = 0;
break;
}
}
return ret;
}
The code would look something like:
protected double calculateCost(Point point) {
final Envelope searchEnvelope = new Envelope(point):
for (final Object o : spatialIndex.query(searchEnvelope)) {
final Polygon p = (Polygon)o;
if (point.intersects(p) {
return 0;
}
}
return costValue;
}
where spatialIndex is something like:
final SpatialIndex spatialIndex = new STRTree(); for (final Polygon p :
polygons) {
spatialIndex.insert(p);
}
I adapted your suggestion and reran the code through the profiler.
The run time for the calls to the calculateCost() method went from
46.4 seconds to 2.79 seconds!
I had to run it a couple of times before I believed it ;-)
Going to go back and add this to the other search areas as well.
Very impressive, Thanks!
- Al
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Efficient searching - point in list of polygons
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
Re: [jts-devel] Efficient searching - point in list of polygons
I needed to upgrade our jts.jar from the 1.8 version to 1.10. I tried using the PreparedGeometry/PreparePolygon classes to see if there was any noticable change in performance, but the numbers looked about the same for each run. The problem I think I'm starting to run into tho, is I am not encountering more overhead from the profiling tool, than I am gaining from the code optimizations, so I'm no longer getting completely accurate timing results. For instance it takes about 45 seconds for the routine to run while being profiles, and about 2 seconds to run normally. I think we may need to alter our design approach in order to gain some more performance. From what I've been reading about the Geometry class, I'm thinking instead of maintaining four different layers, that we could use the Geometry's setUserData() method to store our 'cost' values for the layer and merge all polygon's as geometry objects, into one index. Maybe the prepared geometry approach would work better with that? Not sure, very new to JTS at this point :) -Original Message- 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 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] Efficient searching - point in list of polygons
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
