triangle.c File Reference

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "wrap_dtlib_cpp/triangle.h"

Macros
#define	NO_TIMER
#define	REDUCED
#define	SINGLE
#define	ANSI_DECLARATIONS
#define	CDT_ONLY
#define	TRILIBRARY
#define	REAL   float
#define	INEXACT   /* Nothing */
#define	FILENAMESIZE   512
#define	INPUTLINESIZE   512
#define	TRIPERBLOCK   4092 /* Number of triangles allocated at once. */
#define	SHELLEPERBLOCK   508 /* Number of shell edges allocated at once. */
#define	POINTPERBLOCK   4092 /* Number of points allocated at once. */
#define	VIRUSPERBLOCK   1020 /* Number of virus triangles allocated at once. */
#define	BADSEGMENTPERBLOCK   252
#define	BADTRIPERBLOCK   4092
#define	SPLAYNODEPERBLOCK   508
#define	DEADPOINT   -1073741824
#define	VOID   int
#define	SAMPLEFACTOR   11
#define	SAMPLERATE   10
#define	PI   3.141592653589793238462643383279502884197169399375105820974944592308
#define	SQUAREROOTTWO   1.4142135623730950488016887242096980785696718753769480732
#define	ONETHIRD   0.333333333333333333333333333333333333333333333333333333333333
#define	decode(ptr, triedge)
#define	encode(triedge)   (triangle) ((unsigned long) (triedge).tri | (unsigned long) (triedge).orient)
#define	sym(triedge1, triedge2)
#define	symself(triedge)
#define	lnext(triedge1, triedge2)
#define	lnextself(triedge)   (triedge).orient = plus1mod3[(triedge).orient]
#define	lprev(triedge1, triedge2)
#define	lprevself(triedge)   (triedge).orient = minus1mod3[(triedge).orient]
#define	onext(triedge1, triedge2)
#define	onextself(triedge)
#define	oprev(triedge1, triedge2)
#define	oprevself(triedge)
#define	dnext(triedge1, triedge2)
#define	dnextself(triedge)
#define	dprev(triedge1, triedge2)
#define	dprevself(triedge)
#define	rnext(triedge1, triedge2)
#define	rnextself(triedge)
#define	rprev(triedge1, triedge2)
#define	rprevself(triedge)
#define	org(triedge, pointptr)   pointptr = (point) (triedge).tri[plus1mod3[(triedge).orient] + 3]
#define	dest(triedge, pointptr)   pointptr = (point) (triedge).tri[minus1mod3[(triedge).orient] + 3]
#define	apex(triedge, pointptr)   pointptr = (point) (triedge).tri[(triedge).orient + 3]
#define	setorg(triedge, pointptr)   (triedge).tri[plus1mod3[(triedge).orient] + 3] = (triangle) pointptr
#define	setdest(triedge, pointptr)   (triedge).tri[minus1mod3[(triedge).orient] + 3] = (triangle) pointptr
#define	setapex(triedge, pointptr)   (triedge).tri[(triedge).orient + 3] = (triangle) pointptr
#define	setvertices2null(triedge)
#define	bond(triedge1, triedge2)
#define	dissolve(triedge)   (triedge).tri[(triedge).orient] = (triangle) dummytri
#define	triedgecopy(triedge1, triedge2)
#define	triedgeequal(triedge1, triedge2)
#define	infect(triedge)
#define	uninfect(triedge)
#define	infected(triedge)   (((unsigned long) (triedge).tri[6] & (unsigned long) 2l) != 0)
#define	elemattribute(triedge, attnum)   ((REAL *) (triedge).tri)[elemattribindex + (attnum)]
#define	setelemattribute(triedge, attnum, value)   ((REAL *) (triedge).tri)[elemattribindex + (attnum)] = value
#define	areabound(triedge)   ((REAL *) (triedge).tri)[areaboundindex]
#define	setareabound(triedge, value)   ((REAL *) (triedge).tri)[areaboundindex] = value
#define	sdecode(sptr, edge)
#define	sencode(edge)   (shelle) ((unsigned long) (edge).sh | (unsigned long) (edge).shorient)
#define	ssym(edge1, edge2)
#define	ssymself(edge)   (edge).shorient = 1 - (edge).shorient
#define	spivot(edge1, edge2)
#define	spivotself(edge)
#define	snext(edge1, edge2)
#define	snextself(edge)
#define	sorg(edge, pointptr)   pointptr = (point) (edge).sh[2 + (edge).shorient]
#define	sdest(edge, pointptr)   pointptr = (point) (edge).sh[3 - (edge).shorient]
#define	setsorg(edge, pointptr)   (edge).sh[2 + (edge).shorient] = (shelle) pointptr
#define	setsdest(edge, pointptr)   (edge).sh[3 - (edge).shorient] = (shelle) pointptr
#define	mark(edge)   (* (int *) ((edge).sh + 6))
#define	setmark(edge, value)   * (int *) ((edge).sh + 6) = value
#define	sbond(edge1, edge2)
#define	sdissolve(edge)   (edge).sh[(edge).shorient] = (shelle) dummysh
#define	shellecopy(edge1, edge2)
#define	shelleequal(edge1, edge2)
#define	tspivot(triedge, edge)
#define	stpivot(edge, triedge)
#define	tsbond(triedge, edge)
#define	tsdissolve(triedge)   (triedge).tri[6 + (triedge).orient] = (triangle) dummysh
#define	stdissolve(edge)   (edge).sh[4 + (edge).shorient] = (shelle) dummytri
#define	pointmark(pt)   ((int *) (pt))[pointmarkindex]
#define	setpointmark(pt, value)   ((int *) (pt))[pointmarkindex] = value
#define	point2tri(pt)   ((triangle *) (pt))[point2triindex]
#define	setpoint2tri(pt, value)   ((triangle *) (pt))[point2triindex] = value
#define	STARTINDEX   0
#define	Absolute(a)   ((a) >= 0.0 ? (a) : -(a))
#define	Fast_Two_Sum_Tail(a, b, x, y)
#define	Fast_Two_Sum(a, b, x, y)
#define	Two_Sum_Tail(a, b, x, y)
#define	Two_Sum(a, b, x, y)
#define	Two_Diff_Tail(a, b, x, y)
#define	Two_Diff(a, b, x, y)
#define	Split(a, ahi, alo)
#define	Two_Product_Tail(a, b, x, y)
#define	Two_Product(a, b, x, y)
#define	Two_Product_Presplit(a, b, bhi, blo, x, y)
#define	Square_Tail(a, x, y)
#define	Square(a, x, y)
#define	Two_One_Sum(a1, a0, b, x2, x1, x0)
#define	Two_One_Diff(a1, a0, b, x2, x1, x0)
#define	Two_Two_Sum(a1, a0, b1, b0, x3, x2, x1, x0)
#define	Two_Two_Diff(a1, a0, b1, b0, x3, x2, x1, x0)

