C++ API reference

This is the complete reference for the (internal) C++ API of py4dgeo. You only need to consult this documentation if you are aiming to extend the C++ core of py4dgeo.

namespace py4dgeo

Typedefs

using EigenPointCloud = Eigen::Matrix<double, Eigen::Dynamic, 3, Eigen::RowMajor>

The C++ type for a point cloud.

Point clouds are represented as (nx3) matrices from the Eigen library.

The choice of this type allows us both very efficient implementation of numeric algorithms using the Eigen library, as well as no-copy interoperability with numpy’s multidimensional arrays.

using EigenPointCloudRef = Eigen::Ref<EigenPointCloud>

A non-const reference type for passing around EigenPointCloud.

You should use this in function signatures that accept a point cloud as a parameter and need to modify the point cloud.

using EigenPointCloudConstRef = Eigen::Ref<const EigenPointCloud>

A const reference type for passing around EigenPointCloud.

You should use this in function signatures that accept a read-only point cloud.

using EigenNormalSet = Eigen::Matrix<double, Eigen::Dynamic, 3, Eigen::RowMajor>: The C++ type to represent a set of normal vectors on a point cloud.

using EigenNormalSetRef = Eigen::Ref<EigenNormalSet>: A mutable reference to a set of normal vectors on a point cloud.

using EigenNormalSetConstRef = Eigen::Ref<const EigenNormalSet>: An immutable reference to a set of normal vectors on a point cloud.

using IndexType = Eigen::Index: The type used for point cloud indices.

using DistanceVector = std::vector<double>: The variable-sized vector type used for distances.

using UncertaintyVector = std::vector<DistanceUncertainty>: The variable-sized vector type used for uncertainties.

Enums

enum class MemoryPolicy

An enumerator for py4dgeo’s memory policy.

This is used and documented through its Python binding equivalent.

Values:

enumerator STRICT

enumerator MINIMAL

enumerator COREPOINTS

enumerator RELAXED

struct DistanceUncertainty

#include <py4dgeo.hpp>

Return structure for the uncertainty of the distance computation.

This structured type is used to describe the uncertainty of point cloud distance at a single corepoint. It contains the level of detection, the spread within both point clouds (e.g. the standard deviation of the distance measure) and the number of sampled points.

Public Members

double lodetection

double spread1

IndexType num_samples1

double spread2

IndexType num_samples2

struct Supervoxel

Public Functions

inline Supervoxel()

inline Supervoxel(EigenPointCloudConstRef c, EigenNormalSetConstRef n, const Eigen::Vector3d &center, EigenPointCloudConstRef boundary)

Public Members

EigenPointCloud cloud

EigenNormalSet normals

Eigen::Vector3d centroid

EigenPointCloud boundary_points

namespace py4dgeo

class Epoch

#include <epoch.hpp>

A data structure representing an epoch.

Stores the point cloud itself (without taking ownership of it) and provides two search trees: a KDTree and an Octree. This structure allows efficient spatial queries without duplicating data.

Public Functions

Epoch(const EigenPointCloudRef&)

Epoch(std::shared_ptr<EigenPointCloud>)

std::ostream &to_stream(std::ostream&) const

Public Members

EigenPointCloudRef cloud

KDTree kdtree

Octree octree

Public Static Functions

static std::unique_ptr<Epoch> from_stream(std::istream&)

static inline void set_default_radius_search_tree(SearchTree tree)

static inline void set_default_nearest_neighbor_tree(SearchTree tree)

static inline SearchTree get_default_radius_search_tree()

static inline SearchTree get_default_nearest_neighbor_tree()

Private Members

std::shared_ptr<EigenPointCloud> owned_cloud

Private Static Attributes

static SearchTree default_radius_search_tree = SearchTree::KDTree 

static SearchTree default_nearest_neighbor_tree = SearchTree::KDTree 

namespace py4dgeo

Typedefs

using RadiusSearchResult = std::vector<IndexType>: Return type used for radius searches.

using RadiusSearchDistanceResult = std::vector<std::pair<IndexType, double>>: Return type used for radius searches that export calculated squared distances

using NearestNeighborsDistanceResult = std::vector<std::pair<std::vector<IndexType>, std::vector<double>>>: Return type used for nearest neighbor with Euclidian distances searches.

using NearestNeighborsResult = std::vector<std::vector<IndexType>>: Return type used for nearest neighbor searches.

using RadiusSearchFuncSingle = std::function<void(const Eigen::Vector3d&, RadiusSearchResult&)>

Function type for performing a single-radius search.

This function takes a 3D query point (as an Eigen vector) and outputs a vector of point indices that lie within a sphere around the query point with specified radius. The specific search algorithm (KDTree or Octree) is determined at runtime.

