A point location query in domains with global coordinate dimension dc and local coordinate dimension db. implemented using a 2^DC tree search structure. Efficient for non-compact domains. More...

#include <d_tree_point_locator.h>

Inheritance diagram for geometry::d_tree_point_locator< DC, DB >:

Friends
class	d_tree_point_locator_node< DC, DB >

D_TREE_POINT_LOCATOR FACET
ptr_linked_pool< d_tree_point_locator_node< DC, DB > >	_node_pool
	Pool for efficiently allocating and deallocating nodes. More...

d_tree_point_locator_node< DC, DB >	_root
	The root node of the tree. More...

size_type	_depth
	The number of levels in the tree; the length of the longest path from the root to a leaf. More...

	d_tree_point_locator (sec_ed &xcoords, size_type xdepth)
	Creates an instance for coordinate section xcoords with depth xdepth. More...

	d_tree_point_locator (sec_ed &xcoords)
	Creates an instance for coordinate section xcoords with depth computed from the size of the mesh. More...

virtual	~d_tree_point_locator ()
	Destructor. More...

const d_tree_point_locator_node< DC, DB > &	root () const
	The root node. More...

size_type	depth () const
	The number of levels; the length of the longest path from root() to a leaf. More...

size_type	size ()
	The number of nodes in the tree. More...

size_type	capacity ()
	The nodes allocated for use by the tree. More...

static size_type	max_depth ()
	The maximum representable number of levels. More...

static size_type &	default_depth ()
	The default depth; the depth of a instance created with the default constructor. More...

	d_tree_point_locator ()
	Default constructor; disabled. More...

	d_tree_point_locator (const d_tree_point_locator< DC, DB > &xother)
	Copy constructor; disabled. More...

virtual d_tree_point_locator &	operator= (const point_locator &xother)
	Assignment operator; disabled. More...

d_tree_point_locator &	operator= (const d_tree_point_locator< DC, DB > &xother)
	Assignment operator; disabled. More...

void	update_bins ()
	Updates the tree bin parameters. More...

ptr_linked_pool< d_tree_point_locator_node< DC, DB > > &	node_pool ()
	Pool for efficiently allocating and deallocating nodes. More...

D_BIN_POINT_LOCATOR FACET
typedef singly_linked_list< const d_bounding_box< DC, DB > * >	box_list_type
	The type of box list. More...

virtual void	insert_box (d_bounding_box< DC, DB > *xbox)
	Insert xbox into the tree. More...

virtual void	remove_box (d_bounding_box< DC, DB > *xbox)
	Remove xbox from the tree. More...

virtual const box_list_type &	box_list (sec_vd_value_type *xpt, size_type xpt_ub) const
	The list of bounding boxes which may contain xpt. More...

virtual bool	contains_box (d_bounding_box< DC, DB > *xbox) const
	True if xbox is in the box list of some bin. More...

virtual void	clear ()
	Clear the tree of all bounding boxes and all nodes except the root. More...

POINT_LOCATOR FACET
virtual bool	invariant () const
	Class invariant. More...

Additional Inherited Members
Public Types inherited from geometry::d_bin_point_locator< DC, DB >
typedef singly_linked_list< const d_bounding_box< DC, DB > * >	box_list_type
	The type of box list. More...

Public Member Functions inherited from geometry::d_bin_point_locator< DC, DB >
virtual	~d_bin_point_locator ()
	Destructor. More...

const block< size_type > &	bin_ub () const
	The upper bound for the bin index. More...

const block< sec_vd_value_type > &	bin_size () const
	The dimensions of the smallest bins. More...

size_type	box_ct () const
	The number of bounding boxes stored in the search structure. More...

bool	is_empty () const
	True if this contains no bounding boxes. More...

d_bin_coordinates< DC, DB > *	relative_position (sec_vd_value_type *xpt, size_type xpt_ub) const
	The position of xpt relative to the lower bound, in integer coordinates; auto-allocated version. More...

void	relative_position_pa (sec_vd_value_type *xpt, size_type xpt_ub, d_bin_coordinates< DC, DB > &xresult) const
	The position of xpt relative to the lower bound, in integer coordinates; pre-allocated version. More...

