Namespaces
	iter

	simplex

Classes
class	BreadthFirst

struct	ExampleTraits
	Example of a traits class suitable for instantiation an edelsbrunner triangulation object. More...

class	ExhaustiveSimplexDistance
	Computes the distance of a point to a simplex by expanding all combinations of vertices and evaluating the distance to the lower-dimensional simplex feature represented by that combination of vertices. More...

struct	Facet
	A facet is a (d-1)-dimensional simplex. More...

class	InducedSubcomplex
	The induced subcomplex of a facet between two simplices is the set of all simplices in the triangulation whose vertices are composed of those from the two simplices in question. More...

struct	SimplexBase
	A simplex in the triangulation. A simplex is the convex hull of Ndim+1 points in R^NDim. More...

class	SimplexFill
	A convenience for setting vertices of a simplex. More...

Functions
template<class Traits , class Derived , class Iterator >
void	BarycentricProjection (typename Traits::Storage &storage, const typename Traits::Point &x, Iterator begin, Iterator end, Eigen::MatrixBase< Derived > L, typename Traits::Point x_proj)
	Given a query point, `x` and a set of vertex points, V, return the point y in hull(V) which is closest to `x_q`. More...

template<class Traits , class OutputIterator >
void	BreadthFirstSearch (typename Traits::Storage &storage, typename Traits::SimplexRef simplex_ref, OutputIterator out)
	Get a list of all simplices by breadth first search starting at `simplex_ref`. More...

template<class Traits , class Container >
std::list< std::pair< typename Traits::SimplexRef, typename Traits::SimplexRef > >	BuildHorizonRidge (typename Traits::Storage &storage, Container &visible_hull)
	Build the horizon ridge, which is the set of all edges which border the x-visible hull. More...

template<class Traits , class Container >
void	DemoteHullSimplices (typename Traits::Storage &storage, Container &visible_hull, typename Traits::PointRef point_ref)
	For each infinite simplex references in `hull_simplices`, replace the null vertex with the vertex pointed to by `point_ref`. More...

template<typename Traits , typename InputIterator , typename OutputIterator >
void	FeatureWalk (typename Traits::Storage &storage, typename Traits::SimplexRef s_0, InputIterator Vf_begin, InputIterator Vf_end, OutputIterator out)
	Given a sub-simplex feature and a simplex adjacent to that feature, enumerate all simplices that are adjacent to that feature. More...

template<class Traits , class Container >
std::list< typename Traits::SimplexRef >	FillHorizonWedges (typename Traits::Storage &storage, Container &horizon_ridge, typename Traits::PointRef point_ref)
	For each simplex pair (s1,s2) in , fill the empty wedge that was created when s1 was demoted to a non-infinite simplex. More...

template<class Traits >
void	FindFillNeighbor (typename Traits::Storage &storage, typename Traits::SimplexRef s_ref, typename Traits::PointRef v_ref, typename Traits::PointRef peak_ref)
	Find the neighbor of a fill simplex that is across from v_ref. More...

template<class Traits >
void	FindWedgeNeighbor (typename Traits::Storage &storage, typename Traits::SimplexRef wedge_ref, int i)
	Given a simplex which fills an empty wedge created by demotion of a simplex along the horizon ridge, find the i'th neighbor by walking around the common edge which contains the peak vertex. More...

template<typename Traits , class OutputIterator >
void	FuzzyWalk (typename Traits::Storage &storage, const typename Traits::SimplexRef s_0, const typename Traits::Point &x_q, const typename Traits::Scalar epsilon, OutputIterator out)
	Given a simplex in a triangulation and a query point, walk the triangulation in the direction of x_q until we find the set of simplices that the query intersects. More...

template<typename Traits , class OutputIterator >
void	FuzzyWalk_ (typename Traits::Storage &storage, const typename Traits::SimplexRef s_0, const typename Traits::Point &x_q, const typename Traits::Scalar epsilon, std::list< typename Traits::SimplexRef > &search_queue, OutputIterator out)
	Implementation, exposed so that the search_queue can be examined in tests. More...

template<typename Traits >
Traits::SimplexRef	FuzzyWalkInsert (typename Traits::Storage &storage, const typename Traits::SimplexRef s_0, const typename Traits::PointRef x_ref, const typename Traits::Scalar epsilon)
	Perform a fuzzy walk to get the set of simplices intersecting the query point, then insert the point into the triangulation. More...