Typedefs
typedef REAL **	triangle
typedef REAL **	shelle
typedef REAL *	point

Enumerations
enum	wordtype { POINTER, FLOATINGPOINT }
enum	locateresult { INTRIANGLE, ONEDGE, ONVERTEX, OUTSIDE }
enum	insertsiteresult { SUCCESSFULPOINT, ENCROACHINGPOINT, VIOLATINGPOINT, DUPLICATEPOINT }
enum	finddirectionresult { WITHIN, LEFTCOLLINEAR, RIGHTCOLLINEAR }
enum	circumcenterresult { OPPOSITEORG, OPPOSITEDEST, OPPOSITEAPEX }

Functions
void	poolrestart (struct memorypool *pool)
void	internalerror ()
void	parsecommandline (int argc, char **argv)
void	printtriangle (struct triedge *t)
void	printshelle (struct edge *s)
void	poolinit (struct memorypool *pool, int bytecount, int itemcount, enum wordtype wtype, int alignment)
void	pooldeinit (struct memorypool *pool)
VOID *	poolalloc (struct memorypool *pool)
void	pooldealloc (struct memorypool *pool, VOID *dyingitem)
void	traversalinit (struct memorypool *pool)
VOID *	traverse (struct memorypool *pool)
void	dummyinit (int trianglewords, int shellewords)
void	initializepointpool ()
void	initializetrisegpools ()
void	triangledealloc (triangle *dyingtriangle)
triangle *	triangletraverse ()
void	shelledealloc (shelle *dyingshelle)
shelle *	shelletraverse ()
void	pointdealloc (point dyingpoint)
point	pointtraverse ()
point	getpoint (int number)
void	triangledeinit ()
void	maketriangle (struct triedge *newtriedge)
void	makeshelle (struct edge *newedge)
void	exactinit ()
int	fast_expansion_sum_zeroelim (int elen, REAL *e, int flen, REAL *f, REAL *h)
int	scale_expansion_zeroelim (int elen, REAL *e, REAL b, REAL *h)
REAL	estimate (int elen, REAL *e)
REAL	counterclockwiseadapt (point pa, point pb, point pc, REAL detsum)
REAL	counterclockwise (point pa, point pb, point pc)
REAL	incircleadapt (point pa, point pb, point pc, point pd, REAL permanent)
REAL	incircle (point pa, point pb, point pc, point pd)
void	triangleinit ()
unsigned long	randomnation (unsigned int choices)
void	makepointmap ()
enum locateresult	preciselocate (point searchpoint, struct triedge *searchtri)
enum locateresult	locate (point searchpoint, struct triedge *searchtri)
void	insertshelle (struct triedge *tri, int shellemark)
void	flip (struct triedge *flipedge)
enum insertsiteresult	insertsite (point insertpoint, struct triedge *searchtri, struct edge *splitedge, int segmentflaws, int triflaws)
void	triangulatepolygon (struct triedge *firstedge, struct triedge *lastedge, int edgecount, int doflip, int triflaws)
void	pointsort (point *sortarray, int arraysize)
void	pointmedian (point *sortarray, int arraysize, int median, int axis)
void	alternateaxes (point *sortarray, int arraysize, int axis)
void	mergehulls (struct triedge *farleft, struct triedge *innerleft, struct triedge *innerright, struct triedge *farright, int axis)
void	divconqrecurse (point *sortarray, int vertices, int axis, struct triedge *farleft, struct triedge *farright)
long	removeghosts (struct triedge *startghost)
long	divconqdelaunay ()
long	delaunay ()
enum finddirectionresult	finddirection (struct triedge *searchtri, point endpoint)
void	segmentintersection (struct triedge *splittri, struct edge *splitshelle, point endpoint2)
int	scoutsegment (struct triedge *searchtri, point endpoint2, int newmark)
void	delaunayfixup (struct triedge *fixuptri, int leftside)
void	constrainededge (struct triedge *starttri, point endpoint2, int newmark)
void	insertsegment (point endpoint1, point endpoint2, int newmark)
void	markhull ()
int	formskeleton (int *segmentlist, int *segmentmarkerlist, int numberofsegments)
void	infecthull ()
void	plague ()
void	regionplague (REAL attribute, REAL area)
void	carveholes (REAL *holelist, int holes, REAL *regionlist, int regions)
enum circumcenterresult	findcircumcenter (point torg, point tdest, point tapex, point circumcenter, REAL *xi, REAL *eta)
void	highorder ()
void	transfernodes (REAL *pointlist, REAL *pointattriblist, int *pointmarkerlist, int numberofpoints, int numberofpointattribs)
void	writenodes (REAL **pointlist, REAL **pointattriblist, int **pointmarkerlist)
void	numbernodes ()
void	writeelements (int **trianglelist, REAL **triangleattriblist)
void	writepoly (int **segmentlist, int **segmentmarkerlist)
void	writeedges (int **edgelist, int **edgemarkerlist)
void	writevoronoi (REAL **vpointlist, REAL **vpointattriblist, int **vpointmarkerlist, int **vedgelist, int **vedgemarkerlist, REAL **vnormlist)
void	writeneighbors (int **neighborlist)
void	quality_statistics ()
void	statistics ()
void	triangulate (char *triswitches, struct triangulateio *in, struct triangulateio *out, struct triangulateio *vorout)

