triangle.cpp File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <sys/time.h>

Include dependency graph for triangle.cpp:

Classes
struct	otri
struct	osub
struct	badsubseg
struct	badtriang
struct	flipstacker
struct	event
struct	splaynode
struct	memorypool
struct	mesh
struct	behavior
Defines
#define	REAL double
#define	INEXACT
#define	FILENAMESIZE 2048
#define	INPUTLINESIZE 1024
#define	TRIPERBLOCK 4092
#define	SUBSEGPERBLOCK 508
#define	VERTEXPERBLOCK 4092
#define	VIRUSPERBLOCK 1020
#define	BADSUBSEGPERBLOCK 252
#define	BADTRIPERBLOCK 4092
#define	FLIPSTACKERPERBLOCK 252
#define	SPLAYNODEPERBLOCK 508
#define	INPUTVERTEX 0
#define	SEGMENTVERTEX 1
#define	FREEVERTEX 2
#define	DEADVERTEX -32768
#define	UNDEADVERTEX -32767
#define	VOID int
#define	SAMPLEFACTOR 11
#define	SAMPLERATE 10
#define	PI 3.141592653589793238462643383279502884197169399375105820974944592308
#define	SQUAREROOTTWO 1.4142135623730950488016887242096980785696718753769480732
#define	ONETHIRD 0.333333333333333333333333333333333333333333333333333333333333
#define	decode(ptr, otri)
#define	encode(otri) (triangle) ((unsigned long) (otri).tri \| (unsigned long) (otri).orient)
#define	sym(otri1, otri2)
#define	symself(otri)
#define	lnext(otri1, otri2)
#define	lnextself(otri) (otri).orient = plus1mod3[(otri).orient]
#define	lprev(otri1, otri2)
#define	lprevself(otri) (otri).orient = minus1mod3[(otri).orient]
#define	onext(otri1, otri2)
#define	onextself(otri)
#define	oprev(otri1, otri2)
#define	oprevself(otri)
#define	dnext(otri1, otri2)
#define	dnextself(otri)
#define	dprev(otri1, otri2)
#define	dprevself(otri)
#define	rnext(otri1, otri2)
#define	rnextself(otri)
#define	rprev(otri1, otri2)
#define	rprevself(otri)
#define	org(otri, vertexptr) vertexptr = (vertex) (otri).tri[plus1mod3[(otri).orient] + 3]
#define	dest(otri, vertexptr) vertexptr = (vertex) (otri).tri[minus1mod3[(otri).orient] + 3]
#define	apex(otri, vertexptr) vertexptr = (vertex) (otri).tri[(otri).orient + 3]
#define	setorg(otri, vertexptr) (otri).tri[plus1mod3[(otri).orient] + 3] = (triangle) vertexptr
#define	setdest(otri, vertexptr) (otri).tri[minus1mod3[(otri).orient] + 3] = (triangle) vertexptr
#define	setapex(otri, vertexptr) (otri).tri[(otri).orient + 3] = (triangle) vertexptr
#define	bond(otri1, otri2)
#define	dissolve(otri) (otri).tri[(otri).orient] = (triangle) m->dummytri
#define	otricopy(otri1, otri2)
#define	otriequal(otri1, otri2)
#define	infect(otri)
#define	uninfect(otri)
#define	infected(otri) (((unsigned long) (otri).tri[6] & (unsigned long) 2l) != 0l)
#define	elemattribute(otri, attnum) ((REAL *) (otri).tri)[m->elemattribindex + (attnum)]
#define	setelemattribute(otri, attnum, value) ((REAL *) (otri).tri)[m->elemattribindex + (attnum)] = value
#define	areabound(otri) ((REAL *) (otri).tri)[m->areaboundindex]
#define	setareabound(otri, value) ((REAL *) (otri).tri)[m->areaboundindex] = value
#define	deadtri(tria) ((tria)[1] == (triangle) NULL)
#define	killtri(tria)
#define	sdecode(sptr, osub)
#define	sencode(osub) (subseg) ((unsigned long) (osub).ss \| (unsigned long) (osub).ssorient)
#define	ssym(osub1, osub2)
#define	ssymself(osub) (osub).ssorient = 1 - (osub).ssorient
#define	spivot(osub1, osub2)
#define	spivotself(osub)
#define	snext(osub1, osub2)
#define	snextself(osub)
#define	sorg(osub, vertexptr) vertexptr = (vertex) (osub).ss[2 + (osub).ssorient]
#define	sdest(osub, vertexptr) vertexptr = (vertex) (osub).ss[3 - (osub).ssorient]
#define	setsorg(osub, vertexptr) (osub).ss[2 + (osub).ssorient] = (subseg) vertexptr
#define	setsdest(osub, vertexptr) (osub).ss[3 - (osub).ssorient] = (subseg) vertexptr
#define	segorg(osub, vertexptr) vertexptr = (vertex) (osub).ss[4 + (osub).ssorient]
#define	segdest(osub, vertexptr) vertexptr = (vertex) (osub).ss[5 - (osub).ssorient]
#define	setsegorg(osub, vertexptr) (osub).ss[4 + (osub).ssorient] = (subseg) vertexptr
#define	setsegdest(osub, vertexptr) (osub).ss[5 - (osub).ssorient] = (subseg) vertexptr
#define	mark(osub) (* (int *) ((osub).ss + 8))
#define	setmark(osub, value) * (int *) ((osub).ss + 8) = value
#define	sbond(osub1, osub2)
#define	sdissolve(osub) (osub).ss[(osub).ssorient] = (subseg) m->dummysub
#define	subsegcopy(osub1, osub2)
#define	subsegequal(osub1, osub2)
#define	deadsubseg(sub) ((sub)[1] == (subseg) NULL)
#define	killsubseg(sub)
#define	tspivot(otri, osub)
#define	stpivot(osub, otri)
#define	tsbond(otri, osub)
#define	tsdissolve(otri) (otri).tri[6 + (otri).orient] = (triangle) m->dummysub
#define	stdissolve(osub) (osub).ss[6 + (osub).ssorient] = (subseg) m->dummytri
#define	vertexmark(vx) ((int *) (vx))[m->vertexmarkindex]
#define	setvertexmark(vx, value) ((int *) (vx))[m->vertexmarkindex] = value
#define	vertextype(vx) ((int *) (vx))[m->vertexmarkindex + 1]
#define	setvertextype(vx, value) ((int *) (vx))[m->vertexmarkindex + 1] = value
#define	vertex2tri(vx) ((triangle *) (vx))[m->vertex2triindex]
#define	setvertex2tri(vx, value) ((triangle *) (vx))[m->vertex2triindex] = value
#define	STARTINDEX 1
#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)
#define	Two_One_Product(a1, a0, b, x3, x2, x1, x0)
Typedefs
typedef REAL **	triangle
typedef REAL **	subseg
typedef REAL *	vertex
Enumerations
enum	locateresult { INTRIANGLE, ONEDGE, ONVERTEX, OUTSIDE, INTRIANGLE, ONEDGE, ONVERTEX, OUTSIDE }
enum	insertvertexresult { SUCCESSFULVERTEX, ENCROACHINGVERTEX, VIOLATINGVERTEX, DUPLICATEVERTEX, SUCCESSFULVERTEX, ENCROACHINGVERTEX, VIOLATINGVERTEX, DUPLICATEVERTEX }
enum	finddirectionresult { WITHIN, LEFTCOLLINEAR, RIGHTCOLLINEAR, WITHIN, LEFTCOLLINEAR, RIGHTCOLLINEAR }
Functions
char *	readline ()
char *	findfield ()
int	triunsuitable (triorg, tridest, triapex, area) vertex triorg
	if (maxlen > 0.05 (triorg[0]triorg[0]+triorg[1]*triorg[1])+0.02)