Param query_point:: The 3D coordinates of the point to search around.
Param result:: A vector of indices of points within the search radius.

using RadiusSearchFunc = std::function<void(const Eigen::Vector3d&, std::size_t, RadiusSearchResult&)>

Function type for performing a multi-radius search.

This function takes a 3D point and an index representing the radius to use from a precomputed list of radii. It outputs a vector of point indices that lie within the selected radius.

Param query_point:: The 3D coordinates of the point to search around.
Param radius_index:: The index to select the radius from a list of radii.
Param result:: A vector of indices of points within the search radius.

Enums

enum class SearchTree

Values:

enumerator KDTree

enumerator Octree

Defines

NANOFLANN_NODE_ALIGNMENT

namespace py4dgeo

class KDTree

#include <kdtree.hpp>

Efficient KDTree data structure for nearest neighbor/radius searches.

This data structure allows efficient radius searches in 3D point cloud data. It is based on NanoFLANN: https://github.com/jlblancoc/nanoflann

Public Functions

std::ostream &saveIndex(std::ostream &stream) const: Save the index to a (file) stream.

std::istream &loadIndex(std::istream &stream): Load the index from a (file) stream.

void build_tree(int leaf)

Build the KDTree index.

This initializes the KDTree search index. Calling this method is required before performing any nearest neighbors or radius searches.

Parameters:: leaf – The threshold parameter definining at what size the search tree is cutoff. Below the cutoff, a brute force search is performed. This parameter controls a trade off decision between search tree build time and query time.

void invalidate(): Invalidate the KDTree index.

std::size_t radius_search(const double *querypoint, double radius, RadiusSearchResult &result) const

Peform radius search around given query point.

This method determines all the points from the point cloud within the given radius of the query point. It returns only the indices and the result is not sorted according to distance.

Parameters:

querypoint – [in] A pointer to the 3D coordinate of the query point
radius – [in] The radius to search within
result – [out] A data structure to hold the result. It will be cleared during application.

Returns:

The amount of points in the return set

std::size_t radius_search_with_distances(const double *querypoint, double radius, RadiusSearchDistanceResult &result) const

Perform radius search around given query point exporting distance information.

This method determines all the points from the point cloud within the given radius of the query point. It returns their indices and their distances from the query point. The result is sorted by ascending distance from the query point.

Parameters:

querypoint – [in] A pointer to the 3D coordinate of the query point
radius – [in] The radius to search within
result – [out] A data structure to hold the result. It will be cleared during application.

Returns:

The amount of points in the return set

void nearest_neighbors_with_distances(EigenPointCloudConstRef cloud, NearestNeighborsDistanceResult &result, int k) const

Calculate the nearest neighbors with Euclidian distance for an entire point cloud.

Parameters:

cloud – [in] The point cloud to use as query points
result – [out] The indexes and distances of k nearest neighbors for each point
k – [in] The amount of nearest neighbors to calculate

void nearest_neighbors(EigenPointCloudConstRef cloud, NearestNeighborsResult &result, int k) const

Calculate the nearest neighbors for an entire point cloud.

Parameters:

cloud – [in] The point cloud to use as query points
result – [out] The indexes of k nearest neighbors for each point
k – [in] The amount of nearest neighbors to calculate

int get_leaf_parameter() const: Return the leaf parameter this KDTree has been built with.

Public Static Functions

static KDTree create(const EigenPointCloudRef &cloud)

Construct instance of KDTree from a given point cloud.

This is implemented as a static function instead of a public constructor to ease the implementation of Python bindings.

Parameters:: cloud – The point cloud to construct the search tree for

Private Types

using KDTreeImpl = nanoflann::KDTreeSingleIndexAdaptor<nanoflann::L2_Simple_Adaptor<double, Adaptor, double>, Adaptor, 3, IndexType>: The NanoFLANN index implementation that we use.

Private Functions

KDTree(const EigenPointCloudRef&): Private constructor from pointcloud - use through KDTree::create.

Private Members

friend Epoch

Adaptor adaptor

std::shared_ptr<KDTreeImpl> search

int leaf_parameter = 0

struct Adaptor

An adaptor between our Eigen data structures and NanoFLANN.

Public Functions

inline std::size_t kdtree_get_point_count() const

inline double kdtree_get_pt(const IndexType idx, const IndexType dim) const

template<class BBOX> inline bool kdtree_get_bbox(BBOX&) const

Public Members

EigenPointCloudRef cloud

struct NoDistancesReturnSet

A structure to perform efficient radius searches with NanoFLANN.

The built-in return set of NanoFLANN does automatically export the distances as well, which we want to omit if we already know that we do not need the distance information.

Public Types

using DistanceType = double

Public Functions

inline std::size_t size() const

inline bool full() const

inline bool addPoint(double dist, IndexType idx)

inline double worstDist() const

inline void sort()

Public Members

double radius

RadiusSearchResult &indices

struct WithDistancesReturnSet

A custom result set structure for collecting radius search results with squared distances using nanoflann.

This structure is used with nanoflann’s radiusSearchCustomCallback() to collect search results in a user-defined format. It stores pairs of point indices and their corresponding squared distances to the query point in a std::vector<std::pair<IndexType, double>> (RadiusSearchDistanceResult).

By using this structure instead of nanoflann::ResultItem, we avoid copying between incompatible result types and maintain compatibility with Octree which uses the same result type.

This class satisfies the interface expected by nanoflann’s custom result set:

addPoint(distance, index): stores the result if within radius
size(), full(), worstDist(): for compatibility
sort(): optional post-processing

Public Types

using DistanceType = double

Public Functions

inline std::size_t size() const

inline bool full() const

inline bool addPoint(double dist_sq, IndexType idx)

inline double worstDist() const

inline void sort()

Public Members

double radius

RadiusSearchDistanceResult &result

namespace py4dgeo

Functions

template<typename T, unsigned int BITS> constexpr T dilate(T x)

Dilate (bit-spread) a small integer so its bits occupy every third bit position.

This function takes a BITS-bit integer x and returns a value in which each original bit has been moved to position (3*i). Two zero bits are inserted between every bit of the input. This operation is the core of Morton (Z-order) encoding, where the x, y, and z bits of a coordinate are interleaved to form a single integer key.

Example (for BITS = 4): input: b3 b2 b1 b0 output: 0 0 b3 0 0 b2 0 0 b1 0 0 b0

The result corresponds to the x-axis contribution of a Morton code before interleaving with y and z bits.

template<typename T, unsigned int BITS, std::size_t TABLE_SIZE = (1ULL << BITS)> static constexpr std::array<T, TABLE_SIZE> make_dilate_table()

Generate a compile-time lookup table of dilated integers.

This function builds a table of size (1 << BITS), where entry i contains dilate(i). The table allows Morton encoding to be done efficiently in large fixed-size chunks (e.g., 8 bits or 5 bits at a time), instead of looping over individual bits.

These tables are computed at compile time (constexpr) and enable the encoder to construct full Morton keys using a handful of table lookups and bit shifts, which is significantly faster than iterative bit interleaving.

class Octree

#include <octree.hpp>

Efficient Octree data structure for nearest neighbor/radius searches.

This data structure allows efficient radius searches in 3D point cloud data. Unlike KDTree, it recursively subdivides space into eight octants.

Public Types

using SpatialKey = std::uint32_t: Alias for the spatial key type used for Z-order value encoding.

using PointContainer = std::vector<IndexType>: Return type used for points.

using KeyContainer = std::vector<SpatialKey>: Return type used for cell searches.

using OctreeCoordinate = std::array<uint32_t, 3>: Coordinate within the octree.

using OctreeCoordinates = Eigen::Matrix<uint32_t, Eigen::Dynamic, 3, Eigen::RowMajor>: Coordinates within the octree.

Public Functions

void build_tree(bool force_cubic = false, std::optional<Eigen::Vector3d> min_corner = std::nullopt, std::optional<Eigen::Vector3d> max_corner = std::nullopt)

Build the Octree index.

This initializes the Octree search index. Calling this method is required before performing any nearest neighbors or radius searches.

Parameters:

force_cubic – If true, the bounding box will be forced to have equal side lengths, resulting in a cubic shape.
min_corner – Optional minimum point (lower corner of the bounding box). If not provided, the minimum point is computed automatically from the input data.
max_corner – Optional maximum point (upper corner of the bounding box). If not provided, the maximum point is computed automatically from the input data.

void invalidate()

Clears the Octree structure, effectively resetting it.

This function deallocates the Octree by clearing the sorted array of indices and keys. This operation invalidates the current Octree, requiring it to be rebuilt before further use.

std::ostream &saveIndex(std::ostream &stream) const: Save the index to a (file) stream.

std::istream &loadIndex(std::istream &stream): Load the index from a (file) stream.

inline const KeyContainer &get_spatial_keys() const

Get all spatial keys (Z-order values) of the Octree.

Returns:: Vector of spatial keys (Z-order values)

inline const PointContainer &get_point_indices() const

Get all point indices corresponding to spatial keys.

Returns:: Vector of point indices

std::size_t radius_search(const Eigen::Vector3d &query_point, double radius, unsigned int level, RadiusSearchResult &result) const

Perform radius search around given query point.

This method determines all the points from the point cloud within the given radius of the query point. It returns only the indices and the result is not sorted according to distance.

Parameters:

query_point – [in] A pointer to the 3D coordinate of the query point
radius – [in] The radius to search within
level – [in] The depth level at which to perform the search
result – [out] A data structure to hold the point indices. It will be cleared during application.

Returns:

Number of points found

std::size_t radius_search_with_distances(const Eigen::Vector3d &query_point, double radius, unsigned int level, RadiusSearchDistanceResult &result) const

Perform radius search around given query point.

This method determines all the points from the point cloud within the given radius of the query point. It returns only the indices and the result is not sorted according to distance.

Parameters:

query_point – [in] A pointer to the 3D coordinate of the query point
radius – [in] The radius to search within
level – [in] The depth level at which to perform the search
result – [out] A data structure to hold the point indices and corresponding distances. It will be cleared during application.

Returns:

Number of points found

inline unsigned int get_number_of_points() const: Return the number of points in the associated cloud.

inline constexpr unsigned int get_max_depth() const: Return the maximum octree depth.

inline Eigen::Vector3d get_box_size() const: Return the side length of the bounding box.

inline Eigen::Vector3d get_min_point() const: Return the minimum point of the bounding box.

inline Eigen::Vector3d get_max_point() const: Return the maximum point of the bounding box.

inline Eigen::Vector3d get_cell_size(unsigned int level) const: Return the size of cells at a level of depth.

inline constexpr unsigned int get_number_of_cells(unsigned int level) const: Return the number of cells at a level of depth.

inline constexpr unsigned int get_number_of_cells_per_axis(unsigned int level) const: Return the number of cells per axis at a level of depth.

inline unsigned int get_number_of_occupied_cells(unsigned int level) const: Return the number of occupied cells per level of depth.

inline unsigned int get_max_cell_population(unsigned int level) const: Return the maximum cell population per level of depth.

inline double get_average_cell_population(unsigned int level) const: Return the average number of points per level of depth.

inline double get_std_cell_population(unsigned int level) const: Return the standard deviation of number of points per level of depth.

std::size_t get_cell_population(SpatialKey truncated_key, unsigned int level) const

Returns the number of points lying in a single octree cell at a specified depth level.

Parameters:

truncated_key – [in] Truncated spatial key identifying the query cell
level – [in] Octree depth level of the query cell

Returns:

The number of points in the specified cell

std::vector<std::size_t> get_cell_population(const KeyContainer &truncated_keys, unsigned int level) const

Returns the cell populations for multiple octree cells at a specified depth level.

Parameters:

truncated_keys – [in] Truncated spatial keys identifying the query cells
level – [in] Octree depth level of the query cell

Returns:

The number of points in the specified cells

std::size_t get_point_indices_from_cells(SpatialKey truncated_key, unsigned int level, RadiusSearchResult &result) const

Return indices of points lying in a single octree cell at a specified depth level.

Given a spatial key identifying the octree cell (truncated to the same depth level), this function gathers all point indices belonging to this cell.

The search exploits the sorted order of the input keys to avoid redundant scans and achieve efficient sequential access.

Parameters:

truncated_key – [in] Spatial keys of the query cell, truncated to the specified depth level
level – [in] Octree depth level of the query cells
result – [out] Container to hold the resulting point indices. Existing contents will be preserved and appended to.

Returns:

The total number of points appended to the result container

std::size_t get_point_indices_from_cells(const KeyContainer &truncated_keys, unsigned int level, RadiusSearchResult &result) const

Return indices of points lying in multiple octree cells at a specified depth level.

Given a sorted list of spatial keys identifying octree cells (truncated to the same depth level), this function gathers all point indices belonging to those cells.

The search exploits the sorted order of the input keys to avoid redundant scans and achieve efficient sequential access.

Parameters:

truncated_keys – [in] Sorted spatial keys of the query cells, truncated to the specified depth level
level – [in] Octree depth level of the query cells
result – [out] Container to hold the resulting point indices. Existing contents will be preserved and appended to.

Returns:

The total number of points appended to the result container

KeyContainer get_unique_cells(unsigned int level) const

Returns the unique spatial keys of occupied cells at a specified depth level.

Parameters:: level – [in] The depth level at which to retrieve the unique cells
Returns:: A container of unique (truncated) spatial keys of occupied cells

OctreeCoordinate get_coordinates(SpatialKey truncated_key) const

Return the octree-grid coordinate (x,y,z) of a spatial key.

If no level is provided, the coordinate at maximum depth is returned.