Variables
struct memorypool	triangles
struct memorypool	shelles
struct memorypool	points
struct memorypool	viri
struct memorypool	badsegments
struct memorypool	badtriangles
struct memorypool	splaynodes
struct badface *	queuefront [64]
struct badface **	queuetail [64]
REAL	xmin
REAL	xmax
REAL	ymin
REAL	ymax
REAL	xminextreme
int	inpoints
int	inelements
int	insegments
int	holes
int	regions
long	edges
int	mesh_dim
int	nextras
int	eextras
long	hullsize
int	triwords
int	shwords
int	pointmarkindex
int	point2triindex
int	highorderindex
int	elemattribindex
int	areaboundindex
int	checksegments
int	readnodefile
long	samples
unsigned long	randomseed
REAL	splitter
REAL	epsilon
REAL	resulterrbound
REAL	ccwerrboundA
REAL	ccwerrboundB
REAL	ccwerrboundC
REAL	iccerrboundA
REAL	iccerrboundB
REAL	iccerrboundC
long	incirclecount
long	counterclockcount
long	hyperbolacount
long	circumcentercount
long	circletopcount
int	poly
int	refine
int	quality
int	vararea
int	fixedarea
int	regionattrib
int	convex
int	firstnumber
int	edgesout
int	voronoi
int	neighbors
int	geomview
int	nobound
int	nopolywritten
int	nonodewritten
int	noelewritten
int	noiterationnum
int	noholes
int	noexact
int	incremental
int	sweepline
int	dwyer
int	splitseg
int	docheck
int	quiet
int	verbose
int	useshelles
int	order
int	nobisect
int	steiner
int	steinerleft
REAL	minangle
REAL	goodangle
REAL	maxarea
point	infpoint1
point	infpoint2
point	infpoint3
triangle *	dummytri
triangle *	dummytribase
shelle *	dummysh
shelle *	dummyshbase
struct triedge	recenttri
int	plus1mod3 [3] = {1, 2, 0}
int	minus1mod3 [3] = {2, 0, 1}

Macro Definition Documentation

#define Absolute

(

a

)

((a) >= 0.0 ? (a) : -(a))

#define ANSI_DECLARATIONS

#define apex	(		triedge,
			pointptr
	)		pointptr = (point) (triedge).tri[(triedge).orient + 3]

#define areabound

(

triedge

)

((REAL *) (triedge).tri)[areaboundindex]

#define BADSEGMENTPERBLOCK   252

#define BADTRIPERBLOCK   4092

#define bond	(		triedge1,
			triedge2
	)

Value:

(triedge1).tri[(triedge1).orient] = encode(triedge2);                       \
  (triedge2).tri[(triedge2).orient] = encode(triedge1)

#define CDT_ONLY

#define DEADPOINT   -1073741824

#define decode	(		ptr,
			triedge
	)

Value:

(triedge).orient = (int) ((unsigned long) (ptr) & (unsigned long) 3l);      \
  (triedge).tri = (triangle *)                                                \
                  ((unsigned long) (ptr) ^ (unsigned long) (triedge).orient)

#define dest	(		triedge,
			pointptr
	)		pointptr = (point) (triedge).tri[minus1mod3[(triedge).orient] + 3]

#define dissolve

(

triedge

)

(triedge).tri[(triedge).orient] = (triangle) dummytri

#define dnext	(		triedge1,
			triedge2
	)

Value:

sym(triedge1, triedge2);                                                    \
  lprevself(triedge2);

#define dnextself

(

triedge

)

Value:

symself(triedge);                                                           \
  lprevself(triedge);

#define dprev	(		triedge1,
			triedge2
	)

Value:

lnext(triedge1, triedge2);                                                  \
  symself(triedge2);

#define dprevself

(

triedge

)

Value:

lnextself(triedge);                                                         \
  symself(triedge);

#define elemattribute	(		triedge,
			attnum
	)		((REAL *) (triedge).tri)[elemattribindex + (attnum)]

#define encode

(

triedge

)

(triangle) ((unsigned long) (triedge).tri | (unsigned long) (triedge).orient)

#define Fast_Two_Sum	(		a,
			b,
			x,
			y
	)

Value:

x = (REAL) (a + b); \
  Fast_Two_Sum_Tail(a, b, x, y)

#define Fast_Two_Sum_Tail	(		a,
			b,
			x,
			y
	)

Value:

bvirt = x - a; \
  y = b - bvirt

#define FILENAMESIZE   512

#define INEXACT   /* Nothing */

#define infect

(

triedge

)

Value:

(triedge).tri[6] = (triangle)                                               \
                     ((unsigned long) (triedge).tri[6] | (unsigned long) 2l)

#define infected

(

triedge

)

(((unsigned long) (triedge).tri[6] & (unsigned long) 2l) != 0)

#define INPUTLINESIZE   512

#define lnext	(		triedge1,
			triedge2
	)

Value:

(triedge2).tri = (triedge1).tri;                                            \
  (triedge2).orient = plus1mod3[(triedge1).orient]

#define lnextself

(

triedge

)

(triedge).orient = plus1mod3[(triedge).orient]

#define lprev	(		triedge1,
			triedge2
	)

Value:

(triedge2).tri = (triedge1).tri;                                            \
  (triedge2).orient = minus1mod3[(triedge1).orient]

#define lprevself

(

triedge

)

(triedge).orient = minus1mod3[(triedge).orient]

#define mark

(

edge

)

(* (int *) ((edge).sh + 6))

#define NO_TIMER

#define ONETHIRD   0.333333333333333333333333333333333333333333333333333333333333

#define onext	(		triedge1,
			triedge2
	)

Value:

lprev(triedge1, triedge2);                                                  \
  symself(triedge2);

#define onextself

(

triedge

)

Value:

lprevself(triedge);                                                         \
  symself(triedge);

#define oprev	(		triedge1,
			triedge2
	)

Value:

sym(triedge1, triedge2);                                                    \
  lnextself(triedge2);

#define oprevself

(

triedge

)

Value:

symself(triedge);                                                           \
  lnextself(triedge);

#define org	(		triedge,
			pointptr
	)		pointptr = (point) (triedge).tri[plus1mod3[(triedge).orient] + 3]

#define PI   3.141592653589793238462643383279502884197169399375105820974944592308

#define point2tri