template<class Traits , class OutputIterator >
void	GetVisibleHull (typename Traits::Storage &storage, typename Traits::SimplexRef s_0, const typename Traits::Point &x_q, OutputIterator out)
	Starting at some x-visible hull simplex, return a list of all x-visible hull simplices. More...

template<class Traits >
Traits::SimplexRef	InsertInside (typename Traits::Storage &storage, typename Traits::SimplexRef simplex_ref, typename Traits::PointRef point_ref)
	Inserts a point into a simplex, performs 1-to-n+1 flip, and performs the delaunay maintenance on the modified graph. More...

template<class Traits >
Traits::SimplexRef	InsertOutside (typename Traits::Storage &storage, typename Traits::SimplexRef simplex_ref, typename Traits::PointRef point_ref)
	Inserts a point outside of the hull of the current point set. Note that `simplex_ref` must point to a hull facet which is visible by the point to insert. More...

template<class Traits , class Iterator >
Traits::SimplexRef	InsertReplace (typename Traits::Storage &storage, typename Traits::PointRef point_ref, Iterator S_begin, Iterator S_end)
	Inserts a point into the triangulation, replacing the given simplex set which intersect the new point. More...

template<class Traits >
bool	IsVisible (typename Traits::Storage &storage, typename Traits::SimplexRef s_ref, const typename Traits::Point &x_q, typename Traits::Scalar epsilon=0.0)
	Given a hull simplex, return true if it is visible by the query point. More...

template<typename Traits >
Traits::SimplexRef	LineWalk (typename Traits::Storage &storage, typename Traits::SimplexRef s_0, const typename Traits::Point &p)
	Starting at the median point of simplex `s_0`, walk the triangulation in the direction of `p` until the simplex containing `p` is found. Return that simplex. Note that the returned simplex may be an "infinite" simplex, i.e. a sentinal for a boundary facet of the convex hull. More...

template<class Traits >
Traits::SimplexRef	Maintain (typename Traits::Storage &storage, typename Traits::PointRef point_ref, typename Traits::SimplexRef return_ref, std::list< Facet< Traits >> &link_facets)
	While the link of the specified point is not locally Delaunay, continue flipping locally non-Delaunay facets. More...

void	pass (std::initializer_list< int > &&)
	A trick to allow parameter pack expansion for filling. More...

template<typename T >
int	signum (T val)

template<class Traits , class OutputIterator >
Traits::Scalar	SimplexDistance (typename Traits::Storage &storage, const typename Traits::Point &x, const typename Traits::SimplexRef s_ref, typename Traits::Point *x_proj, OutputIterator V_out)
	Given a set of <= NDim+1 vertices, compute the distance of the query point to the convex hull of the vertex set. More...

template<class Traits >
Traits::SimplexRef	Triangulate (typename Traits::Storage &storage, std::initializer_list< typename Traits::PointRef > refs)
	Initialize a triangulation with NDim+1 points and return the simplex. More...

Function Documentation

template<class Traits , class Derived , class Iterator >

void edelsbrunner96::BarycentricProjection	(	typename Traits::Storage &	storage,
		const typename Traits::Point &	x,
		Iterator	begin,
		Iterator	end,
		Eigen::MatrixBase< Derived > *	L,
		typename Traits::Point *	x_proj
	)

Given a query point, x and a set of vertex points, V, return the point y in hull(V) which is closest to x_q.

Parameters

storage	the storage model
x	the query point
begin	iterator to the first vertex reference
end	iterator to the past-the-end vertex reference

Definition at line 177 of file simplex.hpp.

template<class Traits , class OutputIterator >

void edelsbrunner96::BreadthFirstSearch	(	typename Traits::Storage &	storage,
		typename Traits::SimplexRef	simplex_ref,
		OutputIterator	out
	)

Get a list of all simplices by breadth first search starting at simplex_ref.

Definition at line 445 of file line_walker.hpp.

template<class Traits , class Container >

std::list<std::pair<typename Traits::SimplexRef, typename Traits::SimplexRef> > edelsbrunner96::BuildHorizonRidge	(	typename Traits::Storage &	storage,
		Container &	visible_hull
	)

