Aleph::VisibilityPolygon::EdgeStatusTree Class Reference

BST-based sweep status for active edges, ordered by ray-intersection distance. More...

Collaboration diagram for Aleph::VisibilityPolygon::EdgeStatusTree:

Classes
struct	EdgeKey
struct	EdgeKeyCmp

Public Member Functions
	EdgeStatusTree (const Array< Point > &verts, const size_t n, const Point &query)
void	insert (const size_t edge, const Point &dir)
void	erase (const size_t edge)
size_t	min () const
	Return the nearest edge (smallest ray_param).
bool	contains (const size_t edge) const
bool	is_empty () const

Private Attributes
DynSetTree< EdgeKey, Treap, EdgeKeyCmp >	tree_
Array< Geom_Number >	params_
Array< bool >	in_tree_
const Array< Point > &	verts_
const size_t	n_
const Point &	query_

Detailed Description

BST-based sweep status for active edges, ordered by ray-intersection distance.

Each edge is keyed by (ray_param, edge_index) computed at insertion time. Since the distance ordering of non-crossing edges is invariant between consecutive vertex events, the BST ordering remains valid throughout the sweep.

Backed by Aleph's Treap via DynSetTree. Provides O(log n) insert, erase and min (nearest edge).

Definition at line 9648 of file geom_algorithms.H.

Constructor & Destructor Documentation

EdgeStatusTree()

Aleph::VisibilityPolygon::EdgeStatusTree::EdgeStatusTree ( const Array< Point > &  verts, const size_t  n, const Point &  query  )

inline

Definition at line 9674 of file geom_algorithms.H.

References Aleph::Array< T >::append(), in_tree_, and params_.

Member Function Documentation

contains()

bool Aleph::VisibilityPolygon::EdgeStatusTree::contains ( const size_t  edge ) const

inline

Definition at line 9713 of file geom_algorithms.H.

References in_tree_.

erase()

void Aleph::VisibilityPolygon::EdgeStatusTree::erase ( const size_t  edge )

inline

Definition at line 9695 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), in_tree_, params_, and tree_.

Referenced by Aleph::VisibilityPolygon::operator()().

insert()

void Aleph::VisibilityPolygon::EdgeStatusTree::insert ( const size_t  edge, const Point &  dir  )

inline

Definition at line 9684 of file geom_algorithms.H.

References in_tree_, Aleph::Array< T >::insert(), n_, params_, query_, Aleph::VisibilityPolygon::ray_param(), tree_, and verts_.

Referenced by Aleph::VisibilityPolygon::operator()().

is_empty()

bool Aleph::VisibilityPolygon::EdgeStatusTree::is_empty ( ) const

inline

Definition at line 9718 of file geom_algorithms.H.

References tree_.

min()

size_t Aleph::VisibilityPolygon::EdgeStatusTree::min ( ) const

inline

Return the nearest edge (smallest ray_param).

Returns n_ if the tree is empty.

Definition at line 9706 of file geom_algorithms.H.

References n_, and tree_.

Referenced by Aleph::VisibilityPolygon::operator()().

Member Data Documentation

in_tree_

Array<bool> Aleph::VisibilityPolygon::EdgeStatusTree::in_tree_

private

Definition at line 9668 of file geom_algorithms.H.

Referenced by EdgeStatusTree(), contains(), erase(), and insert().

n_

const size_t Aleph::VisibilityPolygon::EdgeStatusTree::n_

private

Definition at line 9670 of file geom_algorithms.H.

Referenced by insert(), and min().

params_

Array<Geom_Number> Aleph::VisibilityPolygon::EdgeStatusTree::params_

private

Definition at line 9667 of file geom_algorithms.H.

Referenced by EdgeStatusTree(), erase(), and insert().

query_

const Point& Aleph::VisibilityPolygon::EdgeStatusTree::query_

private

Definition at line 9671 of file geom_algorithms.H.

Referenced by insert().

tree_

DynSetTree<EdgeKey, Treap, EdgeKeyCmp> Aleph::VisibilityPolygon::EdgeStatusTree::tree_

private

Definition at line 9666 of file geom_algorithms.H.

Referenced by erase(), insert(), is_empty(), and min().

verts_

const Array<Point>& Aleph::VisibilityPolygon::EdgeStatusTree::verts_

private

Definition at line 9669 of file geom_algorithms.H.

Referenced by insert().

---

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

• geom_algorithms.H