# Given a collection of polygons, how do you find which one contains a given point? Java or Python

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. – yanes Dec 2 '15 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 Fairhurst Dec 2 '15 at 0:19
• @RichardFairhurst thanks for the pointers! Unfortunately, I'm not using any GIS tools, just plain Python or Java. – YakovK Dec 2 '15 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. – YakovK Dec 2 '15 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 – Cyrille Dec 2 '15 at 1:03

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