geospatialpoint-in-polygonjts

Point in polygon is not performant using IndexedPointInAreaLocator and STRTree (JTS Topology Suite)

private List<ZoneDefinitionCacheMemory> findZonesForShipPosition(Point point) {
    List<Object> zoneDefinitionCacheHits = new ArrayList<>();
    strTree.query(point.getEnvelopeInternal(), zoneDefinitionCacheHits::add);
    return zoneDefinitionCacheHits.stream()
        .filter(ZoneDefinitionCacheMemory.class::isInstance)
        .map(ZoneDefinitionCacheMemory.class::cast)
        .filter(zoneDefinition -> isPointInsideGeometry(point, zoneDefinition.getGeometry()))
        .toList();
}

private boolean isPointInsideGeometry(Point point, Geometry geometry) {
    PointOnGeometryLocator pointOnGeometryLocator = new IndexedPointInAreaLocator(geometry);
    int location = pointOnGeometryLocator.locate(point.getCoordinate());
    boolean isInside = location == Location.INTERIOR;
    return isInside;
}

I am using the above code to search the point in the polygon, I am inserting all the polygons and multipolygons into the strTree before querying it, and also I am using IndexedPointInAreaLocator to have an additional filter on the top of STR Tree to validate whether given point really lies in the geometry or not.

Also, my polygons are quite big means some polygons have almost 1.6m points in them.

So with this implementation, I am facing performance issues for one point this approach is taking at least 100ms to complete, which is not expected for my use case.

What can be the issue here? or any suggestion to make it fast somehow.

My Use case: I'll be getting lots of points to detect whether they lie inside or outside in the given geometries (polygons and multi-polygons)

I have tried using a polygon.contains(point) predicate but it is taking more time than the IndexedPointInAreaLocator approach.

Solution

  • If your polygons are big (in the sense they cover a large area) or oddly shaped. Then, subdividing them may improve the index performance, remember that the index works on the bounding box of the polygon to start with to save doing an expensive point in polygon test. If a point falls into many bounding boxes but only one polygon the index won't help much.

    This blog post by Paul Ramsey discusses this in the PostGIS context but the underlying implementation is the same here. This answer will help you divide up your polygons (as I don't think JTS has a subdivide method).

    You may also benefit from using GeoTools around the JTS code as that would allow you to switch to using a PostGIS or GeoPackage database with their built in indexes or an easier indexed in memory store.