How to plot hyperrectangles of scipy.spatial.kdtree

Question

Im trying to perform a KD-tree on a set of x,y coordinate pairs for spatial indexing them. I found scipy.spatial.kdtree to perform this quickly. However I can't seem to manage plotting hyperrectangles of the kdtree (Im using matplotlib).

Does anyone know how to fetch the hyperrectangles generated by the algorithm?

Answer 1

how to fetch the hyperrectangles generated by the algorithm ?

the trick is to generate them as you go along: extend wikipedia K-d tree with e.g.

class Node( namedtuple( "Node",  # aka Box
"level "    # 0 ..
"axis "     # 0 .. Dim
"mid "      # the point with middle x / middle y
"lo hi "    # corners, inbox(p): lo <= p <= hi
"L R "      # left, right Nodes or None
"points "   # if needed / leaves only
)):
...

Code to build (no query yet) might be under my gists.
A sample plot: