DelaunayNP Class Reference

construct Delaunay Triangulation of a 2D, non-periodic point set via Bowyer-Watson algorithm More...

#include <Delaunay1.h>

Public Member Functions
	DelaunayNP (std::vector< Dscalar2 > points)
	constructor via a vector of point objects
	DelaunayNP (std::vector< Dscalar > points)
	constructor via a vector of scalars, {x1,y1,x2,y2,...}
void	setSorted (bool s)
void	setPoints (std::vector< Dscalar2 > points)
	Set the points you want to triangulate.
void	setPoints (std::vector< Dscalar > points)
void	printPoint (int i)
	A debugging function, prints the location of a point.
void	getSortedPoint (int i, Dscalar2 &point)
	A debugging function... gets the sorted point i.
int	deSortPoint (int i)
	Figure out the original point that the sorted set of points refers to.
void	sortPoints ()
	sorts points by their x-coordinate...necessary for the algorithm More...
void	triangulate ()
	default call... update this whenever a better algorithm is implemented More...
void	naiveBowyerWatson ()
	calculate the Delaunay triangulation via an O(nV^1.5) version ofBowyer-Watson More...
void	printTriangulation (int maxprint)
	output part of triangulation to screen More...
void	writeTriangulation (ofstream &outfile)
	write triangulation to text file More...
void	testDel (int numpts, int tmax, bool verbose)
	simple unit test More...

Public Attributes
std::vector< int >	mapi
	a map to sorted coords...mapi[j] tells you the position in sortmap that vertex j appears in
triangulation	DT
	a public variable that stores the triangulation as sets of (i,j,k) vertices, referring to the order of sortmap entries

Detailed Description

construct Delaunay Triangulation of a 2D, non-periodic point set via Bowyer-Watson algorithm

DelaunayNP implements a naive Bowyer-watson algorithm to compute the Delaunay Triangulation of a non-periodic set of points. Ideally this method should not be called (in favor of CGAL- based triangulations), but if for some reason CGAL is not available this can be used in a pinch. In particular, it will be slower and more prone to crashes, as CGAL has a robust error catching scheme.

Member Function Documentation

sortPoints()

void DelaunayNP::sortPoints

(

)

sorts points by their x-coordinate...necessary for the algorithm

Sorts points according to the sortmap array, which itself is via the x-coordinate of the points

References mapi.

triangulate()

void DelaunayNP::triangulate

(

)

default call... update this whenever a better algorithm is implemented

A simple wrapper around the naiveBowyerWatson routine written... if DelaunayNP ever gets additional algorithms (to reduce how poorly it performs relative to CGAL, for instance), this function can be updated, potentially with additional logic if some routines are specialized to particular situations

References naiveBowyerWatson().

Referenced by DelaunayLoc::getNeighbors(), and DelaunayLoc::triangulatePoint().

naiveBowyerWatson()

void DelaunayNP::naiveBowyerWatson

(

)

calculate the Delaunay triangulation via an O(nV^1.5) version ofBowyer-Watson

A simple Bowyer-Watson-style algorithm to deduce the Delaunay triangulation of a point set. A fixed choice of bounding triangle has been used, which was empirically chosen from its acceptable performance on random point sets.

Referenced by triangulate().

printTriangulation()

void DelaunayNP::printTriangulation

(

int

maxprint

)

output part of triangulation to screen

A utility function, of use for debugging

Parameters

maxprint

the number of points to print to screen

References DT, triangulation::nTriangles, and triangulation::triangles.

writeTriangulation()

void DelaunayNP::writeTriangulation

(

ofstream &

outfile

)

write triangulation to text file

A utility function, of use for debugging...outputs a simple representation of the triangulation to the file specifed by "outfile"

Parameters

outfile

The file to which the info should be sent

References DT, triangulation::nEdges, and triangulation::nTriangles.

testDel()

void DelaunayNP::testDel	(	int	numpts,
		int	tmax,
		bool	verbose
	)

simple unit test

A utility function for timing random point configurations

Parameters

numpts	the number of points to perform timing tests on
tmax	the number of distinct configurations to average over
verbose	print extra info if true

---

The documentation for this class was generated from the following files:

• Delaunay1.h
• Delaunay1.cpp