(

pt

)

((triangle *) (pt))[point2triindex]

#define pointmark

(

pt

)

((int *) (pt))[pointmarkindex]

#define POINTPERBLOCK   4092 /* Number of points allocated at once. */

#define REAL   float

#define REDUCED

#define rnext	(		triedge1,
			triedge2
	)

Value:

sym(triedge1, triedge2);                                                    \
  lnextself(triedge2);                                                        \
  symself(triedge2);

#define rnextself

(

triedge

)

Value:

symself(triedge);                                                           \
  lnextself(triedge);                                                         \
  symself(triedge);

#define rprev	(		triedge1,
			triedge2
	)

Value:

sym(triedge1, triedge2);                                                    \
  lprevself(triedge2);                                                        \
  symself(triedge2);

#define rprevself

(

triedge

)

Value:

symself(triedge);                                                           \
  lprevself(triedge);                                                         \
  symself(triedge);

#define SAMPLEFACTOR   11

#define SAMPLERATE   10

#define sbond	(		edge1,
			edge2
	)

Value:

(edge1).sh[(edge1).shorient] = sencode(edge2);                              \
  (edge2).sh[(edge2).shorient] = sencode(edge1)

#define sdecode	(		sptr,
			edge
	)

Value:

(edge).shorient = (int) ((unsigned long) (sptr) & (unsigned long) 1l);      \
  (edge).sh = (shelle *)                                                      \
              ((unsigned long) (sptr) & ~ (unsigned long) 3l)

#define sdest	(		edge,
			pointptr
	)		pointptr = (point) (edge).sh[3 - (edge).shorient]

#define sdissolve

(

edge

)

(edge).sh[(edge).shorient] = (shelle) dummysh

#define sencode

(

edge

)

(shelle) ((unsigned long) (edge).sh | (unsigned long) (edge).shorient)

#define setapex	(		triedge,
			pointptr
	)		(triedge).tri[(triedge).orient + 3] = (triangle) pointptr

#define setareabound	(		triedge,
			value
	)		((REAL *) (triedge).tri)[areaboundindex] = value

#define setdest	(		triedge,
			pointptr
	)		(triedge).tri[minus1mod3[(triedge).orient] + 3] = (triangle) pointptr

#define setelemattribute	(		triedge,
			attnum,
			value
	)		((REAL *) (triedge).tri)[elemattribindex + (attnum)] = value

#define setmark	(		edge,
			value
	)		* (int *) ((edge).sh + 6) = value

#define setorg	(		triedge,
			pointptr
	)		(triedge).tri[plus1mod3[(triedge).orient] + 3] = (triangle) pointptr

#define setpoint2tri	(		pt,
			value
	)		((triangle *) (pt))[point2triindex] = value

#define setpointmark	(		pt,
			value
	)		((int *) (pt))[pointmarkindex] = value

#define setsdest	(		edge,
			pointptr
	)		(edge).sh[3 - (edge).shorient] = (shelle) pointptr

#define setsorg	(		edge,
			pointptr
	)		(edge).sh[2 + (edge).shorient] = (shelle) pointptr

#define setvertices2null

(

triedge

)

Value:

(triedge).tri[3] = (triangle) NULL;                                         \
  (triedge).tri[4] = (triangle) NULL;                                         \
  (triedge).tri[5] = (triangle) NULL;

#define shellecopy	(		edge1,
			edge2
	)

Value:

(edge2).sh = (edge1).sh;                                                    \
  (edge2).shorient = (edge1).shorient

#define shelleequal	(		edge1,
			edge2
	)

Value:

(((edge1).sh == (edge2).sh) &&                                              \
   ((edge1).shorient == (edge2).shorient))

#define SHELLEPERBLOCK   508 /* Number of shell edges allocated at once. */

#define SINGLE

#define snext	(		edge1,
			edge2
	)

Value:

sptr = (edge1).sh[1 - (edge1).shorient];                                    \
  sdecode(sptr, edge2)

#define snextself

(

edge

)

Value:

sptr = (edge).sh[1 - (edge).shorient];                                      \
  sdecode(sptr, edge)

#define sorg	(		edge,
			pointptr
	)		pointptr = (point) (edge).sh[2 + (edge).shorient]

#define spivot	(		edge1,
			edge2
	)

Value:

sptr = (edge1).sh[(edge1).shorient];                                        \
  sdecode(sptr, edge2)

#define spivotself

(

edge

)

Value:

sptr = (edge).sh[(edge).shorient];                                          \
  sdecode(sptr, edge)

#define SPLAYNODEPERBLOCK   508

#define Split	(		a,
			ahi,
			alo
	)

Value:

c = (REAL) (splitter * a); \
  abig = (REAL) (c - a); \
  ahi = c - abig; \
  alo = a - ahi

#define Square	(		a,
			x,
			y
	)

Value:

x = (REAL) (a * a); \
  Square_Tail(a, x, y)

#define Square_Tail	(		a,
			x,
			y
	)

Value:

Split(a, ahi, alo); \
  err1 = x - (ahi * ahi); \
  err3 = err1 - ((ahi + ahi) * alo); \
  y = (alo * alo) - err3

#define SQUAREROOTTWO   1.4142135623730950488016887242096980785696718753769480732

#define ssym	(		edge1,
			edge2
	)

Value:

(edge2).sh = (edge1).sh;                                                    \
  (edge2).shorient = 1 - (edge1).shorient

#define ssymself

(

edge

)

(edge).shorient = 1 - (edge).shorient

#define STARTINDEX   0

#define stdissolve

(

edge

)

(edge).sh[4 + (edge).shorient] = (shelle) dummytri

#define stpivot	(		edge,
			triedge
	)

Value:

ptr = (triangle) (edge).sh[4 + (edge).shorient];                            \
  decode(ptr, triedge)

#define sym	(		triedge1,
			triedge2
	)

Value:

ptr = (triedge1).tri[(triedge1).orient];                                    \
  decode(ptr, triedge2);

#define symself

(

triedge

)

Value:

ptr = (triedge).tri[(triedge).orient];                                      \
  decode(ptr, triedge);

#define triedgecopy	(		triedge1,
			triedge2
	)

Value:

(triedge2).tri = (triedge1).tri;                                            \
  (triedge2).orient = (triedge1).orient

#define triedgeequal	(		triedge1,
			triedge2
	)

Value:

(((triedge1).tri == (triedge2).tri) &&                                      \
   ((triedge1).orient == (triedge2).orient))

#define TRILIBRARY

#define TRIPERBLOCK   4092 /* Number of triangles allocated at once. */

#define tsbond	(		triedge,
			edge
	)

Value:

(triedge).tri[6 + (triedge).orient] = (triangle) sencode(edge);             \
  (edge).sh[4 + (edge).shorient] = (shelle) encode(triedge)

#define tsdissolve

(

triedge

)

(triedge).tri[6 + (triedge).orient] = (triangle) dummysh

#define tspivot	(		triedge,
			edge
	)

Value:

sptr = (shelle) (triedge).tri[6 + (triedge).orient];                        \
  sdecode(sptr, edge)

#define Two_Diff	(		a,
			b,
			x,
			y
	)

Value:

x = (REAL) (a - b); \
  Two_Diff_Tail(a, b, x, y)

#define Two_Diff_Tail	(		a,
			b,
			x,
			y
	)

Value:

bvirt = (REAL) (a - x); \
  avirt = x + bvirt; \
  bround = bvirt - b; \
  around = a - avirt; \
  y = around + bround

#define Two_One_Diff	(		a1,
			a0,
			b,
			x2,
			x1,
			x0
	)

Value:

Two_Diff(a0, b , _i, x0); \
  Two_Sum( a1, _i, x2, x1)

#define Two_One_Sum	(		a1,
			a0,
			b,
			x2,
			x1,
			x0
	)

Value:

Two_Sum(a0, b , _i, x0); \
  Two_Sum(a1, _i, x2, x1)

#define Two_Product	(		a,
			b,
			x,
			y
	)

Value:

x = (REAL) (a * b); \
  Two_Product_Tail(a, b, x, y)

#define Two_Product_Presplit	(		a,
			b,
			bhi,
			blo,
			x,
			y
	)

Value:

x = (REAL) (a * b); \
  Split(a, ahi, alo); \
  err1 = x - (ahi * bhi); \
  err2 = err1 - (alo * bhi); \
  err3 = err2 - (ahi * blo); \
  y = (alo * blo) - err3

#define Two_Product_Tail	(		a,
			b,
			x,
			y
	)

Value:

Split(a, ahi, alo); \
  Split(b, bhi, blo); \
  err1 = x - (ahi * bhi); \
  err2 = err1 - (alo * bhi); \
  err3 = err2 - (ahi * blo); \
  y = (alo * blo) - err3

#define Two_Sum	(		a,
			b,
			x,
			y
	)

Value:

x = (REAL) (a + b); \
  Two_Sum_Tail(a, b, x, y)

#define Two_Sum_Tail	(		a,
			b,
			x,
			y
	)

Value:

bvirt = (REAL) (x - a); \
  avirt = x - bvirt; \
  bround = b - bvirt; \
  around = a - avirt; \
  y = around + bround

