PatchSkdTree is the class that implements a spatial kd-tree (skd-tree) a bitpit patch. More...

Inheritance diagram for bitpit::PatchSkdTree:

[legend]

Collaboration diagram for bitpit::PatchSkdTree:

[legend]

Public Member Functions
bool	areLookupsThreadSafe () const

void	build (std::size_t leaftThreshold=1, bool squeezeStorage=false)

void	clear (bool release=false)

void	enableThreadSafeLookups (bool enable)

std::size_t	evalMaxDepth (std::size_t rootId=0) const

std::size_t	getLeafCount () const

std::size_t	getLeafMaxCellCount () const

std::size_t	getLeafMinCellCount () const

const SkdNode &	getNode (std::size_t nodeId) const

std::size_t	getNodeCount () const

const SkdBox &	getPartitionBox (int rank) const

const PatchKernel &	getPatch () const

Protected Member Functions
	PatchSkdTree (const PatchKernel *patch, bool interiorCellsOnly=false)

SkdNode &	_getNode (std::size_t nodeId)

void	freeCommunicator ()

const MPI_Comm &	getCommunicator () const

bool	isCommunicatorSet () const

void	setCommunicator (MPI_Comm communicator)

Protected Attributes
std::vector< std::size_t >	m_cellRawIds

MPI_Comm	m_communicator

bool	m_interiorCellsOnly

std::size_t	m_nLeafs

std::size_t	m_nMaxLeafCells

std::size_t	m_nMinLeafCells

std::vector< SkdNode >	m_nodes

int	m_nProcessors

std::vector< SkdBox >	m_partitionBoxes

SkdPatchInfo	m_patchInfo

int	m_rank

bool	m_threadSafeLookups

Detailed Description

PatchSkdTree is the class that implements a spatial kd-tree (skd-tree) a bitpit patch.

Spatial kd-tree is a spatial access method presented bt Ooi et al. where successive levels are split along different dimensions. Tke skd-tree was proposed to handle spatial obects with extension, which could not be handled by the original kd-tree. Skd-trees belong to the Bounding Volume Hierarchy (BVH) class of geometric search structures. Bounding volume hierarchies come in many variations: swept spheres, OBB-trees, sphere trees, and skd-trees are all examples.

Each node of a skd-tree structure contains a bounding volume for some subset of the initial geometry. The nodes are generally arranged in an oriented tree, where child nodes bound non-empty subsets of their parents’ geometry. Nodes with no children are called leaves.

The bounding volumes are selected to minimize the cost of query operations (e.g. proximity, intersection, or containment) while providing a close fit to the underlying geometry.

Analyzing the asymptotic behavior of skd-trees is difficult. In the best case, skd-tree queries can be answered in constant time. In the worst case, each node of the tree may have to be visited, leading to O(n) work for the example of a binary tree with n leaf nodes. On average, the effort for intersection testing queries appears to be O(log2 n), while nearest features queries appear to be considerably cheaper than O(n).

See:

Deterministic point inclusion methods for computational applications with complex geometry, Ahmed Khamayseh and Andrew Kuprat. Computational Science & Discovery, Volume 1, Number 1, 2008. [This paper contains the algorithms for building the skd-tree and for performing closest cell queries.]

Efficient Query Processing in Geographic Information Systems (Lecture Notes in Computer Science vol 471), Ooi B. C., 1990.

A comparative study of spatial indexing techniques for multidimensional scientific datasets, Beomseok Nam and Alan Sussman Nam, International Conference on Scientific and Statistical Database Management, 2004.

Definition at line 174 of file patch_skd_tree.hpp.

Constructor & Destructor Documentation

◆ PatchSkdTree()

bitpit::PatchSkdTree::PatchSkdTree	(	const PatchKernel *	patch,
		bool	interiorCellsOnly = false )

protected

Constructor.

Parameters

patch	is the patch that will be use to build the tree
interiorCellsOnly	if set to true, only interior cells will be considered

Definition at line 1023 of file patch_skd_tree.cpp.

Member Function Documentation

◆ _getNode()

SkdNode & bitpit::PatchSkdTree::_getNode ( std::size_t nodeId )

protected

Get a reference to the specified node.

Parameters

nodeId is the id of the node

Returns: A reference to the specified node.

