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:

Go to the source code of this file.

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 }
enum  insertvertexresult { SUCCESSFULVERTEX, ENCROACHINGVERTEX, VIOLATINGVERTEX, DUPLICATEVERTEX }
enum  finddirectionresult { WITHIN, LEFTCOLLINEAR, RIGHTCOLLINEAR }

Functions

char * readline ()
char * findfield ()
int triunsuitable (triorg, tridest, triapex, area) vertex triorg

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
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.

Generated on Mon Apr 18 11:35:42 2011 for Chaste by  doxygen 1.5.5