Build the horizon ridge, which is the set of all edges which border the x-visible hull.

An edge is a set of (N+1-2) vertices. For simplices along the horizon ridge, one of the missing vertices is the infinite vertex, or, if the simplex is newly demoted, the vertex that was added. We go through all of the demoted simplices, and make a list of those that are on the horizon ridge (i.e. the boundary of the demoted subcomplex).

Definition at line 224 of file triangulation.hpp.

template<class Traits , class Container >

void edelsbrunner96::DemoteHullSimplices	(	typename Traits::Storage &	storage,
		Container &	visible_hull,
		typename Traits::PointRef	point_ref
	)

For each infinite simplex references in hull_simplices, replace the null vertex with the vertex pointed to by point_ref.

Definition at line 177 of file triangulation.hpp.

template<typename Traits , typename InputIterator , typename OutputIterator >

void edelsbrunner96::FeatureWalk	(	typename Traits::Storage &	storage,
		typename Traits::SimplexRef	s_0,
		InputIterator	Vf_begin,
		InputIterator	Vf_end,
		OutputIterator	out
	)

Given a sub-simplex feature and a simplex adjacent to that feature, enumerate all simplices that are adjacent to that feature.

A "feature" is a simplex s = conv(V), of |V| < NDim+1 vertices. It is a simplex of lower dimension than the embedding dimension of the triangulation. As an example, for a triangulation in 3 dimensions, a simplex is a tetrahedron, which is the convex hull of four vertices. The (3-1=2)-dimensional features of this simplex are it's triangle facets. The (3-2=1)-dimensional features of this simplex are it's line-segment edges. The (3-3=0)-dimensional features are it's vertices.

Given a simplex S, with vertex set V_S, and a feature with vertex set V_f, we identify the set of vertices V = V_S \ V_f. For each vertex v in V, the neighbor of S across from v shares all vertices V \ v. In particular, it shares V_f. We enumerate simplices of a common feature by breadth-first utilizing this fact.

Definition at line 168 of file line_walker.hpp.

template<class Traits , class Container >

std::list<typename Traits::SimplexRef> edelsbrunner96::FillHorizonWedges	(	typename Traits::Storage &	storage,
		Container &	horizon_ridge,
		typename Traits::PointRef	point_ref
	)

For each simplex pair (s1,s2) in , fill the empty wedge that was created when s1 was demoted to a non-infinite simplex.

Definition at line 246 of file triangulation.hpp.

template<class Traits >

void edelsbrunner96::FindFillNeighbor	(	typename Traits::Storage &	storage,
		typename Traits::SimplexRef	s_ref,
		typename Traits::PointRef	v_ref,
		typename Traits::PointRef	peak_ref
	)

Find the neighbor of a fill simplex that is across from v_ref.

Definition at line 579 of file triangulation.hpp.

template<class Traits >

void edelsbrunner96::FindWedgeNeighbor	(	typename Traits::Storage &	storage,
		typename Traits::SimplexRef	wedge_ref,
		int	i
	)

Given a simplex which fills an empty wedge created by demotion of a simplex along the horizon ridge, find the i'th neighbor by walking around the common edge which contains the peak vertex.

The algorithm for this is based on the horizon-ridge algorithm from Clarkson93. For each new simplex along the horizon ridge that we need to find the neighbor of, the neighbor that we need will lie across a facet of that simplex. That facet is composed of N vertices, one of which is the peak vertex (the newly added point). If we remove the peak vertex we are left with (N-1) vertices which we will call the "pivot edge". We will do a walk around this pivot edge until we find the neighboring simplex.

From our starting simplex we move to the neighbor across the infinite vertex. This neighbor shares the pivot edge, and one other vertex in common with the starting simplex. Incidentally, it is also a recently demoted simplex. We continue the walk by following that other vertex. A proof is given in the Clarkson93 paper that the walk must end at the desired neighbor of the starting simplex.

This walk is illustrated in 2d in the following ascii art. We start at simplex [0] and are looking for the neighbor across the facet {x,inf}. The relevant edge we will walk "around" is {x}. Note that we define an edge as the NDim points of the common facet, minus the infinite vertex. In 2d this is a set of one vertex, or, simply, a point. In 2d, an edge is a point... confusing, I know.