OctreeCoordinates get_coordinates(const KeyContainer &truncated_keys) const

Return the octree-grid coordinates (x,y,z) of a set of spatial keys.

If no level is provided, the coordinates at maximum depth is returned.

OctreeCoordinates get_coordinates_at_level(unsigned int level) const

Return the octree-grid coordinates (x,y,z) of all points at a given level.

If no level is provided, the coordinates at maximum depth is returned.

unsigned int find_appropriate_level_for_radius_search(double radius) const

Returns the level of depth at which a radius search will be most efficient.

Parameters:: radius – The radius of the search sphere
Returns:: The depth level at which to perform a radius search

Public Static Functions

static Octree create(const EigenPointCloudRef &cloud)

Construct instance of Octree from a given point cloud.

This is implemented as a static function instead of a public constructor to ease the implementation of Python bindings.

Parameters:: cloud – The point cloud to construct the search tree for

Private Types

enum class cell_relation_to_sphere

Enum to describe the geometric relationship between a cell and a sphere.

Values:

enumerator Inside

enumerator Intersecting

enumerator Outside

Private Functions

Octree(const EigenPointCloudRef&): Private constructor from point cloud - use through Octree::create.

inline SpatialKey compute_spatial_key(const Eigen::Vector3d &point) const

Computes a unique spatial key (Z-order value) for a given point.

This function normalizes the input point within the bounding box and maps it to an integer 3D grid of size ‘2^max_depth × 2^max_depth × 2^max_depth’. The computed grid coordinates are then interleaved using bitwise operations to generate a Z-order value key that represents the point’s hierarchical position in the Octree.

Parameters:: point – The 3D point for which to compute the spatial key.
Returns:: A SpatialKey (unsigned integer) representing the spatial key of the point.

inline SpatialKey compute_spatial_key(const OctreeCoordinate &query_cell, unsigned int level) const

Computes a unique spatial key (Z-order value) for a given octree cell.

Parameters:: query_cell – The 3D octree coordinate for which to compute the spatial key.
Returns:: A SpatialKey (unsigned integer) representing the spatial key of the point.

inline SpatialKey compute_spatial_key(SpatialKey ix, SpatialKey iy, SpatialKey iz) const

Computes a unique spatial key (Z-order value) for a given point.

This function takes integer grid coordinates and interleaves their bits to generate a Z-order value key that represents the point’s hierarchical position in the Octree.

Parameters:

ix – The integer x-coordinate in the grid.
iy – The integer y-coordinate in the grid.
iz – The integer z-coordinate in the grid.

Returns:

A SpatialKey (unsigned integer) representing the spatial key of the point.

inline OctreeCoordinate decode_spatial_key_at_level(SpatialKey key, unsigned int level) const

Decode a spatial key into (x, y, z) coordinates at a given octree level.

The input SpatialKey is a Morton-encoded (Z-order) spatial key where the bits of x, y, and z are interleaved as:

... z2 y2 x2  z1 y1 x1  z0 y0 x0

At maximum depth (level == max_depth), decode_spatial_key() returns the full-resolution integer coordinates (max_depth bits per axis).

For coarser octree levels, this function first discards the least significant Morton “triples” (x,y,z) by shifting the key to the right by

bit_shift[level] = 3 * (max_depth - level)

which removes all detail below the requested level while preserving the x/y/z bit-lane alignment. The truncated code is then decoded via decode_spatial_key(), yielding the cell coordinates at the requested level.

In other words:

level == max_depth: full-resolution coordinates
level < max_depth: coordinates on a coarser 2^level grid

Parameters:

key – Morton-encoded spatial key.
level – Target octree level in [0, max_depth].

Returns:

(x, y, z) octree-grid coordinates at the specified level.

void compute_bounding_box(bool force_cubic = false, std::optional<Eigen::Vector3d> min_corner = std::nullopt, std::optional<Eigen::Vector3d> max_corner = std::nullopt)

Computes the smallest power-of-two bounding box that contains all points.

This function calculates the minimum and maximum coordinates of the point cloud and determines a cuboid that fully encloses the data. The box size is rounded up to the nearest power of two.

The computed bounding box is stored in min_point, max_point, and box_size.

Parameters:

force_cubic – If true, the bounding box will be forced to have equal side lengths, resulting in a cubic shape.
min_corner – Optional minimum point (lower corner of the bounding box). If not provided, the minimum point is computed automatically from the input data.
max_corner – Optional maximum point (upper corner of the bounding box). If not provided, the maximum point is computed automatically from the input data.

void compute_statistics(): Computes the average cell properties of occupied cells at all depth levels.