d_bounding_box< DC, DB > *	assign_box (const scoped_index &xmbr_id, const scoped_index &xbranch_id, section_evaluator &xeval, const sec_vd_dof_type *xdofs, size_type xdofs_ct)
	Assigns a box to xmbr_id and initializes it, but does not insert it in the search structure. More...

size_type	box_capacity ()
	The number of boxes that have been allocated. More...

d_bounding_box< DC, DB > *	box (pod_index_type xi)
	The xi-th bounding box. More...

void	update_box (pod_index_type xi, const sec_vd_dof_type *xdofs, size_type xdofs_ct)
	Updates the xi-th bounding box with dofs xdofs. More...

const block< sec_vd_dof_type > &	gathered_dofs () const
	The dofs of gathered by evaluation member. More...

virtual void	update ()
	Updates the search structure to the current values of coordinates(); synonym for update(true);. More...

virtual void	update (bool xpopulate, size_type xeval_capacity)
	Updates the search structure to the current values of coordinates(); if xpopulate, populates the search structure with the eval members coordinates(). Ensures capacity for at least xeval_capacity eval members. More...

virtual void	point_at_value (const sec_vd_value_type *xvalue, size_type xvalue_ub, chart_point &xresult)
	Finds a chart point at which coordinates() has value xvalue. More...

virtual void	all_points_at_value (const sec_vd_value_type *xvalue, size_type xvalue_ub, block< chart_point_3d > &xresult)
	Finds all chart points at which coordinates() has value xvalue and appends them to xresult. Note that charts overlap at their boundaries and hence if xvalue lies on a boundary it is contained in more than one chart. More...

virtual void	branch_points_at_value (const sec_vd_value_type *xvalue, size_type xvalue_ub, block< branch_point_pair > &xresult)
	Finds one chart point in each branch at which coordinates() has value xvalue and appends them to xresult. More...

Public Member Functions inherited from geometry::point_locator
sec_ed &	coordinates () const
	The coordinate section this inverts. More...

const block< sec_vd_value_type > &	lb () const
	The lower bound of the domain defined by coordinates(). More...

const block< sec_vd_value_type > &	ub () const
	The upper bound of the domain defined by coordinates(). More...

int	dc () const
	The spatial dimension of the domain; the dimension of the global coordinates. More...

int	db () const
	The intrinsic dimension of the domain; the dimension of the local coordinates. More...

bool	domain_contains (sec_vd_value_type *xpt, size_type xpt_ub) const
	True if the domain contains xpt. More...

virtual	~point_locator ()
	Destructor. More...

Protected Member Functions inherited from geometry::d_bin_point_locator< DC, DB >
	d_bin_point_locator (sec_ed &xcoords)
	Creates an instance for coordinate section xcoords. More...

	d_bin_point_locator ()
	Default constructor; disabled. More...

	d_bin_point_locator (const d_bin_point_locator< DC, DB > &xother)
	Copy constructor; disabled. More...

d_bin_point_locator &	operator= (const d_bin_point_locator< DC, DB > &xother)
	Assignment operator; disabled. More...

Protected Member Functions inherited from geometry::point_locator
	point_locator ()
	Default constructor. More...

	point_locator (sec_ed &xcoords)
	Create an instance for coordinate section xcoords. More...

void	update_domain ()
	Initializes the domain bounds and dimension. More...

Static Protected Member Functions inherited from geometry::point_locator
static sec_vd_value_type	slightly_greater_than (sec_vd_value_type x)
	A value slightly greater then x. More...

static sec_vd_value_type	slightly_less_than (sec_vd_value_type x)
	A value slightly less then x. More...

Protected Attributes inherited from geometry::d_bin_point_locator< DC, DB >
block< size_type >	_bin_ub
	The upper bound for the bin index. More...

block< sec_vd_value_type >	_bin_size
	The dimensions of the smallest bins. More...

block< sec_vd_value_type >	_one_over_min_bin_size
	Reciprocal of the dimensions of the smallest bins. More...

size_type	_box_ct
	The number of bounding boxes stored in the search structure. More...

block< d_bounding_box< DC, DB > >	_boxes
	Bounding boxes for the evaluation members. More...

block< sec_vd_dof_type >	_gathered_dofs
	The dofs of gathered by evaluation member. More...

