Geometric clustering

Builder

template<typename T>
class ClusterTreeBuilder

a ClusterTreeBuilder object encapsulates the parameters and strategies to create Cluster objects.

Template Parameters:

T –

Public Functions

inline void set_maximal_leaf_size(int maximal_leaf_size)

inline void set_is_complete(bool is_complete)

inline void set_partitioning_strategy(std::shared_ptr<VirtualPartitioning<T>> partitioning_strategy)

Cluster<T> create_cluster_tree(int number_of_points, int spatial_dimension, const T *coordinates, const T *radii, const T *weights, int number_of_children, int size_of_partition, const int *partition) const

It performs a hierarchical partitioning of the geometry defined with coordinates using the VirtualPartitioning strategy contained in the ClusterTreeBuilder object. Each geometric point is associated with a weight and a radius, which are used to compute the radius and center of each cluster node. A special level of the cluster tree, called level of partition, can be customized, either by its size or its content.

Parameters:

• number_of_points – [in]

• spatial_dimension – [in]

• coordinates – [in] is a column-major T array of dimension spatial_dimension x number_of_points, corresponding to the geometric points.

• radii – [in] is a T array of dimension number_of_points

• weights – [in] is a T array of dimension number_of_points

• number_of_children – [in] specifies the number of children in the cluster tree, except for the parent of the level of partition.

• size_of_partition – [in] specifies the number of cluster node on the level of partition.

• partition – [in] is an integer array of size 2 x size_of_partition. Pairs of (offset,size) for each cluster node on the level of partition.

Returns:

Cluster root of the cluster tree

inline Cluster<T> create_cluster_tree(int number_of_points, int spatial_dimension, const T *coordinates, int number_of_children, int size_of_partition) const

Same as main constructor but defaults weights and radiis and defines the partition automatically using the contained VirtualPartitioning strategy.

Parameters:

• number_of_points –

• spatial_dimension –

• coordinates –

• number_of_children –

• size_of_partition –

Returns:

Cluster root of the cluster tree

inline Cluster<T> create_cluster_tree(int number_of_points, int spatial_dimension, const T *coordinates, int number_of_children, int size_of_partition, const int *partition) const

Same as main constructor but defaults weights and radiis.

Parameters:

• number_of_points –

• spatial_dimension –

• coordinates –

• number_of_children –

• size_of_partition –

• partition –

Returns:

Cluster root of the cluster tree

Cluster

template<typename CoordinatesPrecision>
class Cluster : public htool::TreeNode<Cluster<CoordinatesPrecision>, ClusterTreeData<CoordinatesPrecision>>

Public Functions

inline Cluster(CoordinatesPrecision radius, std::vector<CoordinatesPrecision> &center, int rank, int offset, int size)

inline Cluster(const Cluster &parent, CoordinatesPrecision radius, std::vector<CoordinatesPrecision> &center, int rank, int offset, int size, int counter, bool is_on_partition)

Cluster(const Cluster&) = delete

Cluster &operator=(const Cluster&) = delete

Cluster(Cluster &&cluster) noexcept = default

Cluster &operator=(Cluster &&cluster) noexcept = default

virtual ~Cluster() = default

inline const CoordinatesPrecision &get_radius() const

inline const std::vector<CoordinatesPrecision> &get_center() const

inline int get_rank() const

inline int get_offset() const

inline int get_size() const

inline int get_counter() const

inline bool is_permutation_local() const

inline unsigned int get_maximal_depth() const

inline unsigned int get_minimal_depth() const

inline unsigned int get_maximal_leaf_size() const

inline const std::vector<const Cluster<CoordinatesPrecision>*> &get_clusters_on_partition() const

inline const Cluster<CoordinatesPrecision> &get_cluster_on_partition(size_t index) const

inline const Cluster<CoordinatesPrecision> &get_root_cluster() const

inline const std::vector<int> &get_permutation() const