#define Two_Two_Diff	(		a1,
			a0,
			b1,
			b0,
			x3,
			x2,
			x1,
			x0
	)

Value:

Two_One_Diff(a1, a0, b0, _j, _0, x0); \
  Two_One_Diff(_j, _0, b1, x3, x2, x1)

#define Two_Two_Sum	(		a1,
			a0,
			b1,
			b0,
			x3,
			x2,
			x1,
			x0
	)

Value:

Two_One_Sum(a1, a0, b0, _j, _0, x0); \
  Two_One_Sum(_j, _0, b1, x3, x2, x1)

#define uninfect

(

triedge

)

Value:

(triedge).tri[6] = (triangle)                                               \
                     ((unsigned long) (triedge).tri[6] & ~ (unsigned long) 2l)

#define VIRUSPERBLOCK   1020 /* Number of virus triangles allocated at once. */

#define VOID   int

Typedef Documentation

typedef REAL* point

typedef REAL** shelle

typedef REAL** triangle

Enumeration Type Documentation

enum circumcenterresult

Enumerator
OPPOSITEORG
OPPOSITEDEST
OPPOSITEAPEX

enum finddirectionresult

Enumerator
WITHIN
LEFTCOLLINEAR
RIGHTCOLLINEAR

enum insertsiteresult

Enumerator
SUCCESSFULPOINT
ENCROACHINGPOINT
VIOLATINGPOINT
DUPLICATEPOINT

enum locateresult

Enumerator
INTRIANGLE
ONEDGE
ONVERTEX
OUTSIDE

enum wordtype

Enumerator
POINTER
FLOATINGPOINT

Function Documentation

void alternateaxes	(	point *	sortarray,
		int	arraysize,
		int	axis
	)

void carveholes	(	REAL *	holelist,
		int	holes,
		REAL *	regionlist,
		int	regions
	)

void constrainededge	(	struct triedge *	starttri,
		point	endpoint2,
		int	newmark
	)

REAL counterclockwise	(	point	pa,
		point	pb,
		point	pc
	)

REAL counterclockwiseadapt	(	point	pa,
		point	pb,
		point	pc,
		REAL	detsum
	)

long delaunay

(

)

void delaunayfixup	(	struct triedge *	fixuptri,
		int	leftside
	)

long divconqdelaunay

(

)

void divconqrecurse	(	point *	sortarray,
		int	vertices,
		int	axis,
		struct triedge *	farleft,
		struct triedge *	farright
	)

void dummyinit	(	int	trianglewords,
		int	shellewords
	)

REAL estimate	(	int	elen,
		REAL *	e
	)

void exactinit

(

)

int fast_expansion_sum_zeroelim	(	int	elen,
		REAL *	e,
		int	flen,
		REAL *	f,
		REAL *	h
	)

enum circumcenterresult findcircumcenter	(	point	torg,
		point	tdest,
		point	tapex,
		point	circumcenter,
		REAL *	xi,
		REAL *	eta
	)

enum finddirectionresult finddirection	(	struct triedge *	searchtri,
		point	endpoint
	)

void flip

(

struct triedge *

flipedge

)

int formskeleton	(	int *	segmentlist,
		int *	segmentmarkerlist,
		int	numberofsegments
	)

point getpoint

(

int

number

)

void highorder

(

)

REAL incircle	(	point	pa,
		point	pb,
		point	pc,
		point	pd
	)

REAL incircleadapt	(	point	pa,
		point	pb,
		point	pc,
		point	pd,
		REAL	permanent
	)

void infecthull

(

)

void initializepointpool

(

)

void initializetrisegpools

(

)

void insertsegment	(	point	endpoint1,
		point	endpoint2,
		int	newmark
	)

void insertshelle	(	struct triedge *	tri,
		int	shellemark
	)

enum insertsiteresult insertsite	(	point	insertpoint,
		struct triedge *	searchtri,
		struct edge *	splitedge,
		int	segmentflaws,
		int	triflaws
	)

void internalerror

(

)

enum locateresult locate	(	point	searchpoint,
		struct triedge *	searchtri
	)

void makepointmap

(

)

void makeshelle

(

struct edge *

newedge

)

void maketriangle

(

struct triedge *

newtriedge

)

void markhull

(

)

void mergehulls	(	struct triedge *	farleft,
		struct triedge *	innerleft,
		struct triedge *	innerright,
		struct triedge *	farright,
		int	axis
	)

void numbernodes

(

)

void parsecommandline	(	int	argc,
		char **	argv
	)

void plague

(

)

void pointdealloc

(

point

dyingpoint

)

void pointmedian	(	point *	sortarray,
		int	arraysize,
		int	median,
		int	axis
	)

