# 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
```