# KD-Tree, simple theory

This topic is 3033 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I'm trying to implement KD-tree with sliding midpoint rule (with some density/bucket size) but I'm stuck on one (I'm sure pretty stupid) problem with this splitting rule. I know that first I have to choose the cell's longest size to split. And this is my problem, how can I know which side (or axis) is the longest? I thought that I could find min and max values for each side, compute the length (=max-min) and select the longest. But then I will never have to performe the sliding part, because the splitting value will be always greater than the min value, so at least on point will be on the left of the splitting line (and the same problem happens for max value and the right side). So it is little weird. One solution I'm thinking of is that I will always know range of axis at the beginning. For example, I know that all points have X coordinates generally between 0.0-1.0, so I will try splitting value 0.5 and then check if sliding is necessary. So If I will assume, that the minimum X coordinates is 0.7, I will slide the cutting line towards to this value. Is this assumption correct? Thanks for any help

##### Share on other sites
Quote:
 And this is my problem, how can I know which side (or axis) is the longest?

During the building of your KD-tree, you will have to know the bounding-box of each cell. With this, it is easy to determine wich axis is the longest.

##### Share on other sites
I know but the bounding-box is created from min and max of coordinates of all points, so there will be no sliding because always at least 1 point will be on the left side of cutting plane and at least 1 on the right one. So is it really sliding midpoint? Or am I completely wrong? :-)

EDIT: I got it :) Thanks

[Edited by - LadaRiha on March 28, 2010 5:00:19 PM]

1. 1
2. 2
Rutin
21
3. 3
JoeJ
18
4. 4
5. 5

• 14
• 39
• 23
• 13
• 13
• ### Forum Statistics

• Total Topics
631717
• Total Posts
3001878
×