void pointsort	(	point *	sortarray,
		int	arraysize
	)

point pointtraverse

(

)

VOID* poolalloc

(

struct memorypool *

pool

)

void pooldealloc	(	struct memorypool *	pool,
		VOID *	dyingitem
	)

void pooldeinit

(

struct memorypool *

pool

)

void poolinit	(	struct memorypool *	pool,
		int	bytecount,
		int	itemcount,
		enum wordtype	wtype,
		int	alignment
	)

void poolrestart

(

struct memorypool *

pool

)

enum locateresult preciselocate	(	point	searchpoint,
		struct triedge *	searchtri
	)

void printshelle

(

struct edge *

s

)

void printtriangle

(

struct triedge *

t

)

void quality_statistics

(

)

unsigned long randomnation

(

unsigned int

choices

)

void regionplague	(	REAL	attribute,
		REAL	area
	)

long removeghosts

(

struct triedge *

startghost

)

int scale_expansion_zeroelim	(	int	elen,
		REAL *	e,
		REAL	b,
		REAL *	h
	)

int scoutsegment	(	struct triedge *	searchtri,
		point	endpoint2,
		int	newmark
	)

void segmentintersection	(	struct triedge *	splittri,
		struct edge *	splitshelle,
		point	endpoint2
	)

void shelledealloc

(

shelle *

dyingshelle

)

shelle* shelletraverse

(

)

void statistics

(

)

void transfernodes	(	REAL *	pointlist,
		REAL *	pointattriblist,
		int *	pointmarkerlist,
		int	numberofpoints,
		int	numberofpointattribs
	)

void traversalinit

(

struct memorypool *

pool

)

VOID* traverse

(

struct memorypool *

pool

)

void triangledealloc

(

triangle *

dyingtriangle

)

void triangledeinit

(

)

void triangleinit

(

)

triangle* triangletraverse

(

)

void triangulate	(	char *	triswitches,
		struct triangulateio *	in,
		struct triangulateio *	out,
		struct triangulateio *	vorout
	)

void triangulatepolygon	(	struct triedge *	firstedge,
		struct triedge *	lastedge,
		int	edgecount,
		int	doflip,
		int	triflaws
	)

void writeedges	(	int **	edgelist,
		int **	edgemarkerlist
	)

void writeelements	(	int **	trianglelist,
		REAL **	triangleattriblist
	)

void writeneighbors

(

int **

neighborlist

)

void writenodes	(	REAL **	pointlist,
		REAL **	pointattriblist,
		int **	pointmarkerlist
	)

void writepoly	(	int **	segmentlist,
		int **	segmentmarkerlist
	)

void writevoronoi	(	REAL **	vpointlist,
		REAL **	vpointattriblist,
		int **	vpointmarkerlist,
		int **	vedgelist,
		int **	vedgemarkerlist,
		REAL **	vnormlist
	)

Variable Documentation

int areaboundindex

struct memorypool badsegments

struct memorypool badtriangles

REAL ccwerrboundA

REAL ccwerrboundB

REAL ccwerrboundC

int checksegments

long circletopcount

long circumcentercount

int convex

long counterclockcount

int docheck

shelle* dummysh

shelle* dummyshbase

triangle* dummytri

triangle* dummytribase

int dwyer

long edges

int edgesout

int eextras

int elemattribindex

REAL epsilon

int firstnumber

int fixedarea

int geomview

REAL goodangle

int highorderindex

int holes

long hullsize

long hyperbolacount

REAL iccerrboundA

REAL iccerrboundB

REAL iccerrboundC

long incirclecount

int incremental

int inelements

point infpoint1

point infpoint2

point infpoint3

int inpoints

int insegments

REAL maxarea

int mesh_dim

REAL minangle

int minus1mod3[3] = {2, 0, 1}

int neighbors

int nextras

int nobisect

int nobound

int noelewritten

int noexact

int noholes

int noiterationnum

int nonodewritten

int nopolywritten

int order

int plus1mod3[3] = {1, 2, 0}

int point2triindex

int pointmarkindex

struct memorypool points

int poly

int quality

struct badface* queuefront[64]

struct badface** queuetail[64]

int quiet

unsigned long randomseed

int readnodefile

struct triedge recenttri

int refine

int regionattrib

int regions

REAL resulterrbound

long samples

struct memorypool shelles

int shwords

struct memorypool splaynodes

int splitseg

REAL splitter

int steiner

int steinerleft

int sweepline

struct memorypool triangles

int triwords

int useshelles

int vararea

int verbose

struct memorypool viri

int voronoi

REAL xmax

REAL xmin

REAL xminextreme

REAL ymax

REAL ymin