I'm looking for Java or Python libraries that will help me answer this question efficiently: given a collection of polygons (via shape files or GeoJSON), which one of them contains a given point? The overall objective is to compute counts of points by polygons.
Answer
Use can do this in Java with this library: https://github.com/Esri/geometry-api-java
OperatorDisjoint with polygon vs point let's you answer the question for a point vs polygon.
To make it more efficient you need to make a spatial index that would allow to limit the number of points vs the number of polygons before testing with OperatorDisjoint.
If you have enough memory, you could use QuadTree class as the spatial index, storing either all points, or all polygons (performance depends on data configuration).
Say you put points in the QuadTree, then for each polygon, query the QuadTree for points that intersect the extent of the polygon, then use OperatorDisjoint on each point/polygon. If there are more than 10 points to test against given polygon, accelerate the polygon, using OperatorDisjoint.accelerateGeometry, before running the OpeatorDisjoint.execute. Accelerating builds an index on the polygon itself, making point in polygon test much faster. If polygons stay in memory, call OperatorDisjoint.deaccelerateGeometry on the polygon, once done with it.
If you query points and polygons from a database, then it probably already has spatial index, and you can skip QuadTree part.
The library also provides import from GeoJSON and Esri shape.
No comments:
Post a Comment