eval_iterator	_eval_itr
	The evaluator iterator used to populate the search structure; must have same life time as the search structure because it owns the eval_family which owns the section evaluators. More...

std::set< stl_scoped_index<> >	_branches
	The branches for which a point has already been found for the current evaluation member. Used in all_points_at_value, allocated her to avoid reallocation for each query. More...

Protected Attributes inherited from geometry::point_locator
block< sec_vd_value_type >	_lb
	The lower bound of the domain. More...

block< sec_vd_value_type >	_ub
	The upper bound of the domain. More...

int	_dc
	The spatial dimension of the domain; the dimension of the global coordinates. More...

int	_db
	The intrinsic dimension of the domain; the dimension of the local coordinates. More...

Detailed Description

template<int DC, int DB>
class geometry::d_tree_point_locator< DC, DB >

A point location query in domains with global coordinate dimension dc and local coordinate dimension db. implemented using a 2^DC tree search structure. Efficient for non-compact domains.

Definition at line 57 of file d_tree_point_locator.h.

Member Typedef Documentation

◆ box_list_type

template<int DC, int DB>

typedef singly_linked_list<const d_bounding_box<DC, DB>*> geometry::d_tree_point_locator< DC, DB >::box_list_type

The type of box list.

Definition at line 177 of file d_tree_point_locator.h.

Constructor & Destructor Documentation

◆ d_tree_point_locator() [1/4]

template<int DC, int DB>

geometry::d_tree_point_locator< DC, DB >::d_tree_point_locator	(	sec_ed &	xcoords,
		size_type	xdepth
	)

Creates an instance for coordinate section xcoords with depth xdepth.

Precondition

xcoords.state_is_read_accessible()

xcoords.schema().df() == DC

xdepth <= max_depth()

Definition at line 61 of file d_tree_point_locator.impl.h.

References geometry::d_tree_point_locator< DC, DB >::_depth, geometry::d_tree_point_locator< DC, DB >::d_tree_point_locator(), fiber_bundle::section_space_schema_member::df(), geometry::d_tree_point_locator< DC, DB >::max_depth(), fiber_bundle::sec_rep_space_member::schema(), sheaf::read_write_monitor_handle::state_is_read_accessible(), and geometry::d_bin_point_locator< DC, DB >::update().

◆ d_tree_point_locator() [2/4]

template<int DC, int DB>

geometry::d_tree_point_locator< DC, DB >::d_tree_point_locator ( sec_ed & xcoords )

Creates an instance for coordinate section xcoords with depth computed from the size of the mesh.

Precondition

xcoords.state_is_read_accessible()

xcoords.schema().df() == DC

Definition at line 86 of file d_tree_point_locator.impl.h.

References geometry::d_tree_point_locator< DC, DB >::_depth, fiber_bundle::section_space_schema_member::df(), fiber_bundle::section_space_schema_member::evaluation_ct(), fiber_bundle::sec_at0_algebra::log(), fiber_bundle::sec_rep_space_member::schema(), sheaf::read_write_monitor_handle::state_is_read_accessible(), geometry::d_bin_point_locator< DC, DB >::update(), and geometry::d_tree_point_locator< DC, DB >::~d_tree_point_locator().

◆ ~d_tree_point_locator()

template<int DC, int DB>

geometry::d_tree_point_locator< DC, DB >::~d_tree_point_locator ( )

virtual

Destructor.

Definition at line 118 of file d_tree_point_locator.impl.h.

References geometry::d_tree_point_locator< DC, DB >::root().

Referenced by geometry::d_tree_point_locator< DC, DB >::d_tree_point_locator().

◆ d_tree_point_locator() [3/4]

template<int DC, int DB>

geometry::d_tree_point_locator< DC, DB >::d_tree_point_locator ( )

inlineprotected

Default constructor; disabled.

Definition at line 121 of file d_tree_point_locator.h.

Referenced by geometry::d_tree_point_locator< DC, DB >::d_tree_point_locator().

◆ d_tree_point_locator() [4/4]

template<int DC, int DB>

geometry::d_tree_point_locator< DC, DB >::d_tree_point_locator ( const d_tree_point_locator< DC, DB > & xother )

inlineprotected

Copy constructor; disabled.

Definition at line 126 of file d_tree_point_locator.h.

Member Function Documentation

◆ box_list()

