A Bounding Volume Hierarchy tree for efficient spatial querying of line segments. More...

#include <river_sss.h>

Public Types
using	line_type = FVLineSourceOrSink< dim, TLineData >

Public Member Functions
void	build (std::vector< SmartPtr< line_type > > &lines)
	Builds the BVH from a vector of line segments.

void	query (const AABox< MathVector< dim > > &box, std::vector< size_t > &out) const
	Finds all line segments whose bounding boxes potentially overlap with the query box.

Private Member Functions
SmartPtr< LineBVHNode< dim > >	build_node (std::vector< SmartPtr< line_type > > &lines, std::vector< size_t > &ids, int depth)
	Internal recursive function to build the tree nodes.

void	query_node (const LineBVHNode< dim > *node, const AABox< MathVector< dim > > &box, std::vector< size_t > &out) const
	Internal recursive function for spatial querying.

Private Attributes
SmartPtr< LineBVHNode< dim > >	m_root

Detailed Description

template<int dim, typename TLineData>
class ug::d3f::LineBVHTree< dim, TLineData >

A Bounding Volume Hierarchy tree for efficient spatial querying of line segments.

The tree is built by recursively splitting the set of lines along the longest axis of their combined bounding box. This reduces spatial query complexity from O(N) to O(log N).

Member Typedef Documentation

◆ line_type

template<int dim, typename TLineData >

using ug::d3f::LineBVHTree< dim, TLineData >::line_type = FVLineSourceOrSink<dim, TLineData>

Member Function Documentation

◆ build()

template<int dim, typename TLineData >

void ug::d3f::LineBVHTree< dim, TLineData >::build ( std::vector< SmartPtr< line_type > > & lines )

inline

Builds the BVH from a vector of line segments.

References ug::d3f::LineBVHTree< dim, TLineData >::build_node(), and ug::d3f::LineBVHTree< dim, TLineData >::m_root.

◆ build_node()

template<int dim, typename TLineData >

SmartPtr< LineBVHNode< dim > > ug::d3f::LineBVHTree< dim, TLineData >::build_node	(	std::vector< SmartPtr< line_type > > &	lines,
		std::vector< size_t > &	ids,
		int	depth
	)

inlineprivate

Internal recursive function to build the tree nodes.

References ug::d3f::LineBVHTree< dim, TLineData >::build_node(), and make_sp().

Referenced by ug::d3f::LineBVHTree< dim, TLineData >::build(), and ug::d3f::LineBVHTree< dim, TLineData >::build_node().

◆ query()

template<int dim, typename TLineData >

void ug::d3f::LineBVHTree< dim, TLineData >::query	(	const AABox< MathVector< dim > > &	box,
		std::vector< size_t > &	out
	)		const

inline

Finds all line segments whose bounding boxes potentially overlap with the query box.

Parameters

box	The query AABox.
out	Vector to be filled with indices of candidate line segments.

References ug::d3f::LineBVHTree< dim, TLineData >::m_root, and ug::d3f::LineBVHTree< dim, TLineData >::query_node().

◆ query_node()

template<int dim, typename TLineData >

void ug::d3f::LineBVHTree< dim, TLineData >::query_node	(	const LineBVHNode< dim > *	node,
		const AABox< MathVector< dim > > &	box,
		std::vector< size_t > &	out
	)		const