Definition at line 1240 of file patch_skd_tree.cpp.

◆ areLookupsThreadSafe()

bool bitpit::PatchSkdTree::areLookupsThreadSafe ( ) const

Check if tree lookups are thread safe.

Returns: Returns true if tree lookups are thread safe, false otherwise.

Definition at line 1409 of file patch_skd_tree.cpp.

◆ build()

void bitpit::PatchSkdTree::build	(	std::size_t	leafThreshold = 1,
		bool	squeezeStorage = false )

Build the tree.

Leaf nodes will contain a number of "characteristic positions" that is less or equal than the specified threshold. Given a parent node, new children are generated divinding the cells of the parent node in two subset. For each cell, a characteristic position is evaluated (i.e., the centrooid of the bounding box) and this characteristic position is used to sort the cells. The weighted average of the characteristics positions of all the cells of the parent will be used as a split threshold. Different cells may have the same characteristics position and all the cells with the same characteristic position will be clustered in the same leaf node. The threshold below which a node is considered a leaf, is compared with the number of characterisic positions containd in the node, not with the number of cell it contains. When there are cells with the same characteristic position, a node may contain a number of cells that is greater than the leaf threshold.

Parameters

	leafThreshold	is the maximum number of "characteristic positions" a node can contain to be considered a leaf
[in]	squeezeStorage	if set to true tree data structures will be squeezed after the build

Definition at line 1079 of file patch_skd_tree.cpp.

◆ clear()

void bitpit::PatchSkdTree::clear ( bool release = false )

Clear the tree.

Parameters

release if it's true the memory hold by the tree will be released, otherwise the treewill be cleared but its memory will not be relased

Definition at line 1169 of file patch_skd_tree.cpp.

◆ enableThreadSafeLookups()

void bitpit::PatchSkdTree::enableThreadSafeLookups ( bool enable )

Set if the tree lookups should be thread safe.

Parameters

enable if set to true the lookups will be thread safe.

Definition at line 1399 of file patch_skd_tree.cpp.

◆ evalMaxDepth()

std::size_t bitpit::PatchSkdTree::evalMaxDepth ( std::size_t rootId = 0 ) const

Evaluate the maximum depth of the tree.

Parameters

rootId is the id of the root node

Returns: The maximum depth of the tree.

Definition at line 1251 of file patch_skd_tree.cpp.

◆ freeCommunicator()

void bitpit::PatchSkdTree::freeCommunicator ( )

protected

Free the MPI communicator

Definition at line 1448 of file patch_skd_tree.cpp.

◆ getCommunicator()

const MPI_Comm & bitpit::PatchSkdTree::getCommunicator ( ) const

protected

Gets the MPI communicator associated to the patch.

Returns: The MPI communicator associated to the patch.

Definition at line 1479 of file patch_skd_tree.cpp.

◆ getLeafCount()

std::size_t bitpit::PatchSkdTree::getLeafCount ( ) const

Get the number of leafs contained in the tree.

Returns: The number of nodes contained in the tree.

Definition at line 1218 of file patch_skd_tree.cpp.

◆ getLeafMaxCellCount()

std::size_t bitpit::PatchSkdTree::getLeafMaxCellCount ( ) const

Gets the maximum number of elements contained in a leaf.

Returns: Get the maximum number of elements contained in a leaf.

Definition at line 1051 of file patch_skd_tree.cpp.

◆ getLeafMinCellCount()

std::size_t bitpit::PatchSkdTree::getLeafMinCellCount ( ) const

Gets the minimum number of elements contained in a leaf.

Returns: Get the minimum number of elements contained in a leaf.

Definition at line 1041 of file patch_skd_tree.cpp.

◆ getNode()

const SkdNode & bitpit::PatchSkdTree::getNode ( std::size_t nodeId ) const

Get a constant reference to the specified node.

Parameters

nodeId is the id of the node

Returns: A constant reference to the specified node.

Definition at line 1229 of file patch_skd_tree.cpp.

◆ getNodeCount()

std::size_t bitpit::PatchSkdTree::getNodeCount ( ) const

Get the number of nodes contained in the tree.

Returns: The number of nodes contained in the tree.

Definition at line 1208 of file patch_skd_tree.cpp.

◆ getPartitionBox()

const SkdBox & bitpit::PatchSkdTree::getPartitionBox ( int rank ) const

