File Exchange

image thumbnail

MATLAB class wrapper for a C++ implementation of a Quadtree

version 1.0.0.0 (42.3 KB) by Shawn Walker
Efficient implementation of a point-region (PR) quadtree for fast nearest neighbor searches.

3 Downloads

Updated 13 Jan 2014

View License

This implementation is based on the paper:

S. F. Frisken and R. N. Perry,
``Simple and Efficient Traversal Methods for Quadtrees and Octrees,''
Journal of Graphics Tools, 2002, Vol. 7, pg. 1-11

This Quadtree class seems to beat MATLAB's KDTree class for speed, both in creating the tree and when doing k-nearest neighbor searches.

Note: it is possible to extend this code to an Octree.

Cite As

Shawn Walker (2020). MATLAB class wrapper for a C++ implementation of a Quadtree (https://www.mathworks.com/matlabcentral/fileexchange/45020-matlab-class-wrapper-for-a-c-implementation-of-a-quadtree), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (7)

Shawn Walker

You cannot add points to a tree (in this implementation). You can create a new tree given a set of points. If you want to update the tree, you can only change the coordinates of the original set of points; you cannot add or delete them. However, from what I have found, it seems to be faster to just recreate the whole tree from scratch, than trying to efficiently re-distribute points.

Sorry for this, but my goal in writing this was for performing closest point searches. You may be able to get by with storing your own list of points, and then creating a quadtree of it whenever you need to search them.

Otherwise, you will need to look at the C++ implementation and modify it to suit your needs.

Thanks very much, this is great. I'm running a simulation in which I add points one by one to the plane, I have one question about the updating procedure for the quadtree. I'm C++ illiterate, and using the Matlab wrapper pretty blindly, so I apologize if the answer to this question is obvious in the C++ file. Basically, when the quadtree updates, is recreating the whole tree, or just removing some points and adding some new ones? If it's the latter, won't the tree become imbalanced after a while? I'd just like to know so that I can balance the tree every once in a while when I add points. That way I don't need to rebuild the tree every time, but can once it's unbalanced. Thanks!

shir

yes i need all kinds of neighbors except corner ones. It would be great if you'll do it. I will take a look at files myself too.

OK. You want neighbors of a quadtree *cell*, such as the left neighbor of a quadtree cell, correct?

I have not interfaced this with MATLAB. However, please look at the source file:

'quadtree.cc'

and search for the class method:

'Locate_Left_Neighbor'

That is how you could do it from within C++. Interfacing it to MATLAB requires modifying 'mexQuadtree.cpp' and the corresponding MATLAB class.

I could expand the interface, but I cannot guarantee when that would happen. If you could give a few more details about what you want, that would be great.

For example, I assume you would want the UP, DOWN, LEFT, and RIGHT neighbors? The corner neighbors too?

shir

yes, i've seen it. I'm talking about neighbors of particular point which belongs to quadtree(node), not arbitrary points.

Shir,

Yes! Look at the m-file:

'test_Quadtree_Random_Points.m'

in the 'Unit_Test' sub-directory. It does a demonstration of k-nearest neighbor find.

Also, if you have added 'QuadTree' to your MATLAB path, then you can type:

help mexQuadtree
help mexQuadtree.kNN_Search

to get more info about how to use it.

shir

Hello, is there a function of neighbor search in your implementation ?

MATLAB Release Compatibility
Created with R2013b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Acknowledgements

Inspired by: Example MATLAB class wrapper for a C++ class