delaunay::triangulation Class Reference

List of all members.

Public Members
		triangulation ( const double l, const double r, const double t, const double b )
		The only constructur for a `triangulation.` More...
	virtual	~triangulation (void)
	bool	corner_point ( const vector2 &p ) const
		Indicate whether a point is one of the corner points of the intitial rectangle. More...
	bool	border_triangle ( const triangle &t ) const
		Indicate whether a `triangle` includes one of the corner points of the intitial rectangle. More...
	bool	contains ( const vector2 &p ) const
		Indicate whether a given point is one of the points of the `triangulation.` More...
	const vector< triangle >&	triangles (void) const
		Provide the set of triangles that form the triangulation. More...
	void	add_point ( const vector2 &p )
		Add a point to the set of points in the `triangulation.` More...
	const double	left
		The x ordinate of the left side of the initial rectangle.
	const double	right
		The x ordinate of the right side of the initial rectangle.
	const double	top
		The y ordinate of the top side of the initial rectangle.
	const double	bottom
		The y ordinate of the bottom side of the initial rectangle.
	const vector2	tl
		The top left corner of the initial rectangle.
	const vector2	tr
		The top right corner of the initial rectangle.
	const vector2	br
		The bottom right corner of the initial rectangle.
	const vector2	bl
		The bottom left corner of the initial rectangle.

Detailed Description

A Delaunay triangulation is a set of triangles that has some particular properties with respect to a set of points. The triangles have the points as their corners, and no other points as their corners. All the points are at the corner of at least one of the triangles. The circumcircle of any of the triangles contains only the points in the set that are the corners of the triangle. The set of triangles fills the convex hull of the set of points.

The faces of the Voroni polygons for the set of points perpendicularly bisect the edges of the triangles. The Voroni polygon of one of the points is the region that is closer to that point than to any other point in the set. Therefore, the edges of the triangles connect a point in the set to the other points in the set that are its nearby neighbours.

This class supports calculation of a Delaunay triangulation for an arbitrary set of points by providing a member function for adding another point to an existing Delaunay triangulation.

Member Function Documentation

The only constructur for a triangulation.

This creates an initial triangulation that fills a given rectangle. All points added to the triangulation must lie within this rectangle. The initial triangulation consists of four points, at the corners of the rectangle, and two triangles.

The class provides a member function, corner_point(vector2), for distinguishing the points at the corners of the rectangle from the other points in the triangulation, and a member function, border_triangle(triangle), for distinguishing the triangles that include one of the rectangle's corner points from the other triangles in the triangulation. Those functions are useful if the user is interested in the Delaunay triangulation of a set of points that do not have a rectangular convex hull. The user can create an initial rectangular triangulation that is guaranteed to include all the points of interst, add the points of interest, then eliminate from consideration the points indicated by corner_point and the triangles indicated by border_triangle.

Parameters:

l	the x ordinate of the left side of the initial rectangle
r	the x ordinate of the right side of the initial rectangle
t	the y ordinate of the top side of the initial rectangle
b	the y ordinate of the bottom side of the initial rectangle

Preconditions:

 assert( l <= r );
 assert( b <= t );

Postconditions:

 assert( this->left == l );
 assert( this->right == r );
 assert( this->top == t );
 assert( this->bottom == b );
 assert( this->tl == vector2( l, t ) );
 assert( this->tr == vector2( r, t ) );
 assert( this->br == vector2( r, b ) );
 assert( this->bl == vector2( l, b ) );

triangles() gives two triangle objects that fill the rectangle specified by the given ordinates. The corners of those triangles are the four border corners.

Definition at line 117 of file delaunay.cpp.

Indicate whether a point is one of the corner points of the intitial rectangle.

Parameters:

p	the point to check

Returns:: true iff p is one of the corner points of the initial rectangle

Invariants:

 assert( this->corner_point( this->tl ) );
 assert( this->corner_point( this->tr ) );
 assert( this->corner_point( this->br ) );
 assert( this->corner_point( this->bl ) );

Otherwise, corner_point returns false.

Definition at line 585 of file delaunay.h.

Indicate whether a triangle includes one of the corner points of the intitial rectangle.

Parameters:

t	the `triangle` to test

Returns:: true iff t includes one of the corner points of the initial rectangle.

Definition at line 602 of file delaunay.h.

Indicate whether a given point is one of the points of the triangulation.

That is, whether the given point is a vertex of any of the traingles of the triangulation.

Parameters:

p	the point to test

Returns:: true iff p is one of the points of the triangulation

Invariants:

 assert( this->contains( this->tl ) );
 assert( this->contains( this->tr ) );
 assert( this->contains( this->br ) );
 assert( this->contains( this->bl ) );

Definition at line 220 of file delaunay.cpp.

Add a point to the set of points in the triangulation.

This alters the set returned by triangles().

Parameters:

p	the point to add

Preconditions:

 assert( this->left <= p.x && p.x <= this->right );
 assert( this->bottom <= p.y && p.y <= this->top );
 assert( !this->contains( p ) );

Postconditions:

 assert( this->contains( p ) );

Implementation:: This member function implements the robust incremental algorithm due to Watson, and ultimately based on the algorithm due to Guibas. This uses the circumcircle test to determine which existing triangles need to be remove, and uses a temporary list of the edges of those triangles, to simplify creation of the new triangles.

Definition at line 147 of file delaunay.cpp.

delaunay::triangulation Class Reference

Public Members

Detailed Description

Member Function Documentation

Member Data Documentation