src/SplitFunctions.h file

Splitting functions for the k-d tree construction.

Contents

Functions

template<typename T, std::size_t N>
auto median(const typename KDTree<T, N>::ArrayIter& begin, const typename KDTree<T, N>::ArrayIter& end, const std::size_t depth) -> KDTree<T, N>::ArrayIter

Function documentation

template<typename T, std::size_t N>
KDTree<T, N>::ArrayIter median(const typename KDTree<T, N>::ArrayIter& begin, const typename KDTree<T, N>::ArrayIter& end, const std::size_t depth)

Parameters
begin the iterator to the beginning of the range
end the iterator to the end of the range
depth

Return the median from the input range at a given dimension. I use std::nth_element over std::sort to speed up the median computation (the average complexity goes from O(n log(n)) to O(n)).