template<typename Reserve, typename CallbackCandidate, typename CallbackInside> inline void radius_search_backend(const Eigen::Vector3d &query_point, double radius, unsigned int level, Reserve &&reserve, CallbackCandidate &&check_candidate, CallbackInside &&take_all) const

Perform radius search with a callback for each matching point.

Searches all points within the given radius around a query point at a specified octree level. For each point inside the radius, the provided callback is called with its index and distance.

Used internally to implement both index-only and distance-returning search variants.

Template Parameters:

Callback – A callable accepting (IndexType, double)

Parameters:

query_point – [in] The 3D coordinates of the query point
radius – [in] The search radius
level – [in] The octree depth level
check_candidate – [in] Called for each candidate point found within the sphere
take_all – [in] Called for all points in cells that are completely within the sphere

std::size_t get_cells_intersected_by_sphere(const Eigen::Vector3d &query_point, double radius, unsigned int level, KeyContainer &inside, KeyContainer &intersecting) const

Returns spatial keys of cells intersected by a sphere with specified radius with it’s center at the query point.

Parameters:

query_point – [in] A reference to of the query point
radius – [in] The radius to search within
level – [in] The depth level to be considered
inside – [out] A vector of spatial keys of the cells entirely in the sphere
intersecting – [out] A vector of spatial keys of the intersected cells

Returns:

The number of intersected cells and cells that are fully inside the sphere

std::optional<IndexType> get_cell_index_start(SpatialKey truncated_key, SpatialKey bitShift, IndexType start_index, IndexType end_index) const

Returns the first occurrence of the index of a cell in the sorted array of point indices and point spatial keys.

Parameters:

key – The spatial key of the query cell
bitShift – The bit shift corresponding to the Octree depth level of the query cell
start_index – Start index
end_index – End index

Returns:

The index of first occurrence of the cell spatial key

std::optional<IndexType> get_cell_index_end(SpatialKey truncated_key, SpatialKey bitShift, IndexType start_index, IndexType end_index) const

Returns the last occurrence of the index of a cell in the sorted array of point indices and point spatial keys.

Parameters:

truncated_key – The spatial key of the query cell
bitShift – The bit shift corresponding to the Octree depth level of the query cell
start_index – Start index
end_index – End index

Returns:

The index of last occurrence of the cell spatial key

std::optional<IndexType> get_cell_index_end_exponential(SpatialKey truncated_key, unsigned int level, IndexType first_index, IndexType global_end_index) const

Efficiently finds the end index of a block of points belonging to the same truncated spatial key.

This function assumes the data is sorted by spatial keys and performs a stride-based search to narrow the interval where the last matching key may occur. The search begins from the known start index of a cell and advances by the estimated average number of points per cell (based on depth level statistics). Once a non-matching key is detected or the global bounds are exceeded, a binary search is performed within the refined interval to find the precise end.

This hybrid approach combines data-aware range narrowing with binary search for performance.

Parameters:

truncated_key – The spatial key (already bit-shifted) identifying the target cell
level – Octree depth level (used to get average cell population)
first_index – Start index of the block in the sorted array
global_end_index – Absolute upper bound for the search (typically the size of the array)

Returns:

Index one past the last occurrence of the given spatial key, or std::nullopt if not found

std::optional<std::pair<IndexType, IndexType>> get_cell_index_range(SpatialKey truncated_key, unsigned int level, IndexType search_start, IndexType search_end) const

Compute the index range of points belonging to a single octree cell.

Given a truncated spatial key identifying an octree cell at a given depth level, this function locates the contiguous block of point indices belonging to that cell in the internally sorted index structure.

The returned index range is half-open: [first, last).

Parameters:

truncated_key – [in] Truncated spatial key identifying the query cell
level – [in] Octree depth level of the query cell
search_start – [in] Lower bound index for the search window
search_end – [in] Upper bound index for the search window (exclusive)

Returns:

Optional pair (first, last) describing the index range of points in the cell, or std::nullopt if the cell contains no points

bool append_points_from_cell(SpatialKey truncated_key, unsigned int level, IndexType &current_start_index, IndexType search_limit_index, RadiusSearchResult &result) const

Append indices of points belonging to a single octree cell.

Finds all points contained in the specified octree cell and appends their point indices to the provided result container.

The search window is advanced to start after the current cell’s block, enabling efficient sequential processing of sorted cell queries.

Parameters:

truncated_key – [in] Truncated spatial key identifying the query cell, truncated to the specified depth level
level – [in] Octree depth level of the query cell
current_start_index – [inout] Start index for the search window; updated to the end of the current cell’s block
search_limit_index – [in] Upper bound of the search window (exclusive)
result – [inout] Container to which point indices are appended

