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.
-
Welcome to the GIS SE site. Please have a look at our tour page, it gives you ideas on how to best benefit from the site. Homework style questions are not encouraged. Please give an example of methods you've tried and any errors you encountered.– yanesCommented Dec 2, 2015 at 0:10
-
What software are you using for GIS? If this is ArcGIS, the Spatial Join geoprocessing tool is the most efficient for a simple point count. If you have a complex set of rules for counting the points than arcpy has geometry methods for intersect, touches, etc that can be looped to get a count..– Richard FairhurstCommented Dec 2, 2015 at 0:19
-
@RichardFairhurst thanks for the pointers! Unfortunately, I'm not using any GIS tools, just plain Python or Java.– YakovKCommented Dec 2, 2015 at 0:54
-
@yanes Thanks for the hints! Unfortunately, it's not a HW question. I'm trying to deal with 20B points and roughly 5K polygons at work. Perhaps, this is not the right forum to ask such questions, sorry.– YakovKCommented Dec 2, 2015 at 0:55
-
Check out this question for a start: programmers.stackexchange.com/questions/299775/… Here's a python solution: en.wikipedia.org/wiki/Even%E2%80%93odd_rule– CyrilleCommented Dec 2, 2015 at 1:03
|
Show 6 more comments
1 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.