Get the bounding box associated to a partition.

Parameters

[in] rank is the ndex of the rank owner of the target partition

Returns: The bounding box associated to the partition.

Definition at line 1527 of file patch_skd_tree.cpp.

◆ getPatch()

const PatchKernel & bitpit::PatchSkdTree::getPatch ( ) const

Get a constant reference to the patch associated to the tree.

Returns: A a constant reference to the patch associated to the tree.

Definition at line 1198 of file patch_skd_tree.cpp.

◆ isCommunicatorSet()

bool bitpit::PatchSkdTree::isCommunicatorSet ( ) const

protected

Checks if the communicator to be used for parallel communications has already been set.

Returns: Returns true if the communicator has been set, false otherwise.

Definition at line 1469 of file patch_skd_tree.cpp.

◆ setCommunicator()

void bitpit::PatchSkdTree::setCommunicator ( MPI_Comm communicator )

protected

Sets the MPI communicator to be used for parallel communications.

Parameters

communicator is the communicator to be used for parallel communications.

Definition at line 1421 of file patch_skd_tree.cpp.

Member Data Documentation

◆ m_cellRawIds

std::vector<std::size_t> bitpit::PatchSkdTree::m_cellRawIds

protected

Definition at line 203 of file patch_skd_tree.hpp.

◆ m_communicator

MPI_Comm bitpit::PatchSkdTree::m_communicator

protected

Definition at line 218 of file patch_skd_tree.hpp.

◆ m_interiorCellsOnly

bool bitpit::PatchSkdTree::m_interiorCellsOnly

protected

Definition at line 211 of file patch_skd_tree.hpp.

◆ m_nLeafs

std::size_t bitpit::PatchSkdTree::m_nLeafs

protected

Definition at line 205 of file patch_skd_tree.hpp.

◆ m_nMaxLeafCells

std::size_t bitpit::PatchSkdTree::m_nMaxLeafCells

protected

Definition at line 207 of file patch_skd_tree.hpp.

◆ m_nMinLeafCells

std::size_t bitpit::PatchSkdTree::m_nMinLeafCells

protected

Definition at line 206 of file patch_skd_tree.hpp.

◆ m_nodes

std::vector<SkdNode> bitpit::PatchSkdTree::m_nodes

protected

Definition at line 209 of file patch_skd_tree.hpp.

◆ m_nProcessors

int bitpit::PatchSkdTree::m_nProcessors

protected

Definition at line 217 of file patch_skd_tree.hpp.

◆ m_partitionBoxes

std::vector<SkdBox> bitpit::PatchSkdTree::m_partitionBoxes

protected

Definition at line 219 of file patch_skd_tree.hpp.

◆ m_patchInfo

SkdPatchInfo bitpit::PatchSkdTree::m_patchInfo

protected

Definition at line 202 of file patch_skd_tree.hpp.

◆ m_rank

int bitpit::PatchSkdTree::m_rank

protected

Controls if the tree lookups should be thread safe

Definition at line 216 of file patch_skd_tree.hpp.

◆ m_threadSafeLookups

bool bitpit::PatchSkdTree::m_threadSafeLookups

protected

Definition at line 213 of file patch_skd_tree.hpp.

The documentation for this class was generated from the following files:

src/patchkernel/patch_skd_tree.hpp
src/patchkernel/patch_skd_tree.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ PatchSkdTree()

Member Function Documentation

◆ _getNode()

◆ areLookupsThreadSafe()

◆ build()

◆ clear()

◆ enableThreadSafeLookups()

◆ evalMaxDepth()

◆ freeCommunicator()

◆ getCommunicator()

◆ getLeafCount()

◆ getLeafMaxCellCount()

◆ getLeafMinCellCount()

◆ getNode()

◆ getNodeCount()

◆ getPartitionBox()

◆ getPatch()

◆ isCommunicatorSet()

◆ setCommunicator()

Member Data Documentation

◆ m_cellRawIds

◆ m_communicator

◆ m_interiorCellsOnly

◆ m_nLeafs

◆ m_nMaxLeafCells

◆ m_nMinLeafCells

◆ m_nodes

◆ m_nProcessors

◆ m_partitionBoxes

◆ m_patchInfo

◆ m_rank

◆ m_threadSafeLookups