geometric_sort.hpp File Reference

Axis-alternating geometric ordering of a point cloud (kd-tree ordering). More...

#include <algorithm>
#include <numeric>
#include <vector>
#include <Eigen/Dense>

Namespaces
namespace	ellipsoid_tree

Functions
std::vector< int >	ellipsoid_tree::geometric_sort (const Eigen::Ref< const Eigen::MatrixXd > &points)
	Returns a permutation of {0, ..., N-1} placing the points (columns of the input) in axis-alternating geometric order.

Detailed Description

Axis-alternating geometric ordering of a point cloud (kd-tree ordering).

Recursively sort by one coordinate axis, split at the median, and recurse on each half with the next axis. Nearby points end up nearby in the ordering, which improves cache behavior of downstream sweeps.