inline std::vector<int> &get_permutation()

inline void set_is_permutation_local(bool is_permutation_local)

inline void set_minimal_depth(unsigned int minimal_depth)

inline void set_maximal_depth(unsigned int maximal_depth)

inline void set_maximal_leaf_size(unsigned int maximal_leaf_size)

inline bool operator==(const Cluster<CoordinatesPrecision> &rhs) const

Partitioning interface

template<typename CoordinatePrecision>
class VirtualPartitioning

Subclassed by htool::Partitioning< CoordinatePrecision, ComputationDirectionPolicy, SplittingPolicy >

Public Functions

virtual std::vector<std::pair<int, int>> compute_partitioning(Cluster<CoordinatePrecision> &current_cluster, int spatial_dimension, const CoordinatePrecision *coordinates, const CoordinatePrecision *const radii, const CoordinatePrecision *const weights, int number_of_partitions) = 0

inline virtual ~VirtualPartitioning()

template<typename CoordinatePrecision, typename ComputationDirectionPolicy, typename SplittingPolicy>
class Partitioning : public htool::VirtualPartitioning<CoordinatePrecision>

Strategy to define a new splitting for a given cluster. It is based on ComputationDirectionPolicy which defines a strategy to compute the main directions of a given cluster, and SplittingPolicy which defines a strategy to split the cluster using these directions.

Template Parameters:

• CoordinatePrecision –

• ComputationDirectionPolicy –

• SplittingPolicy –

Public Functions

inline virtual std::vector<std::pair<int, int>> compute_partitioning(Cluster<CoordinatePrecision> &current_cluster, int spatial_dimension, const CoordinatePrecision *coordinates, const CoordinatePrecision *const radii, const CoordinatePrecision *const weights, int number_of_partitions) override

It returns number_of_partitions pairs of (offset,size) defining a new splitting of the current cluster, and it updates the permutation stored in current_cluster to make this new splitting contiguous. If number_of_partitions is equal to two to the spatial_dimension power, it will split in two using SplittingPolicy along the main directions computed with ComputationDirectionPolicy. Otherwise, it will only split number_of_partition along the main direction.

Parameters:

• current_cluster –

• spatial_dimension –

• coordinates –

• radii –

• weights –

• number_of_partitions –

Returns:

Direction computation strategies

template<typename T>
class ComputeLargestExtent

It computes the main directions of a cluster by computing the eigenvectors of the covariance matrix.

Template Parameters:

T –

Public Static Functions

static inline Matrix<T> compute_direction(const Cluster<T> &cluster, int spatial_dimension, const T *const coordinates, const T*const, const T *const weights)

template<typename T>
class ComputeBoundingBox

It computes the main directions of a cluster by choosing the x/y/z axis containing its largest extent in descreasing order.

Template Parameters:

T –

Public Static Functions

static inline Matrix<T> compute_direction(const Cluster<T> &cluster, int spatial_dimension, const T *const coordinates, const T*const, const T*const)

Splitting strategies

template<typename T>
class GeometricSplitting

It splits in a given number of partitions of near-equal geometric size along a specific direction.

Template Parameters:

T –

Public Static Functions

static inline std::vector<std::pair<int, int>> splitting(int offset, int size, int spatial_dimension, const T *const coordinates, const std::vector<int> &permutation, const std::vector<T> &direction, int number_of_partition)

template<typename T>
class RegularSplitting

It splits in a given number of partitions of near-equal number of elements.

Template Parameters:

T –

Public Static Functions

static inline std::vector<std::pair<int, int>> splitting(int offset, int size, int, const T*const, const std::vector<int>&, const std::vector<T>&, int number_of_partition)

Visualisation

template<typename CoordinatesPrecision>
void htool::save_clustered_geometry(const Cluster<CoordinatesPrecision> &cluster_tree, int spatial_dimension, const CoordinatesPrecision *x0, std::string filename, const std::vector<int> &depths)