template<int DC, int DB>

const d_tree_point_locator< DC, DB >::box_list_type & geometry::d_tree_point_locator< DC, DB >::box_list	(	sec_vd_value_type *	xpt,
		size_type	xpt_ub
	)		const

virtual

The list of bounding boxes which may contain xpt.

Precondition

xpt != 0

xpt_ub >= this->dc()

this->domain_contains(xpt, xpt_ub)

Implements geometry::d_bin_point_locator< DC, DB >.

Definition at line 396 of file d_tree_point_locator.impl.h.

References geometry::d_tree_point_locator< DC, DB >::_root, geometry::d_tree_point_locator< DC, DB >::contains_box(), geometry::point_locator::dc(), geometry::point_locator::domain_contains(), and geometry::d_bin_point_locator< DC, DB >::relative_position_pa().

Referenced by geometry::d_tree_point_locator< DC, DB >::remove_box().

◆ capacity()

template<int DC, int DB>

size_type geometry::d_tree_point_locator< DC, DB >::capacity ( )

The nodes allocated for use by the tree.

Definition at line 222 of file d_tree_point_locator.impl.h.

References geometry::d_tree_point_locator< DC, DB >::default_depth(), and geometry::d_tree_point_locator< DC, DB >::node_pool().

Referenced by geometry::d_tree_point_locator< DC, DB >::size().

◆ clear()

template<int DC, int DB>

void geometry::d_tree_point_locator< DC, DB >::clear ( )

virtual

Clear the tree of all bounding boxes and all nodes except the root.

Postcondition

this->is_empty()

Implements geometry::d_bin_point_locator< DC, DB >.

Definition at line 448 of file d_tree_point_locator.impl.h.

References geometry::d_bin_point_locator< DC, DB >::_box_ct, geometry::d_tree_point_locator< DC, DB >::_root, geometry::d_tree_point_locator< DC, DB >::invariant(), geometry::d_bin_point_locator< DC, DB >::is_empty(), and geometry::d_tree_point_locator< DC, DB >::node_pool().

Referenced by geometry::d_tree_point_locator< DC, DB >::contains_box().

◆ contains_box()

template<int DC, int DB>

bool geometry::d_tree_point_locator< DC, DB >::contains_box ( d_bounding_box< DC, DB > * xbox ) const

virtual

True if xbox is in the box list of some bin.

Precondition

xbox != 0

Implements geometry::d_bin_point_locator< DC, DB >.

Definition at line 424 of file d_tree_point_locator.impl.h.

References geometry::d_tree_point_locator< DC, DB >::_root, and geometry::d_tree_point_locator< DC, DB >::clear().

Referenced by geometry::d_tree_point_locator< DC, DB >::box_list(), geometry::d_tree_point_locator< DC, DB >::insert_box(), and geometry::d_tree_point_locator< DC, DB >::remove_box().

◆ default_depth()

template<int DC, int DB>

size_type & geometry::d_tree_point_locator< DC, DB >::default_depth ( )

static

The default depth; the depth of a instance created with the default constructor.

Definition at line 248 of file d_tree_point_locator.impl.h.

References geometry::d_tree_point_locator< DC, DB >::update_bins().

Referenced by geometry::d_tree_point_locator< DC, DB >::capacity().

◆ depth()

template<int DC, int DB>

size_type geometry::d_tree_point_locator< DC, DB >::depth ( ) const

The number of levels; the length of the longest path from root() to a leaf.

Postcondition

result > 0

Definition at line 154 of file d_tree_point_locator.impl.h.

References geometry::d_tree_point_locator< DC, DB >::_depth, and geometry::d_tree_point_locator< DC, DB >::max_depth().

Referenced by geometry::d_tree_point_locator< DC, DB >::invariant(), and geometry::d_tree_point_locator< DC, DB >::root().

◆ insert_box()

template<int DC, int DB>

void geometry::d_tree_point_locator< DC, DB >::insert_box ( d_bounding_box< DC, DB > * xbox )

virtual

Insert xbox into the tree.

Precondition

xbox != 0

Postcondition

contains_box(xbox)

this->box_ct() == old_box_ct + 1

Implements geometry::d_bin_point_locator< DC, DB >.

Definition at line 341 of file d_tree_point_locator.impl.h.

