I have a huge dataset (millions of points) and a irregular grid (quadtree) in shapefile format and I need to convert the points in countes over the grid provided. I managed to make it work, using shapely Polygon.contains and a naive double-loop that scales as O(n**2).

Obviously, the script is very slow. It takes already very long on thousands of points. Is there any other way to greatly reduce running time, without writing a lot more code?

What's the typical procedure to convert so many points to a grid system, and how is it called, so that I can search further information about it?

  • 1
    I'd say it is converting both inputs to rasters and perform zonal ( polygons) statistics
    – FelixIP
    Sep 7, 2015 at 5:48

1 Answer 1


Rather than checking every point against every polygon in your grid, you can use a spatial index to speed things up. The spatial index allows you to search for polygons with a bounding box that intersects the query bounding box. In your particular case, as the polygons in your quadtree will be square and your search for points, you don't even need to call contains.

There is some example code using Shapely and Rtree in this answer:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.