In any case we start at simplex [0] and walk to the neighbor across from (inf) which is simplex [1] in the diagram. Simplex [1] contains exactly one vertex which is on the facet between [0] and [1] and is not (x). We identify that vertex (a), and then move to the neighbor across that vertex, [2]. Again simplex [2] and simplex [1] share only a single vertex which is on the their common facet but is not (x). We identify that vertex (b) and move to the neighbor across (b), in this case simplex [3]. We continue this walk until we reach simplex [4], which is the first infinite simplex in this walk around the edge. Simplex [4] is the neighbor across from [0] that we were searching for.

              (inf)           [.] simplex
               |              (.) vertex
               |
      [4]   (x)|     [0]
             //\\
          /  /  \  \
       /    /    \    \
    /      /      \      \
 /   [3]  /   [2]  \  [1]   \
(d)      (c)       (b)      (a)

Definition at line 368 of file triangulation.hpp.

template<typename Traits , class OutputIterator >

void edelsbrunner96::FuzzyWalk	(	typename Traits::Storage &	storage,
		const typename Traits::SimplexRef	s_0,
		const typename Traits::Point &	x_q,
		const typename Traits::Scalar	epsilon,
		OutputIterator	out
	)

Given a simplex in a triangulation and a query point, walk the triangulation in the direction of x_q until we find the set of simplices that the query intersects.

We return all simplices which are within epsilon distance from x_q. The search is a greedy walk through the triangulation. Starting at s_0, we find the feature of the simplex nearest to x_q. We then queue up all simplices that are adjacent to that feature. A feature is a sub-simplex such as a facet, edge, or lower-dimensional hull of some subset of the vertex set (down to a single vertex). For instance, if the query point is closest to a facet of s_0, we only queue up the neighbor of s_0 across that facet. If x_q is closest to a vertex of s_0, we queue up all simplices that share that vertex.

param storage the storage model param s_0 the simplex to start the walk at param epsilon the radius of fuzz for which we consider something to intersect param x_q the query point param[out] out iterator where we write the output set of simplices

Definition at line 299 of file line_walker.hpp.

template<typename Traits , class OutputIterator >

void edelsbrunner96::FuzzyWalk_	(	typename Traits::Storage &	storage,
		const typename Traits::SimplexRef	s_0,
		const typename Traits::Point &	x_q,
		const typename Traits::Scalar	epsilon,
		std::list< typename Traits::SimplexRef > &	search_queue,
		OutputIterator	out
	)

Implementation, exposed so that the search_queue can be examined in tests.

Definition at line 227 of file line_walker.hpp.

template<typename Traits >

Traits::SimplexRef edelsbrunner96::FuzzyWalkInsert	(	typename Traits::Storage &	storage,
		const typename Traits::SimplexRef	s_0,
		const typename Traits::PointRef	x_ref,
		const typename Traits::Scalar	epsilon
	)

Perform a fuzzy walk to get the set of simplices intersecting the query point, then insert the point into the triangulation.

Definition at line 724 of file triangulation.hpp.

template<class Traits , class OutputIterator >

void edelsbrunner96::GetVisibleHull	(	typename Traits::Storage &	storage,
		typename Traits::SimplexRef	s_0,
		const typename Traits::Point &	x_q,
		OutputIterator	out
	)

Starting at some x-visible hull simplex, return a list of all x-visible hull simplices.

Definition at line 356 of file line_walker.hpp.

template<class Traits >

Traits::SimplexRef edelsbrunner96::InsertInside	(	typename Traits::Storage &	storage,
		typename Traits::SimplexRef	simplex_ref,
		typename Traits::PointRef	point_ref
	)

Inserts a point into a simplex, performs 1-to-n+1 flip, and performs the delaunay maintenance on the modified graph.

Definition at line 498 of file triangulation.hpp.

template<class Traits >

Traits::SimplexRef edelsbrunner96::InsertOutside	(	typename Traits::Storage &	storage,
		typename Traits::SimplexRef	simplex_ref,
		typename Traits::PointRef	point_ref
	)

Inserts a point outside of the hull of the current point set. Note that simplex_ref must point to a hull facet which is visible by the point to insert.

Definition at line 411 of file triangulation.hpp.

