Storing Rectangles/Circles/Triangles in a KD-Tree

Question

I was looking at Kd-tree and found some implementations of this algorithm. All of these were storing points (2d in major of cases). What I am trying to achieve is to store different shapes in it like rectangle, triangle etc. So is it possible in kd-trees to store shapes? I have some code for Quad-trees. In that shapes were being stored.

Answer 1

This is not so different than the method used for Quad trees.

For each shape, you should be able to compute :

• its centroid.

• its envelope.

When computing the median, use the centroids. The envelope of a shape should fit in the quad. When inserting a shape in a quad, check if its envelope crosses the hyperplane. If true, store the shape in the quad. If false, put this shape in the appropriate list of shapes of your left or right quad construction call.

Cheers

Answer 2

It depends on what you want to do with your set of shapes once you have your kd-tree for it. Let's say you have a set of rectangles, and you want to quickly find all rectangles that are completely contained in a query rectangle. Then the appropriate way to use a kd-tree (or better yet, a range tree imo) is to store the min and max x and y coordinates for the rectangle as a 4-dimensional point and build a tree for the 4-dimensional points. Then, for a query rectangle (a0,a1)x(b0,b1), you use the tree to do a range query on the 4-dimensional points using the range (a0,+inf) x (-inf, a1) x (b0, +inf) x (-inf, b1).

Answer 3

This is a natural extension of a KD-tree.

When you have only points in your tree:

• Nodes in the tree correspond to regions of your space
• Given a parent node P and children nodes C1, C2, ..., CN, the children nodes Ci are mutually disjoint and they partition P
• Each point x is present in exactly one leaf node of the tree

When you have volumes in your tree:

• Nodes in the tree correspond to regions of your space
• Given a parent node P and children nodes C1, C2, ..., CN, the children nodes Ci are mutually disjoint and they partition P
• Each volume v is present in at least one leaf node of the tree (it's "in" any leaf node that it intersects with)