Variables
REAL	splitter
REAL	epsilon
REAL	resulterrbound
REAL	ccwerrboundA
REAL	ccwerrboundB
REAL	ccwerrboundC
REAL	iccerrboundA
REAL	iccerrboundB
REAL	iccerrboundC
REAL	o3derrboundA
REAL	o3derrboundB
REAL	o3derrboundC
unsigned long	randomseed
int	plus1mod3 [3] = {1, 2, 0}
int	minus1mod3 [3] = {2, 0, 1}
vertex	tridest
vertex	triapex
REAL	area
REAL	dxoa = triorg[0] - triapex[0]
REAL	dxda = tridest[0] - triapex[0]
REAL	dxod = triorg[0] - tridest[0]
REAL	dyoa = triorg[1] - triapex[1]
REAL	dyda = tridest[1] - triapex[1]
REAL	dyod = triorg[1] - tridest[1]
REAL	oalen = dxoa * dxoa + dyoa * dyoa
REAL	dalen = dxda * dxda + dyda * dyda
REAL	odlen = dxod * dxod + dyod * dyod
REAL	maxlen = (dalen > oalen) ? dalen : oalen
char **	argv
struct behavior *	b
struct otri *	t
struct osub *	s
int	bytecount
int	itemcount
int	firstitemcount
unsigned	alignment
VOID *	dyingitem
int	trianglebytes
int	subsegbytes
triangle *	dyingtriangle
subseg *	dyingsubseg
vertex	dyingvertex
struct badsubseg *	dyingseg
int	number
struct otri *	newotri
struct osub *	newsubseg
REAL *	e
int	flen
REAL *	f
REAL *	h
vertex	pb
vertex	pc
REAL	detsum
vertex	pa
vertex	pd
REAL	permanent
REAL	aheight
REAL	bheight
REAL	cheight
REAL	dheight
vertex	torg
vertex	tdest
vertex	tapex
vertex	circumcenter
REAL *	xi
REAL *	eta
int	offcenter
struct badtriang *	badtri
struct otri *	enqtri
REAL	minedge
vertex	enqapex
vertex	enqorg
vertex	enqdest
struct osub *	testsubseg
struct otri *	testtri
vertex	searchpoint
struct otri *	searchtri
int	stopatsubsegment
struct otri *	tri
int	subsegmark
struct otri *	flipedge
vertex	newvertex
struct osub *	splitseg
int	segmentflaws
int	triflaws
struct otri *	firstedge
struct otri *	lastedge
int	edgecount
int	doflip
struct otri *	deltri
int	arraysize
int	median
int	axis
struct otri *	farleft
struct otri *	innerleft
struct otri *	innerright
struct otri *	farright
vertex *	sortarray
int	vertices
struct otri *	startghost
int	heapsize
struct event *	newevent
int	eventnum
struct event ***	eventheap
struct event **	events
struct event **	freeevents
struct otri *	fronttri
vertex	newsite
REAL	ccwabc
struct splaynode *	splaytree
struct splaynode *	splayroot
struct otri *	newkey
REAL	topy
struct otri *	bottommost
vertex	searchvertex
char *	elefilename
char *	areafilename
char *	polyfilename
FILE *	polyfile
struct otri *	splittri
struct osub *	splitsubseg
vertex	endpoint2
int	newmark
vertex	endpoint1
struct otri *	fixuptri
int	leftside
struct otri *	starttri
REAL	attribute
REAL *	holelist
int	holes
REAL *	regionlist
int	regions
FILE *	infile
char *	infilename
char *	nodefilename
REAL **	hlist
REAL **	rlist
int	argc
char *	edgefilename
char *	vnodefilename
char *	vedgefilename
char *	neighborfilename
char *	offfilename

