Pure Python Quadtree Implementation

Question

All,

There are a few examples on implementing a quadtree using Python but my question is, does anyone know of a class written in pure python as in a single .py file that I can easily include in my project? The three most popular packages are listed here Are any of these quad-tree libraries any good? but I have not had luck with using them because of all the dependencies required to run them. I am really going for something lighweight and relatively simple to use. I would like to call the script by passing in the bounds for the entire globe and work down from there. myMethod((-180,-90,180,90))

Thanks, Adam

Intercession

What about the second library in the question you linked to (#2299017)? The dependencies are trivial to none. – Trout

Answer 1

PyQuadTree is a pretty lightweight module (that I built based on someone else's code). It's written in pure-Python, has no dependencies, and doesn't require any installation or compiling at all. It's a single .py file that can be easily included as part of bigger project, which sounds like what is being asked about here.

It also has documentation and supports both Python 2x and 3x.

Vernita

I have no experience with Quadtrees, but I have to implement it for a project on trajectory analysis. Please kindly let me know, if your module can be helpful with the analysis of trajectories (trajectory data which consists of sequence of x,y coordinates) – Lilley

If by trajectory you simply mean a line geometry that represents movement, that works fine. But the lib doesnt care about type of geometry, all it needs is a bounding box (xmin,ymin,xmax,ymax). So you can insert many different trajectory bboxes into the tree, and then you can query the tree to quickly see which trajectories are located in an area. Go to the github repo linked to in the blogpost to read specifically how to use it. – Vernita

Thank you so much for replying. Please have a look here #44148128 I am trying to implement this on a data frame, also I am not sure how to query the tree to know which trajectories belongs to which quadrants. Even a little help will be very useful. Thanks. – Lilley

Thank you for your library, I could partially achieve what I wanted. But I would want your suggestion on a special scenario, where there are two very close trajectories, and both of them are horizontal. So both of them will have their own bbox which will simply be two lines over the trajectories. So,if I give an Intersection box which targetting the area between these two trajectories, inspite of being very close, the two trajectories wont be a match. Solution to this might be creating a buffer box around the bounding box to address this scenario. Please suggest what can I do? – Lilley

If the intersection bbox does not contain the two trajectory bboxes, then this is the expected behavior. Not sure why you mention them being horizontal, the behavior would be the same regardless. Or is your question more about how you can get matches that are near within a buffer? If so I suggest making a new question, the short answer being yes you should buffer the intersection bbox. Pyqtree so far doesnt have a method for getting x nearest. – Vernita

Answer 2

Take a look at Rect. You'll need 2 files. You can merge them into one.

Salinas

The wiki pages (and indeed the entire project) on code.google.com for the Rect package seem to have gone missing. Anyone know of an updated link for the missing info? – Overpraise

That's unfortunate. The tar.gz is still available on PyPi though. – Salinas