I just finished writing a quadtree spatial index package in pure python which is aimed for GIS use.
Spatial index packages for Python already exist, a popular one being the Rtree package, which comes in both a C and pure-Python variety. In comparison to Rtree indexes however, QuadTree indexes are supposedly preferable over Rtree indexes when the index has to be updated often. I only know of one QuadTree index package for Python, but that one was last updated in 2004, so I’m not sure if it is compatible with newer versions of Python, and it has to be compiled.
And so I threw together the pure-Python PyQuadTree package; for portable and easy-install uses, and when heavy updates to the index is expected. In reality I didn’t really make the quadtree index code, that credit goes to Matt Rasmussen’s original Quadtree code. What I did was I added support for irregularly shaped quad trees instead of only squares, and simplified the front-end user functions for GIS users. The API syntax is purposely made very similar to the Rtree package and so should be familiar to users of that package. Exact guidelines for how to use it is found on the Github package page linked to below.
Click here to go the Github page where you can download and try the package.
This is timely. I’ve been planning to add quadtrees to karta for a while now, and ran into a problem at work last week where I wished it had them. Checking out your code now!
Gotta love good timing! Is there a reason you needed QuadTrees specifically, or could you have gone for any spatial index like Rtree or PyRtree? Let me know if it works out or not and how it performs speedwise. Unfortunately I still haven’t gotten to try Karta, but I will one of these days 😛
I had been thinking QuadTrees over Rtrees only out of familiarity, to be honest.
Reading your code was educational – thanks! My use case is for point data specifically, so that’s what I ended up implementing, and I got a speed boost by using regular region sizes using hashes for queries rather than recursion.