misleadingly-named data structure, is actually a "simplexification", the dimension agnostic analog of a triangulation More...

#include <mpblocks/clarkson93/Triangulation.h>

Inheritance diagram for mpblocks::clarkson93::Triangulation< Traits >:

Public Types
typedef Traits::Callback	Callback

typedef Traits::Deref	Deref

typedef std::vector< Ridge >	HorizonSet

typedef Traits::Point	Point

typedef Traits::PointRef	PointRef

typedef std::set< PointRef >	PointSet

typedef Indexed< Scalar, SimplexRef >	PQ_Key

typedef HorizonRidge< Traits >	Ridge

typedef Traits::Scalar	Scalar

typedef Traits::Simplex	Simplex

typedef Traits::SimplexMgr	SimplexMgr

typedef Traits::SimplexRef	SimplexRef

typedef std::vector< SimplexRef >	SimplexSet

typedef Triangulation< Traits >	This

typedef P_Queue< PQ_Key >	WalkQueue

Public Member Functions
void	alter_x_visible (const OptLevel< 0 > &, PointRef x)

void	clear ()
	destroys all simplex objects that have been generated and clears all lists/ sets More...

void	fill_x_visible (const OptLevel< 0 > &, PointRef x, SimplexRef S)
	given a simplex S which is x-visible and infinite, fill the set of all x-visible and infinite facets More...

Simplex *	find_x_visible (PointRef x, SimplexRef S)
	find the set of $x\mathrm{-visible}$ facets and put them in `x_visible` More...

template<class Iterator , class Deiter >
void	init (Iterator begin, Iterator end, Deiter deiter)
	builds the initial triangulation from the first `NDim` + 1 points inserted More...

void	insert (const PointRef x, SimplexRef S)
	insert a new point into the triangulation and update the convex hull (if necessary) More...

void	insert (const PointRef x)

	Triangulation ()

	~Triangulation ()

Public Attributes
PointRef	m_antiOrigin
	fictitious point More...

Callback	m_callback
	event hooks More...

Deref	m_deref
	dereferences a PointRef or SimplexRef More...

SimplexRef	m_hullSimplex
	a simplex in the hull More...

SimplexRef	m_origin
	origin simplex More...

HorizonSet	m_ridges
	set of horizon ridges More...

SimplexMgr	m_sMgr
	simplex manager More...

WalkQueue	m_xv_queue
	walk for x-visible search More...

SimplexSet	m_xv_walked
	set of simplices ever expanded for the walk More...

SimplexSet	m_xvh
	set of x-visible hull simplices More...

SimplexSet	m_xvh_queue
	search queue for x-visible hull More...

Static Public Attributes
static const unsigned int	NDim = Traits::NDim

static const OptLevel < OptLevelGet< Traits >::Value >	s_optLvl = OptLevel< OptLevelGet<Traits>::Value >()

Detailed Description

template<class Traits>
struct mpblocks::clarkson93::Triangulation< Traits >

misleadingly-named data structure, is actually a "simplexification", the dimension agnostic analog of a triangulation