Detailed Description

This file is part of the triangle source code, not part of Chaste per se.

We use the <autogenerated> tag to ignore it from our Doxygen checker.

Definition in file triangle.cpp.

Define Documentation

#define bond	(	otri1,
		otri2		)

Value:

(otri1).tri[(otri1).orient] = encode(otri2);                                \
  (otri2).tri[(otri2).orient] = encode(otri1)

Definition at line 1092 of file triangle.cpp.

#define decode	(	ptr,
		otri		)

Value:

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

Definition at line 947 of file triangle.cpp.

#define dnext	(	otri1,
		otri2		)

Value:

sym(otri1, otri2);                                                          \
  lprevself(otri2);

Definition at line 1021 of file triangle.cpp.

#define dnextself ( otri )

Value:

symself(otri);                                                              \
  lprevself(otri);

Definition at line 1025 of file triangle.cpp.

#define dprev	(	otri1,
		otri2		)

Value:

lnext(otri1, otri2);                                                        \
  symself(otri2);

Definition at line 1033 of file triangle.cpp.

#define dprevself ( otri )

Value:

lnextself(otri);                                                            \
  symself(otri);

Definition at line 1037 of file triangle.cpp.

#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 infect ( otri )

Value:

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

Definition at line 1119 of file triangle.cpp.