Returns:

True if the cell contains points, false otherwise

Private Members

EigenPointCloudRef cloud: Reference to the point cloud.

unsigned int number_of_points = 0: Number of points in the cloud.

IndexAndKey indexed_keys: Pairs of spatial key (Z-order values) and corresponding index, sorted by z-order value

Eigen::Vector3d min_point: Min point of the bounding box.

Eigen::Vector3d max_point: Max point of the bounding box.

Eigen::Vector3d box_size: Size of the bounding box.

Eigen::Vector3d inv_box_size: Inverse of box size.

std::array<Eigen::Vector3d, max_depth + 1> cell_size: Cell size as a function of depth level.

std::array<unsigned int, max_depth + 1> occupied_cells: Number of occupied cells per depth level.

std::array<unsigned int, max_depth + 1> max_cell_population: Maximum number of points per depth level.

std::array<double, max_depth + 1> average_cell_population: Average number of points per depth level.

std::array<double, max_depth + 1> std_cell_population: Standard deviation of points per depth level.

friend Epoch: Allow the Epoch class to directly call the private constructor.

Private Static Functions

static inline uint64_t compact3(uint64_t v)

Extracts and compacts every third bit from a Morton-encoded word.

Morton (Z-order) encoding interleaves the bits of three coordinates: x0 y0 z0 x1 y1 z1 x2 y2 z2 …

Given a 64-bit integer v that represents one of these three shifted Morton streams (i.e., either key >> 0, key >> 1, or key >> 2), this function isolates the bits belonging to one coordinate and compacts them into contiguous low-order bits:

input bits: v = _ _ x2 _ _ x1 _ _ x0 (spread every 3rd bit) output: x = 0 0 0 x2 x1 x0 (packed)

The implementation applies a sequence of bit masks and shift-OR operations. Each step reduces the spacing between valid bits while preventing bits from moving across structural boundaries. This is the standard high-performance Morton decode algorithm used in libmorton, Embree, and OptiX.

The routine works for both 32-bit and 64-bit Morton keys: if v originates from a 32-bit Morton code, all upper bits are zero and the additional compaction steps simply have no effect. No separate 32-bit implementation is required.

Parameters:: v – The shifted Morton stream (x = key>>0, y = key>>1, z = key>>2).
Returns:: The compacted coordinate (up to 22 bits for max depth 21).

static inline OctreeCoordinate decode_spatial_key(SpatialKey key)

Decodes a spatial key into integer coordinates.

A Morton (Z-order) key interleaves the bits of three coordinates x, y, z:

morton = z2 y2 x2  z1 y1 x1  z0 y0 x0 ...

This function extracts each bit stream by shifting the Morton key: x-bits: key >> 0 y-bits: key >> 1 z-bits: key >> 2

and then compacts them using compact3(). The result is the integer octree-grid coordinate of the point at the maximum tree depth. If a coarser level is required, the caller can right-shift the results by (max_depth - level).

Works for both 32-bit and 64-bit Morton keys. Larger word sizes simply provide more Morton layers; compact3() automatically ignores unused bits.

Parameters:: key – The Morton-encoded spatial key.
Returns:: The decoded (x, y, z) octree-grid coordinate at maximum depth.

Private Static Attributes

static constexpr SpatialKey invalid_key = std::numeric_limits<SpatialKey>::max(): Invalid spatial key constant.

static constexpr unsigned int max_depth = (sizeof(SpatialKey) * 8) / 3: Max depth level, depends solely on spatial key integer representation.

static constexpr unsigned int grid_size = (1 << max_depth): Number of cells per axis at the lowest level (2^max_depth)

static constexpr std::array<SpatialKey, max_depth + 1> bit_shift = []() {std::array<SpatialKey, max_depth + 1> arr{};for (std::size_t level = 0; level <= max_depth; ++level) {arr[level] = 3 * (max_depth - level);}return arr;}(): Bit shift per level.

static constexpr auto dilate8_table = make_dilate_table<SpatialKey, 8>(): Lookup table for dilating 8-bit spatial keys (256 entries), computed at compile time.

static constexpr auto dilate5_table = make_dilate_table<SpatialKey, 5>(): Lookup table for dilating 5-bit spatial keys (32 entries), computed at compile time

static constexpr auto dilate2_table = make_dilate_table<SpatialKey, 2>(): Lookup table for dilating 2-bit spatial keys (4 entries), computed at compile time

static constexpr std::array<SpatialKey, max_depth + 1> number_of_cells = []() constexpr {std::array<SpatialKey, max_depth + 1> a{};for (unsigned int i = 0; i <= max_depth; ++i)a[i] =SpatialKey(1) << 3 * i;return a;}(): Number of cells as a function of depth level.

