CODEWITHSUNDEEP
c++cdata-structures
iDev
iDev

Reputation: 2421

How to implement 3d kDTree build and search algorithm in c or c++?

How to implement 3d kDTree build and search algorithm in c or c++? I am wondering if we have a working code to follow

Upvotes: 2

Views: 9239

Answers (3)

Sergei Danielian
Sergei Danielian

Reputation: 5015

I'd like to recommend you a two good presentations to start with:

Both give all (basic ideas behind kd-trees, short visual examples and code snippets) you need to start writing your own implementation.

Update-19-10-2021: Resources are now longer public. Thanks to @Hari for posting new links down below in the comments.

Upvotes: 4

Shawn Chin
Shawn Chin

Reputation: 86844

For an example of a 3D kd-tree implementation in C, take a look at kd3. It is not general purpose library and requires the input data to be in a specific form, but the ideas and approach should be transferable.

Disclosure: I am the author of kd3.

Disclaimer: It was written as proof-of-concept code for an existing application and is therefore not as generic nor as well-tested as it should be. Bug reports/fixes are welcome.

Upvotes: 0

hansmaad
hansmaad

Reputation: 18905

I found the publications of Vlastimil Havran very useful. His Ph.d Thesis gives a nice introduction to kd-trees and traversal algorithms. Further articles are about several improvements, e.g. how to construct kd-tree in O(nlogn). There are also a lot of implementations in different graphic libs. You should just google for it.

Upvotes: 3

Related Questions