#define killsubseg ( sub )

Value:

(sub)[1] = (subseg) NULL;                                                   \
  (sub)[2] = (subseg) NULL

Definition at line 1277 of file triangle.cpp.

#define killtri ( tria )

Value:

(tria)[1] = (triangle) NULL;                                                \
  (tria)[3] = (triangle) NULL

Definition at line 1154 of file triangle.cpp.

#define lnext	(	otri1,
		otri2		)

Value:

(otri2).tri = (otri1).tri;                                                  \
  (otri2).orient = plus1mod3[(otri1).orient]

Definition at line 977 of file triangle.cpp.

#define lprev	(	otri1,
		otri2		)

Value:

(otri2).tri = (otri1).tri;                                                  \
  (otri2).orient = minus1mod3[(otri1).orient]

Definition at line 986 of file triangle.cpp.

#define onext	(	otri1,
		otri2		)

Value:

lprev(otri1, otri2);                                                        \
  symself(otri2);

Definition at line 997 of file triangle.cpp.

#define onextself ( otri )

Value:

lprevself(otri);                                                            \
  symself(otri);

Definition at line 1001 of file triangle.cpp.

#define oprev	(	otri1,
		otri2		)

Value:

sym(otri1, otri2);                                                          \
  lnextself(otri2);

Definition at line 1009 of file triangle.cpp.

#define oprevself ( otri )

Value:

symself(otri);                                                              \
  lnextself(otri);

Definition at line 1013 of file triangle.cpp.

#define otricopy	(	otri1,
		otri2		)

Value:

(otri2).tri = (otri1).tri;                                                  \
  (otri2).orient = (otri1).orient

Definition at line 1106 of file triangle.cpp.

#define otriequal	(	otri1,
		otri2		)

Value:

(((otri1).tri == (otri2).tri) &&                                            \
   ((otri1).orient == (otri2).orient))

Definition at line 1112 of file triangle.cpp.

#define rnext	(	otri1,
		otri2		)

Value:

sym(otri1, otri2);                                                          \
  lnextself(otri2);                                                           \
  symself(otri2);

Definition at line 1045 of file triangle.cpp.

#define rnextself ( otri )

Value:

symself(otri);                                                              \
  lnextself(otri);                                                            \
  symself(otri);

Definition at line 1050 of file triangle.cpp.

#define rprev	(	otri1,
		otri2		)

Value:

sym(otri1, otri2);                                                          \
  lprevself(otri2);                                                           \
  symself(otri2);

Definition at line 1059 of file triangle.cpp.

#define rprevself ( otri )

Value:

symself(otri);                                                              \
  lprevself(otri);                                                            \
  symself(otri);

Definition at line 1064 of file triangle.cpp.

