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
