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;
   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) {

jts-devel mailing list

Reply via email to