# kd-trees

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

## Recommended Posts

Does anyone know the easiest way to modify kd-trees to support having a single point in there multiple times? For instance, the point (5, 5) might be in there a few times. mike http://www.coolgroups.com/

##### Share on other sites
most properly coded k-d tree this will not be a problem, if space is a concern you could have a reference count for the nodes. what are you using it for?

##### Share on other sites
I'm using it for culling in a maze game.

I got the code by converting pseudocode from Computational Geometry by Mark DeBerg into C++. Here's what happens if you try to add the point (5, 5) to the tree twice:

You call the buildsubtree function, and it creates a partition node with (5,5), and then it calls the function buildsubtree again for the left subtree with both points since their x values are <= 5.

Then, it partitions on y values, and again calls the buildsubtree function again with the two points.

It keeps calling the buildsubtree function infinitely with the same two points.

I'm pretty sure I got the code right, and the author makes no guarantees about being able to add duplicate points.

mike
http://www.coolgroups.com/

##### Share on other sites
once you pick a point to use, it's stored in the node and it's not used in further subdiviosn, why would it be? if I entered two of the same points I'd expect this to happen

point = points.pick random point();
points = points - point(kinda set like operation, you dont process a point twice)
take point split with x dim(or something)
pointsleft = take all points to the left of splitting plane
make tree(pointsLeft)
points right = take all points to right of plane
make tree (pointsRight)

so suppose it identifies the second point as being to the right of the splitting dim, it would call this funciton with only that point, you wouldn't include the point you just processed. this would have a recursive depth of 2, not infinity. once it sees the next point it gonna split using y(orsomething) then, it's gonna call make tree left and make tree right with 0 points, so here is where it terminates.

Tim

##### Share on other sites
This is not how the kd-trees work in the book Computational geometry. If a point is used as a partition, it is not removed from the set of points. All of the initial points are leaves in the implementation in the book.

mike
http://www.coolgroups.com/

##### Share on other sites
I hear ya. ya if you implimented a leaf based k-d tree I could see how that could happen but it seems this could be solved simply by adding a maximun depth to the construction, you know if the depth excedes the number of points you got trouble, and you should stop the construction right there.

Tim

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 27
• 16
• 10
• 10
• 11
• ### Forum Statistics

• Total Topics
634098
• Total Posts
3015525
×