References geometry::d_bin_point_locator< DC, DB >::_box_ct, geometry::d_tree_point_locator< DC, DB >::_root, geometry::d_bin_point_locator< DC, DB >::box_ct(), geometry::d_tree_point_locator< DC, DB >::contains_box(), and geometry::d_tree_point_locator< DC, DB >::remove_box().

Referenced by geometry::d_tree_point_locator< DC, DB >::node_pool().

◆ invariant()

template<int DC, int DB>

bool geometry::d_tree_point_locator< DC, DB >::invariant ( ) const

virtual

Class invariant.

Invariant

depth() > 0

this->coordinates().schema().df() == DC

Reimplemented from geometry::d_bin_point_locator< DC, DB >.

Definition at line 477 of file d_tree_point_locator.impl.h.

References geometry::point_locator::coordinates(), and geometry::d_tree_point_locator< DC, DB >::depth().

Referenced by geometry::d_tree_point_locator< DC, DB >::clear(), and geometry::d_tree_point_locator< DC, DB >::root().

◆ max_depth()

template<int DC, int DB>

size_type geometry::d_tree_point_locator< DC, DB >::max_depth ( )

static

The maximum representable number of levels.

Postcondition

result > 0

Definition at line 177 of file d_tree_point_locator.impl.h.

References geometry::d_bin_coordinates< DC, DB >::leftmost_bit_id(), and geometry::d_tree_point_locator< DC, DB >::size().

Referenced by geometry::d_tree_point_locator< DC, DB >::d_tree_point_locator(), and geometry::d_tree_point_locator< DC, DB >::depth().

◆ node_pool()

template<int DC, int DB>

ptr_linked_pool< d_tree_point_locator_node< DC, DB > > & geometry::d_tree_point_locator< DC, DB >::node_pool ( )

protected

Pool for efficiently allocating and deallocating nodes.

Definition at line 315 of file d_tree_point_locator.impl.h.

References geometry::d_tree_point_locator< DC, DB >::_node_pool, and geometry::d_tree_point_locator< DC, DB >::insert_box().

Referenced by geometry::d_tree_point_locator< DC, DB >::capacity(), geometry::d_tree_point_locator< DC, DB >::clear(), geometry::d_tree_point_locator< DC, DB >::size(), and geometry::d_tree_point_locator< DC, DB >::update_bins().

◆ operator=() [1/2]

template<int DC, int DB>

virtual d_tree_point_locator& geometry::d_tree_point_locator< DC, DB >::operator= ( const point_locator & xother )

inlineprotectedvirtual

Assignment operator; disabled.

Reimplemented from geometry::d_bin_point_locator< DC, DB >.

Definition at line 131 of file d_tree_point_locator.h.

◆ operator=() [2/2]

template<int DC, int DB>

d_tree_point_locator& geometry::d_tree_point_locator< DC, DB >::operator= ( const d_tree_point_locator< DC, DB > & xother )

inlineprotected

Assignment operator; disabled.

Definition at line 136 of file d_tree_point_locator.h.

◆ remove_box()

template<int DC, int DB>

void geometry::d_tree_point_locator< DC, DB >::remove_box ( d_bounding_box< DC, DB > * xbox )

virtual

Remove xbox from the tree.

Precondition

xbox != 0

contains_box(xbox)

Postcondition

!contains_box(xbox)

this->box_ct() == old_box_ct - 1

Implements geometry::d_bin_point_locator< DC, DB >.

Definition at line 368 of file d_tree_point_locator.impl.h.

References geometry::d_bin_point_locator< DC, DB >::_box_ct, geometry::d_tree_point_locator< DC, DB >::_root, geometry::d_bin_point_locator< DC, DB >::box_ct(), geometry::d_tree_point_locator< DC, DB >::box_list(), and geometry::d_tree_point_locator< DC, DB >::contains_box().

Referenced by geometry::d_tree_point_locator< DC, DB >::insert_box().

◆ root()

template<int DC, int DB>

const d_tree_point_locator_node< DC, DB > & geometry::d_tree_point_locator< DC, DB >::root ( ) const

The root node.

Postcondition

invariant()

Definition at line 136 of file d_tree_point_locator.impl.h.