#define sbond	(	osub1,
		osub2		)

Value:

(osub1).ss[(osub1).ssorient] = sencode(osub2);                              \
  (osub2).ss[(osub2).ssorient] = sencode(osub1)

Definition at line 1248 of file triangle.cpp.

#define sdecode	(	sptr,
		osub		)

Value:

(osub).ssorient = (int) ((unsigned long) (sptr) & (unsigned long) 1l);      \
  (osub).ss = (subseg *)                                                      \
              ((unsigned long) (sptr) & ~ (unsigned long) 3l)

Definition at line 1167 of file triangle.cpp.

#define snext	(	osub1,
		osub2		)

Value:

sptr = (osub1).ss[1 - (osub1).ssorient];                                    \
  sdecode(sptr, osub2)

Definition at line 1202 of file triangle.cpp.

#define snextself ( osub )

Value:

sptr = (osub).ss[1 - (osub).ssorient];                                      \
  sdecode(sptr, osub)

Definition at line 1206 of file triangle.cpp.

#define spivot	(	osub1,
		osub2		)

Value:

sptr = (osub1).ss[(osub1).ssorient];                                        \
  sdecode(sptr, osub2)

Definition at line 1191 of file triangle.cpp.

#define spivotself ( osub )

Value:

sptr = (osub).ss[(osub).ssorient];                                          \
  sdecode(sptr, osub)

Definition at line 1195 of file triangle.cpp.

#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 ssym	(	osub1,
		osub2		)

Value:

(osub2).ss = (osub1).ss;                                                    \
  (osub2).ssorient = 1 - (osub1).ssorient

Definition at line 1181 of file triangle.cpp.

#define stpivot	(	osub,
		otri		)

Value:

ptr = (triangle) (osub).ss[6 + (osub).ssorient];                            \
  decode(ptr, otri)

Definition at line 1294 of file triangle.cpp.

#define subsegcopy	(	osub1,
		osub2		)

Value:

(osub2).ss = (osub1).ss;                                                    \
  (osub2).ssorient = (osub1).ssorient

Definition at line 1260 of file triangle.cpp.

#define subsegequal	(	osub1,
		osub2		)

Value:

(((osub1).ss == (osub2).ss) &&                                              \
   ((osub1).ssorient == (osub2).ssorient))

Definition at line 1266 of file triangle.cpp.

#define sym	(	otri1,
		otri2		)

Value:

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

Definition at line 967 of file triangle.cpp.

#define symself ( otri )

Value:

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

Definition at line 971 of file triangle.cpp.

#define tsbond	(	otri,
		osub		)

Value:

(otri).tri[6 + (otri).orient] = (triangle) sencode(osub);                   \
  (osub).ss[6 + (osub).ssorient] = (subseg) encode(otri)

Definition at line 1300 of file triangle.cpp.

#define tspivot	(	otri,
		osub		)

Value:

sptr = (subseg) (otri).tri[6 + (otri).orient];                              \
  sdecode(sptr, osub)

Definition at line 1287 of file triangle.cpp.

#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_Product	(	a1,
		a0,
		b,
		x3,
		x2,
		x1,
		x0	)

Value:

Split(b, bhi, blo); \
  Two_Product_Presplit(a0, b, bhi, blo, _i, x0); \
  Two_Product_Presplit(a1, b, bhi, blo, _j, _0); \
  Two_Sum(_i, _0, _k, x1); \
  Fast_Two_Sum(_j, _k, x3, x2)

#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 ( otri )

Value:

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

Definition at line 1123 of file triangle.cpp.

Function Documentation

int triunsuitable	(	triorg	,
		tridest	,
		triapex	,
		area
	)

Variable Documentation

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

Definition at line 937 of file triangle.cpp.

Referenced by quality_statistics().

triangle.cpp File Reference

Classes

Defines

Typedefs

Enumerations

Functions

Variables

Detailed Description

Define Documentation

Function Documentation

Variable Documentation