Implementation of RIC convex-hull construction (but not maintainance) algorithm by Clarkson (Computational Geometry, '93) More...
Namespaces | |
| dynamic | |
| simplex | |
Classes | |
| struct | BitMember |
| indicates membership into a number of sets by a bitfield More... | |
| struct | BitMemberBase |
| dummy class which allows us to use SNFINAE More... | |
| struct | DefaultSimplex |
| default simplex structure which contains no additional functionality More... | |
| struct | ExampleTraits |
| documents the interface for Traits : encapsulates various policies for the Triangulation More... | |
| struct | ExampleTraits2 |
| documents the interface for Traits : encapsulates various policies for the Triangulation More... | |
| struct | Facet2 |
| a subset of the vertices of a simplex More... | |
| struct | HorizonRidge |
| A horizon ridge is a d-2 dimensional facet (i.e. a facet of a facet),. More... | |
| struct | Indexed |
| priority queue node More... | |
| struct | NeighborIterator |
| an interator over neighbors in a simplex More... | |
| struct | NeighborRange |
| provides an iterator range for neighbors of a simplex More... | |
| struct | OptDefined |
| Template meta function evaluating whether or not a traits class specifies an optimization level. More... | |
| struct | OptLevel |
| simply maps a complile-time integer to a type More... | |
| struct | OptLevelGet |
| Template meta function evaluating the optimization level as specified by the traits class. More... | |
| struct | OptLevelGet< T, false > |
| class | P_Queue |
| A priority queue with a slightly more readable interface than from the STL. More... | |
| struct | Simplex2 |
| A simplex is the convex hull of d+1 points in general position (IGP), i.e. they do not lie on the same hyperplane. More... | |
| struct | SimplexBase |
| encapsulates a vertex, simplex pair where the simplex is the neighbor across from the specified vertex More... | |
| struct | SimplexOps |
| implements simplex operations for simplex references, using other references can be easily extended by building on top of this class More... | |
| class | Stack |
| class | Stack< T *, SetEnum > |
| struct | Stack< T, void > |
| struct | Surrogate |
| surrogate for a certain value used in setters More... | |
| struct | Triangulation |
| misleadingly-named data structure, is actually a "simplexification", the dimension agnostic analog of a triangulation More... | |
| struct | VertexIterator |
| an interator over vertices in a simplex More... | |
| struct | VertexRange |
| provides an iterator range for vertices of a simplex More... | |
| struct | WithoutSet |
Typedefs | |
| typedef simplex::Bits | SimplexBits |
Enumerations | |
| enum | Orientation { INSIDE, OUTSIDE } |
Functions | |
| template<typename Index_t , typename Value_t > | |
| bool | operator< (const Indexed< Index_t, Value_t > &a, const Indexed< Index_t, Value_t > &b) |
| template<typename Index_t , typename Value_t > | |
| bool | operator> (const Indexed< Index_t, Value_t > &a, const Indexed< Index_t, Value_t > &b) |
Variables | |
| const int | Dynamic = -1 |
Detailed Description
Implementation of RIC convex-hull construction (but not maintainance) algorithm by Clarkson (Computational Geometry, '93)
The algorithm builds a data structure representing the convex hull by Random Incremental Construction. An (extended) Triangulation of inserted points is maintained. The triangulation is extended in such a way that every point in 
is contained in some simplex. Specifically, every facet of the convex hull is in fact a member of two simplices. One, which is a normal simplex, is contained within the convex hull. The other lies outside the convex hull, and it's peak vertex is the so called 'anti-origin' (or vertex 'at infinity in CGAL speak).
Typedef Documentation
Enumeration Type Documentation
| Enumerator | |
|---|---|
| INSIDE | |
| OUTSIDE | |
Definition at line 60 of file clarkson93.h.
Function Documentation
| bool mpblocks::clarkson93::operator< | ( | const Indexed< Index_t, Value_t > & | a, |
| const Indexed< Index_t, Value_t > & | b | ||
| ) |
| bool mpblocks::clarkson93::operator> | ( | const Indexed< Index_t, Value_t > & | a, |
| const Indexed< Index_t, Value_t > & | b | ||
| ) |
Variable Documentation
| const int mpblocks::clarkson93::Dynamic = -1 |
Definition at line 58 of file clarkson93.h.
