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

#include <mpblocks/clarkson93/dynamic/Triangulation.h>

Public Types
typedef Traits::template Factory< HorizonRidge_t >	HorizonAlloc

typedef HorizonRidge< Traits >	HorizonRidge_t

typedef Stack< HorizonRidge_t >	HorizonSet

typedef Traits::Point	Point

typedef Traits::PointDeref	PointDeref

typedef Traits::PointRef	PointRef

typedef std::set< PointRef >	PointSet

typedef Indexed< Scalar, Simplex * >	PQ_Key

typedef Traits::Scalar	Scalar

typedef Traits::Setup	Setup

typedef Traits::Simplex	Simplex

typedef Traits::template Factory< Simplex >	SimplexAlloc

typedef SimplexBase< Traits >	SimplexBase_t

typedef Stack< Simplex *, SimplexBits >	SimplexSet

typedef Stack< Simplex * >	SimplexStack

typedef Triangulation< Traits >	This_t

typedef Triangulation< Traits >	Triangulation_t

typedef unsigned int	uint

typedef P_Queue< PQ_Key >	WalkQueue

Public Member Functions
void	alter_x_visible (PointRef x)

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

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

SimplexAlloc &	getAllocator ()
	return the allocator (for debugging) More...

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

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

void	setup (Setup &setup)
	set's up the triangulation by helping it construct it's allocators and preallocate it's sets More...

	Triangulation ()

	~Triangulation ()

Public Attributes
PointRef	m_antiOrigin
	fictitious point More...

PointDeref	m_deref
	dereferences a PointRef More...

Simplex *	m_hullSimplex
	a simplex in the hull More...

uint	m_ndim
	dimension More...

Simplex *	m_origin
	origin simplex More...

HorizonSet	m_ridges
	set of horizon ridges More...

SimplexAlloc	m_sAlloc
	simplex allocator More...

SimplexSet	m_x_visible
	set of x-visible simplices More...

SimplexSet	m_xv_queue
	search queue for x-visible building More...

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

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

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

Detailed Description

template<class Traits>
class mpblocks::clarkson93::dynamic::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 53 of file Triangulation.h.

Member Typedef Documentation

template<class Traits >

typedef Traits::template Factory<HorizonRidge_t> mpblocks::clarkson93::dynamic::Triangulation< Traits >::HorizonAlloc

Definition at line 79 of file Triangulation.h.

template<class Traits >

typedef HorizonRidge<Traits> mpblocks::clarkson93::dynamic::Triangulation< Traits >::HorizonRidge_t

Definition at line 71 of file Triangulation.h.

template<class Traits >

typedef Stack<HorizonRidge_t> mpblocks::clarkson93::dynamic::Triangulation< Traits >::HorizonSet

Definition at line 76 of file Triangulation.h.

template<class Traits >

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

Definition at line 62 of file Triangulation.h.

template<class Traits >

typedef Traits::PointDeref mpblocks::clarkson93::dynamic::Triangulation< Traits >::PointDeref

Definition at line 65 of file Triangulation.h.

template<class Traits >

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

Definition at line 64 of file Triangulation.h.

template<class Traits >

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

Definition at line 80 of file Triangulation.h.

template<class Traits >

typedef Indexed<Scalar,Simplex*> mpblocks::clarkson93::dynamic::Triangulation< Traits >::PQ_Key

Definition at line 83 of file Triangulation.h.

template<class Traits >

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

Definition at line 61 of file Triangulation.h.

template<class Traits >

typedef Traits::Setup mpblocks::clarkson93::dynamic::Triangulation< Traits >::Setup

Definition at line 66 of file Triangulation.h.

template<class Traits >

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

Definition at line 63 of file Triangulation.h.

template<class Traits >

typedef Traits::template Factory<Simplex> mpblocks::clarkson93::dynamic::Triangulation< Traits >::SimplexAlloc

Definition at line 78 of file Triangulation.h.

template<class Traits >

typedef SimplexBase<Traits> mpblocks::clarkson93::dynamic::Triangulation< Traits >::SimplexBase_t

Definition at line 72 of file Triangulation.h.

template<class Traits >

typedef Stack<Simplex*, SimplexBits> mpblocks::clarkson93::dynamic::Triangulation< Traits >::SimplexSet

Definition at line 74 of file Triangulation.h.

template<class Traits >

typedef Stack<Simplex*> mpblocks::clarkson93::dynamic::Triangulation< Traits >::SimplexStack

Definition at line 75 of file Triangulation.h.

template<class Traits >

typedef Triangulation<Traits> mpblocks::clarkson93::dynamic::Triangulation< Traits >::This_t

Definition at line 69 of file Triangulation.h.

template<class Traits >

typedef Triangulation<Traits> mpblocks::clarkson93::dynamic::Triangulation< Traits >::Triangulation_t

Definition at line 68 of file Triangulation.h.

template<class Traits >

typedef unsigned int mpblocks::clarkson93::dynamic::Triangulation< Traits >::uint

Definition at line 60 of file Triangulation.h.

template<class Traits >

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

Definition at line 84 of file Triangulation.h.

Constructor & Destructor Documentation

template<class Traits >

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

Definition at line 39 of file Triangulation.hpp.

template<class Traits >

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

Definition at line 50 of file Triangulation.hpp.

Member Function Documentation

template<class Traits >

void mpblocks::clarkson93::dynamic::Triangulation< Traits >::alter_x_visible ( PointRef x )

Definition at line 356 of file Triangulation.hpp.

template<class Traits >

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

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

Definition at line 186 of file Triangulation.hpp.

template<class Traits >

void mpblocks::clarkson93::dynamic::Triangulation< Traits >::find_x_visible	(	PointRef	x,
		Simplex *	S = `0`
	)

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$