Sign in to follow this  
LadaRiha

KD-Tree, simple theory

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 this post


Link to post
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 this post


Link to post
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]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this