template<class Traits , class Iterator >

Traits::SimplexRef edelsbrunner96::InsertReplace	(	typename Traits::Storage &	storage,
		typename Traits::PointRef	point_ref,
		Iterator	S_begin,
		Iterator	S_end
	)

Inserts a point into the triangulation, replacing the given simplex set which intersect the new point.

Definition at line 619 of file triangulation.hpp.

template<class Traits >

bool edelsbrunner96::IsVisible	(	typename Traits::Storage &	storage,
		typename Traits::SimplexRef	s_ref,
		const typename Traits::Point &	x_q,
		typename Traits::Scalar	epsilon = `0.0`
	)

Given a hull simplex, return true if it is visible by the query point.

Definition at line 310 of file line_walker.hpp.

template<typename Traits >

Traits::SimplexRef edelsbrunner96::LineWalk	(	typename Traits::Storage &	storage,
		typename Traits::SimplexRef	s_0,
		const typename Traits::Point &	p
	)

Starting at the median point of simplex s_0, walk the triangulation in the direction of p until the simplex containing p is found. Return that simplex. Note that the returned simplex may be an "infinite" simplex, i.e. a sentinal for a boundary facet of the convex hull.

Starting at centroid of simplex s_0, walk the triangulation in the direction of p until the simplex containing p is found. Return that simplex. Note that the returned simplex may be an "infinite" simplex, i.e. a sentinal for a boundary facet of the convex hull.

Definition at line 42 of file line_walker.hpp.

template<class Traits >

Traits::SimplexRef edelsbrunner96::Maintain	(	typename Traits::Storage &	storage,
		typename Traits::PointRef	point_ref,
		typename Traits::SimplexRef	return_ref,
		std::list< Facet< Traits >> &	link_facets
	)

While the link of the specified point is not locally Delaunay, continue flipping locally non-Delaunay facets.

Definition at line 87 of file triangulation.hpp.

void edelsbrunner96::pass ( std::initializer_list< int > && )

inline

A trick to allow parameter pack expansion for filling.

Definition at line 47 of file simplex.hpp.

template<typename T >

int edelsbrunner96::signum ( T val )

Definition at line 160 of file induced_subcomplex.hpp.

template<class Traits , class OutputIterator >

Traits::Scalar edelsbrunner96::SimplexDistance	(	typename Traits::Storage &	storage,
		const typename Traits::Point &	x,
		const typename Traits::SimplexRef	s_ref,
		typename Traits::Point *	x_proj,
		OutputIterator	V_out
	)

Given a set of <= NDim+1 vertices, compute the distance of the query point to the convex hull of the vertex set.

We use a reduced version of GJK to compute the distance to the hull. We start at the nearest vertex and build up features until we find the nearest feature. A feature is a vertex, a line segment between two vertices, a triangle between three vertices, a tetrahedron between four vertices, etc.

Parameters

storage	the triangulation storage class
point	the query point
V	the vertex set of the simplex
out	output iterator, the vertex set of the nearest feature is written here

Definition at line 213 of file simplex.hpp.

template<class Traits >

Traits::SimplexRef edelsbrunner96::Triangulate	(	typename Traits::Storage &	storage,
		std::initializer_list< typename Traits::PointRef >	refs
	)

Initialize a triangulation with NDim+1 points and return the simplex.

The triangulation is actually composed of NDim+2 simplices. In 2d this is drawn in ascii art below.

                    (inf)             [.] simplex
                     |                (.) vertex
                     |
                     |(2)
                    / \
             [1]   /   \    [0]
                  /     \
                 /  [3]  \
(inf) ----------/_________\------------ (inf)
             (0)           (1)
                    [2]

Note that there are (NDim=2 + 2) = 4 simplices (triangles) generated. The triangle formed by the three vertices is [3] = conv({(0),(1),(2)}). There are three additional meta-simplices. Each one is formed by two of the vertices, with the addition of the designated "infinite" vertex as the third. In this way the entire space of R^2 is covered. Note that these infinite simplices are degenerate: their circumcenter and circumradius are undefined. This is useful, however, to ensure that the entire space of R^2 is covered by an element in the tesselation.

Definition at line 40 of file triangulation.hpp.

Namespaces

Classes

Functions

Function Documentation