References geometry::d_tree_point_locator< DC, DB >::_root, geometry::d_tree_point_locator< DC, DB >::depth(), and geometry::d_tree_point_locator< DC, DB >::invariant().

Referenced by geometry::d_tree_point_locator< DC, DB >::~d_tree_point_locator().

◆ size()

template<int DC, int DB>

size_type geometry::d_tree_point_locator< DC, DB >::size ( )

The number of nodes in the tree.

Definition at line 198 of file d_tree_point_locator.impl.h.

References geometry::d_tree_point_locator< DC, DB >::capacity(), and geometry::d_tree_point_locator< DC, DB >::node_pool().

Referenced by geometry::d_tree_point_locator< DC, DB >::max_depth().

◆ update_bins()

template<int DC, int DB>

void geometry::d_tree_point_locator< DC, DB >::update_bins ( )

protectedvirtual

Updates the tree bin parameters.

Precondition

this->is_empty()

Implements geometry::d_bin_point_locator< DC, DB >.

Definition at line 272 of file d_tree_point_locator.impl.h.

References geometry::d_bin_point_locator< DC, DB >::_bin_size, geometry::d_bin_point_locator< DC, DB >::_bin_ub, geometry::d_tree_point_locator< DC, DB >::_depth, geometry::point_locator::_lb, geometry::d_bin_point_locator< DC, DB >::_one_over_min_bin_size, geometry::point_locator::_ub, geometry::d_bin_point_locator< DC, DB >::is_empty(), geometry::d_tree_point_locator< DC, DB >::node_pool(), fiber_bundle::sec_at0_algebra::pow(), and geometry::d_bin_coordinates< DC, DB >::ub().

Referenced by geometry::d_tree_point_locator< DC, DB >::default_depth().

Member Data Documentation

◆ _depth

template<int DC, int DB>

size_type geometry::d_tree_point_locator< DC, DB >::_depth

protected

The number of levels in the tree; the length of the longest path from the root to a leaf.

Definition at line 162 of file d_tree_point_locator.h.

Referenced by geometry::d_tree_point_locator< DC, DB >::d_tree_point_locator(), geometry::d_tree_point_locator< DC, DB >::depth(), and geometry::d_tree_point_locator< DC, DB >::update_bins().

◆ _node_pool

template<int DC, int DB>

ptr_linked_pool< d_tree_point_locator_node<DC, DB> > geometry::d_tree_point_locator< DC, DB >::_node_pool

protected

Pool for efficiently allocating and deallocating nodes.

Definition at line 151 of file d_tree_point_locator.h.

Referenced by geometry::d_tree_point_locator< DC, DB >::node_pool().

◆ _root

template<int DC, int DB>

d_tree_point_locator_node<DC, DB> geometry::d_tree_point_locator< DC, DB >::_root

protected

The root node of the tree.

Definition at line 156 of file d_tree_point_locator.h.

Referenced by geometry::d_tree_point_locator< DC, DB >::box_list(), geometry::d_tree_point_locator< DC, DB >::clear(), geometry::d_tree_point_locator< DC, DB >::contains_box(), geometry::d_tree_point_locator< DC, DB >::insert_box(), geometry::d_tree_point_locator< DC, DB >::remove_box(), and geometry::d_tree_point_locator< DC, DB >::root().

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

Friends

D_TREE_POINT_LOCATOR FACET

D_BIN_POINT_LOCATOR FACET

POINT_LOCATOR FACET

Additional Inherited Members

Detailed Description

template<int DC, int DB> class geometry::d_tree_point_locator< DC, DB >

Member Typedef Documentation

◆ box_list_type

Constructor & Destructor Documentation

◆ d_tree_point_locator() [1/4]

◆ d_tree_point_locator() [2/4]

◆ ~d_tree_point_locator()

◆ d_tree_point_locator() [3/4]

◆ d_tree_point_locator() [4/4]

Member Function Documentation

◆ box_list()

◆ capacity()

◆ clear()

◆ contains_box()

◆ default_depth()

◆ depth()

◆ insert_box()

◆ invariant()

◆ max_depth()

◆ node_pool()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove_box()

◆ root()

◆ size()

◆ update_bins()

Member Data Documentation

◆ _depth

◆ _node_pool

◆ _root

template<int DC, int DB>
class geometry::d_tree_point_locator< DC, DB >