Efficient searching - point in list of polygons

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Efficient searching - point in list of polygons

Dorrington, Albert
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
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Efficient searching - point in list of polygons

Tuure Laurinolli
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
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Efficient searching - point in list of polygons

Dorrington, Albert
 

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
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Efficient searching - point in list of polygons

Martin Davis
In reply to this post by Dorrington, Albert
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
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>  

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Efficient searching - point in list of polygons

Dorrington, Albert
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
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Efficient searching - point in list of polygons

Martin Davis
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.

I"m 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
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>
>  

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Loading...