Spatial Partitioning: User Manual

Table of Contents

• Introduction
  • Datastructures
  • Queries
• KdTree
  • Specifications
  • Basic usage
    • Construction
    • Queries
    • Samples and indexing
  • Extending KdTree
  • Usage of the convenience classes KdTree and KdTreeBase
• KnnGraph
  • Basic usage
    • Construction
    • Queries

[Go back to user manual]

Introduction

This module provides spatial datastructures to speed up spatial queries (e.g., neighbors search).

Datastructures

• Ponca::KdTreeDense and Ponca::KdTreeSparse: binary search trees (https://en.wikipedia.org/wiki/K-d_tree). Both classes inherit from Ponca::KdTree.
• Ponca::KnnGraph : a nearest neighbor graph (https://en.wikipedia.org/wiki/Nearest_neighbor_graph). Constructed from a Ponca::KdTree.

All datastructures are available in arbitrary dimensions.

Queries

Ponca queries are defined according to their input type (QueryInputIsIndex, or QueryInputIsPosition) and their output type (closest point with QueryOutputIsNearest, k-neighborhood with QueryOutputIsKNearest, and range neighborhood with QueryOutputIsRange):

QueryType	Closest Point	k-neighborhood	Range neighborhood
Index	NearestIndexQuery	KNearestIndexQuery	RangeIndexQuery
Coordinate	NearestPointQuery	KNearestPointQuery	RangePointQuery

These classes provide a consistent API for all datastructures, where the results are exposed as Range and thus accessed through iterators, ie.:

#pragma omp parallel for
for (int i = 0; i < nbVert; ++i) // for all the vertices of the point cloud
  for (int neiId : myDataStructure.k_nearest_neighbors(i, k)) // collect k-nearest neighbors
  {
    // process neighbor at index neiId
  }

Note

As queries are objets that are independent from the datastructure, they can be created and used in parallel from multiple threads. The queries are always constructed by the datastructure.

Thanks to the iterator formalism, queries can be seamlessly combined with Basket::computeWithIds:

Fit fit;
fit.setWeightFunc(MyWeightFunc(scale));
fit.init(fitInitPos);
fit.computeWithIds( myDataStructure.range_neighbors(fitInitPos, scale), vectorPoints );

Warning

Queries from an index (NearestIndexQuery, KNearestIndexQuery and RangeIndexQuery) do not iterate on the queried index.

KdTree

Specifications

In Ponca, the kd-tree is a binary search tree that

• is balanced (cuts at the median at each node),
• cuts along the dimension that extends the most at each node,
• has a maximal depth (KdTreeBase::MAX_DEPTH),
• has a minimal number of points per leaf (KdTreeBase::m_min_cell_size),
• only stores points in the leafs,
• uses depth-first search with a static stack for queries,
• keeps the initial order of points.

Basic usage

The class Ponca::KdTreeDense provides methods to construct a tree and query points neighborhoods. The class Ponca::KdTreeSparse provides the same functionalities as its dense counterpart, but allows construction from a subset of points. They both share the same API with their abstract base class KdTree.

Construction

As for the other modules, the point type is defined by a template parameter DataPoint. At construction time, the coordinates are copied in the tree from a container provided by the caller. For instance, to generate a tree from a random point cloud:

    auto points = VectorContainer(N);
    std::generate(points.begin(), points.end(), []() {return DataPoint(VectorType::Random()); });
 
    KdTreeDense<DataPoint> structure(points);

For convenience, it is possible to convert the custom input points to DataPoint using a converter.

When using a Ponca::KdTreeSparse, it is possible to provide a set of indices to sample a subset of the input point during the construction. Here, to randomly select half of the points:

    std::vector<int> indices(N);
    std::vector<int> sampling(N / 2);
    std::iota(indices.begin(), indices.end(), 0);
    std::sample(indices.begin(), indices.end(), sampling.begin(), N / 2, std::mt19937(seed));
 
    KdTreeSparse<DataPoint> structure(points, sampling);

Queries

As for other datastructures, queries are objects generated by the KdTree, and are designed as Range: accessing the neighbors requires to iterate over the query. Here an example from the test suite, where the indices returned from the queries are compared with an explicit search

    Ponca::KdTreeDense<DataPoint> kdTree(points);
 
#pragma omp parallel for
    for (int i = 0; i < N; ++i)
    {
        std::vector<int> results; results.reserve( k );
        for (int j : kdTree.k_nearest_neighbors(i, k))
        {
            results.push_back(j);
        }
 
        bool res = check_k_nearest_neighbors<Scalar, VectorContainer>(points, i, k, results);
        VERIFY(res);
    }

Several query types are provided (see KdTreeBase for related method list):

• KdTreeKNearestQueryBase, specialized by KdTreeKNearestIndexQuery and KdTreeKNearestPointQuery
• KdTreeNearestQueryBase, specialized by KdTreeNearestIndexQuery and KdTreeNearestPointQuery
• KdTreeRangeQueryBase, specialized by KdTreeRangeIndexQuery and KdTreeRangePointQuery

Several KdTree queries are illustrated in the example Ponca::KdTree neighbor searches. KdTree usage is also demonstrated both in tests and examples:

• tests/src/basket.cpp
• tests/src/queries_knearest.cpp
• tests/src/queries_nearest.cpp
• tests/src/queries_range.cpp
• examples/cpp/nanoflann/ponca_nanoflann.cpp

Samples and indexing

There are two main ways of iterating over a KdTree: over points or over samples. Points are the underlying data storage, which the KdTree does not modify, while samples are a set of indices into the point storage that the KdTree reorders internally when it is constructed to keep track of spatial partitions.

We call indices into the underlying point storage point indices and indices into the sample storage sample indices. Note that the sample storage stores point indices: sample number 0 may, for example, refer to point number 25. The point storage can be accessed with KdTreeBase::points, while the array of samples can be accessed with KdTreeBase::samples.

While most of the KdTree API is built on using point indices, it can still be useful to iterate over samples instead (e.g. when using a Ponca::KdTreeSparse). If you ever need to convert sample indices to point indices, see KdTreeBase::pointFromSample (see also KdTreeBase::pointDataFromSample).

Extending KdTree

The trees can be customized using Traits, to change containers and nodes types. KdTreeDefaultTraits provides general-purpose Traits that fit most usages, and is directly used by Ponca::KdTree, Ponca::KdTreeDense and Ponca::KdTreeSparse:

template <typename DataPoint>
struct KdTree : public Ponca::KdTreeBase<KdTreeDefaultTraits<DataPoint>>{};

template <typename DataPoint>
struct KdTreeDense : public Ponca::KdTreeDenseBase<KdTreeDefaultTraits<DataPoint>>{};

template <typename DataPoint>
struct KdTreeSparse : Ponca::KdTreeSparseBase<KdTreeDefaultTraits<DataPoint>>{};

To use your own type of Traits, see KdTreeDefaultTraits and KdTreeCustomizableNode APIs. See also:

• examples/cpp/ponca_customize_kdtree.cpp

Usage of the convenience classes KdTree and KdTreeBase

KdTree provides the common interface of KdTreeDense and KdTreeSparse. This class can be used to store or pass references/pointers that can be of either child type, see for instance:

    // Abstract pointer type that can receive KdTreeSparse or KdTreeDense objects
    KdTree<DataPoint> *kdtree {nullptr};

        // assign sparse
        kdtree = new KdTreeSparse<DataPoint> (points, sampling);

        // assign dense
        kdtree = new KdTreeDense<DataPoint> (points);

KdTreeBase provides the same abstraction for arbitrary types of traits. When the type of Traits is not restricted, it is recommended to use KdTreeBase to declare functions parameters or variables. In this example:

    const KdTreeBase<Traits>* m_kdtree { nullptr };

the variable m_kdtree can be either dense or sparse, and have any type of Traits.

KnnGraph

Basic usage

The class Ponca::KnnGraph provides methods to construct a neighbor graph and query points neighborhoods.

Construction

The graph is constructed from an existing KdTree, and the point collection is accessed through it (with no copy). Here an example from the test-suite where a graph is constructed, where only closest neighbors are connected:

    Ponca::KnnGraph<DataPoint> knnGraph(kdTree, 1);

Warning

At the moment, a KnnGraph can only be constructed from a Ponca::KdTreeDense. This will change in a future release.

Queries

As for other datastructures, queries are objects generated by KdTrees, and are designed as Range: accessing the neighbors requires to iterate over the query.

    Ponca::KnnGraph<DataPoint> knnGraph(kdTree, k);
#pragma omp parallel for
    for (int i = 0; i < N; ++i)
    {
        std::vector<int> results; results.reserve( k );
        for (int j : knnGraph.k_nearest_neighbors(i))
        {
            results.push_back(j);
        }
 
        bool res = check_k_nearest_neighbors<Scalar, VectorContainer>(points, i, k, results);
        VERIFY(res);
    }

Note

By construction, the KnnGraph can be queried only from an index.

Two types of queries are provided (see KnnGraphBase for related method list):

• KnnGraphRangeQuery
• KnnGraphKNearestQuery: the number of neighbors is defined at construction-time: a k-neighbor graph gives access to k-neighborhoods only.

  Note

  The query KnnGraphNearestQuery does not need to exist explicitly as it boils down to KnnGraphKNearestQuery with k=1.

  [Go back to user manual]