By the convensions of Clarkson.compgeo93, the first (i.e. 0 index) simplex is the "origin" simplex. The 'origin' ( $ O $ ) is a point inside that simplex (we'll pick the geometric mean of the vertices). The 'anti-origin' ( $\overbar{o}$ ) is a fictitous vertex which is a member of all simplices on the convex hull. It is analogous to CGAL's 'vertex at infinity'. We'll give it a value of $ [0 0 0...] $ , but it's address is used to identify it as a special point, and it's value is never used in calculations.

Definition at line 95 of file Triangulation.h.

Member Typedef Documentation

template<class Traits >

typedef Traits::Callback mpblocks::clarkson93::Triangulation< Traits >::Callback

Definition at line 110 of file Triangulation.h.

template<class Traits >

typedef Traits::Deref mpblocks::clarkson93::Triangulation< Traits >::Deref

Definition at line 109 of file Triangulation.h.

template<class Traits >

typedef std::vector<Ridge> mpblocks::clarkson93::Triangulation< Traits >::HorizonSet

Definition at line 118 of file Triangulation.h.

template<class Traits >

typedef Traits::Point mpblocks::clarkson93::Triangulation< Traits >::Point

Definition at line 105 of file Triangulation.h.

template<class Traits >

typedef Traits::PointRef mpblocks::clarkson93::Triangulation< Traits >::PointRef

Definition at line 107 of file Triangulation.h.

template<class Traits >

typedef std::set<PointRef> mpblocks::clarkson93::Triangulation< Traits >::PointSet

Definition at line 116 of file Triangulation.h.

template<class Traits >

typedef Indexed<Scalar,SimplexRef> mpblocks::clarkson93::Triangulation< Traits >::PQ_Key

Definition at line 121 of file Triangulation.h.

template<class Traits >

typedef HorizonRidge<Traits> mpblocks::clarkson93::Triangulation< Traits >::Ridge

Definition at line 114 of file Triangulation.h.

template<class Traits >

typedef Traits::Scalar mpblocks::clarkson93::Triangulation< Traits >::Scalar

Definition at line 104 of file Triangulation.h.

template<class Traits >

typedef Traits::Simplex mpblocks::clarkson93::Triangulation< Traits >::Simplex

Definition at line 106 of file Triangulation.h.

template<class Traits >

typedef Traits::SimplexMgr mpblocks::clarkson93::Triangulation< Traits >::SimplexMgr

Definition at line 111 of file Triangulation.h.

template<class Traits >

typedef Traits::SimplexRef mpblocks::clarkson93::Triangulation< Traits >::SimplexRef

Definition at line 108 of file Triangulation.h.

template<class Traits >

typedef std::vector<SimplexRef> mpblocks::clarkson93::Triangulation< Traits >::SimplexSet

Definition at line 117 of file Triangulation.h.

template<class Traits >

typedef Triangulation<Traits> mpblocks::clarkson93::Triangulation< Traits >::This

Definition at line 113 of file Triangulation.h.

template<class Traits >

typedef P_Queue<PQ_Key> mpblocks::clarkson93::Triangulation< Traits >::WalkQueue

Definition at line 122 of file Triangulation.h.

Constructor & Destructor Documentation

template<class Traits >

mpblocks::clarkson93::Triangulation< Traits >::Triangulation ( )

Definition at line 44 of file Triangulation.hpp.

template<class Traits >

mpblocks::clarkson93::Triangulation< Traits >::~Triangulation ( )

Definition at line 51 of file Triangulation.hpp.

Member Function Documentation

template<class Traits >

void mpblocks::clarkson93::Triangulation< Traits >::alter_x_visible	(	const OptLevel< 0 > &	,
		PointRef	x
	)

Definition at line 344 of file Triangulation.hpp.

template<class Traits >

void mpblocks::clarkson93::Triangulation< Traits >::clear ( )

destroys all simplex objects that have been generated and clears all lists/ sets

Definition at line 157 of file Triangulation.hpp.

template<class Traits >

void mpblocks::clarkson93::Triangulation< Traits >::fill_x_visible	(	const OptLevel< 0 > &	,
		PointRef	x,
		SimplexRef	S
	)

given a simplex S which is x-visible and infinite, fill the set of all x-visible and infinite facets

Definition at line 272 of file Triangulation.hpp.

template<class Traits >

Traits::Simplex * mpblocks::clarkson93::Triangulation< Traits >::find_x_visible	(	PointRef	x,
		SimplexRef	S
	)

find the set of $x\mathrm{-visible}$ facets and put them in x_visible

Using the first method of Clarkson.compgeo93, we walk along the segment $\overbar{Ox}$ , starting at $ O $ . If this walk enters a simplex whose peak vertex is the anti-origin, then an x-visible current facet has been found. Otherwise a simplex of T containing $ x $ has been found, showing that $x \in \mathrm{hull} R$