static constexpr std::array<uint32_t, max_depth + 1> number_of_cells_per_axis = []() constexpr {std::array<uint32_t, max_depth + 1> a{};for (unsigned int i = 0; i <= max_depth; ++i)a[i] = uint32_t(1) << i;return a;}(): Number of cells per axis as a function of depth level.

Friends

friend struct OctreeTestAccess

struct IndexAndKey

#include <octree.hpp>

Struct combining Z-order value and original point index.

Public Members

KeyContainer keys: Z-order values.

PointContainer indices: Indices of the corresponding points in cloud.

void py4dgeo::compute_distances(EigenPointCloudConstRef, double, const Epoch&, const Epoch&, EigenNormalSetConstRef, double, double, DistanceVector&, UncertaintyVector&, const WorkingSetFinderCallback&, const DistanceUncertaintyCalculationCallback&): Compute M3C2 distances.

void py4dgeo::compute_multiscale_directions(const Epoch&, EigenPointCloudConstRef, const std::vector<double>&, EigenNormalSetConstRef, EigenNormalSetRef, std::vector<double>&): Compute M3C2 multi scale directions.

namespace py4dgeo

Typedefs

using EigenSpatiotemporalArray = Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic, Eigen::RowMajor>: The type to use for the spatiotemporal distance array.

using EigenSpatiotemporalArrayRef = Eigen::Ref<EigenSpatiotemporalArray>

using EigenSpatiotemporalArrayConstRef = Eigen::Ref<const EigenSpatiotemporalArray>

using EigenTimeSeries = Eigen::Vector<double, Eigen::Dynamic>: The type to use for a TimeSeries.

using EigenTimeSeriesRef = Eigen::Ref<EigenTimeSeries>

using EigenTimeSeriesConstRef = Eigen::Ref<const EigenTimeSeries>

using TimeseriesDistanceFunction = std::function<double(const TimeseriesDistanceFunctionData&)>: The signature to use for a distance function.

struct TimeseriesDistanceFunctionData

#include <segmentation.hpp>

The data object passed to time series distance functions.

Public Members

EigenTimeSeriesConstRef ts1

EigenTimeSeriesConstRef ts2

double norm1

double norm2

struct ObjectByChange

#include <segmentation.hpp>

Basic data structure for 4D change object.

Public Members

std::unordered_map<IndexType, double> indices_distances

IndexType start_epoch

IndexType end_epoch

double threshold

struct RegionGrowingSeed

Public Members

IndexType index

IndexType start_epoch

IndexType end_epoch

struct RegionGrowingAlgorithmData

Public Members

EigenSpatiotemporalArrayConstRef distances

const Epoch &corepoints

double radius

RegionGrowingSeed seed

std::vector<double> thresholds

std::size_t min_segments

std::size_t max_segments

struct ChangePointDetectionData

Public Members

EigenTimeSeriesConstRef ts

IndexType window_width

IndexType min_size

IndexType jump

double penalty

namespace py4dgeo

Typedefs

using Transformation = Eigen::Transform<double, 3, Eigen::Affine>: The type that used for affine transformations on point clouds.

class DisjointSet

#include <registration.hpp>

Union/Find data structure

Public Functions

DisjointSet(IndexType size): Construct the data structure for a given size.

IndexType Find(IndexType i) const: Find the subset identifier that the i-th element currently belongs to.

IndexType Union(IndexType i, IndexType j, bool balance_sizes)

Merge two subsets into one.

Parameters:

i – First subset identifier to merge
j – Second subset identifier to merge
balance_sizes – If true, the large subset is merged into the smaller.

Returns:

The subset identifier of the merged subset

Private Members

IndexType size_: The number of points in the data structure.

std::vector<IndexType> numbers_: The subset sizes.

mutable std::vector<IndexType> subsets_: The subset index for all our points.

class CallbackExceptionVault

#include <openmp.hpp>

A container to handle exceptions in parallel regions.

OpenMP does have limited support for C++ exceptions in parallel regions: Exceptions need to be catched on the same thread they have been thrown on. This class allows to store the first thrown exception to then rethrow it after we left the parallel region. This is a necessary construct to propagate exceptions from Python callbacks through the multithreaded C++ layer back to the calling Python scope. Inspiration is taken from: https://stackoverflow.com/questions/11828539/elegant-exceptionhandling-in-openmp

Public Functions

template<typename Function, typename ...Parameters> inline void run(Function &&f, Parameters&&... parameters)

inline void rethrow() const

Private Members

std::exception_ptr ptr = nullptr