TINA_tools  5
TINAmachinevisionlibraries
Data Structures | Defines | Typedefs | Enumerations | Functions | Variables
tlvisTrn_triangle.c File Reference
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <tinatool/tlvision/tlvisTrn_triangle.h>
Include dependency graph for tlvisTrn_triangle.c:

Go to the source code of this file.

Data Structures

struct  triedge
struct  edge
struct  badsegment
struct  badface
struct  event
struct  splaynode
struct  memorypool

Defines

#define REAL   double
#define NO_TIMER   1
#define TRILIBRARY
#define REDUCED
#define CDT_ONLY
#define INEXACT
#define FILENAMESIZE   512
#define INPUTLINESIZE   512
#define TRIPERBLOCK   4092
#define SHELLEPERBLOCK   508
#define POINTPERBLOCK   4092
#define VIRUSPERBLOCK   1020
#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 * malloc ()
void free ()
void exit ()
double strtod ()
long strtol ()
void poolrestart ()
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 poolrestart (struct memorypool *pool)
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)
triangletriangletraverse ()
void shelledealloc (shelle *dyingshelle)
shelleshelletraverse ()
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 badfacequeuefront [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
triangledummytri
triangledummytribase
shelledummysh
shelledummyshbase
struct triedge recenttri
int plus1mod3 [3] = {1, 2, 0}
int minus1mod3 [3] = {2, 0, 1}

Define Documentation

#define Absolute (   a)    ((a) >= 0.0 ? (a) : -(a))

Definition at line 3899 of file tlvisTrn_triangle.c.

Referenced by counterclockwiseadapt(), incircle(), and incircleadapt().

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

Definition at line 988 of file tlvisTrn_triangle.c.

Referenced by insertsite(), and printtriangle().

#define BADSEGMENTPERBLOCK   252

Definition at line 264 of file tlvisTrn_triangle.c.

#define BADTRIPERBLOCK   4092

Definition at line 266 of file tlvisTrn_triangle.c.

#define bond (   triedge1,
  triedge2 
)
Value:
(triedge1).tri[(triedge1).orient] = encode(triedge2);                       \
  (triedge2).tri[(triedge2).orient] = encode(triedge1)

Definition at line 938 of file tlvisTrn_triangle.c.

Referenced by divconqrecurse(), flip(), insertsite(), and mergehulls().

#define CDT_ONLY

Definition at line 232 of file tlvisTrn_triangle.c.

#define DEADPOINT   -1073741824

Definition at line 274 of file tlvisTrn_triangle.c.

Referenced by pointdealloc(), and pointtraverse().

#define decode (   ptr,
  triedge 
)
Value:
(triedge).orient = (int) ((unsigned long) (ptr) & (unsigned long) 3l);      \
  (triedge).tri = (triangle *)                                                \
                  ((unsigned long) (ptr) ^ (unsigned long) (triedge).orient)

Definition at line 788 of file tlvisTrn_triangle.c.

Referenced by insertsegment(), printshelle(), and printtriangle().

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

Definition at line 947 of file tlvisTrn_triangle.c.

Referenced by plague(), and removeghosts().

#define dnext (   triedge1,
  triedge2 
)
Value:
sym(triedge1, triedge2);                                                    \
  lprevself(triedge2);

Definition at line 862 of file tlvisTrn_triangle.c.

#define dnextself (   triedge)
Value:
symself(triedge);                                                           \
  lprevself(triedge);

Definition at line 866 of file tlvisTrn_triangle.c.

#define dprev (   triedge1,
  triedge2 
)
Value:
lnext(triedge1, triedge2);                                                  \
  symself(triedge2);

Definition at line 874 of file tlvisTrn_triangle.c.

#define dprevself (   triedge)
Value:
lnextself(triedge);                                                         \
  symself(triedge);

Definition at line 878 of file tlvisTrn_triangle.c.

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

Definition at line 980 of file tlvisTrn_triangle.c.

Referenced by insertsite(), and writeelements().

#define encode (   triedge)    (triangle) ((unsigned long) (triedge).tri | (unsigned long) (triedge).orient)

Definition at line 797 of file tlvisTrn_triangle.c.

Referenced by makepointmap(), and removeghosts().

#define Fast_Two_Sum (   a,
  b,
  x,
 
)
Value:
x = (REAL) (a + b); \
  Fast_Two_Sum_Tail(a, b, x, y)

Definition at line 3919 of file tlvisTrn_triangle.c.

Referenced by fast_expansion_sum_zeroelim(), and scale_expansion_zeroelim().

#define Fast_Two_Sum_Tail (   a,
  b,
  x,
 
)
Value:
bvirt = x - a; \
  y = b - bvirt

Definition at line 3915 of file tlvisTrn_triangle.c.

#define FILENAMESIZE   512

Definition at line 248 of file tlvisTrn_triangle.c.

Referenced by parsecommandline().

#define INEXACT
#define infect (   triedge)
Value:
(triedge).tri[6] = (triangle)                                               \
                     ((unsigned long) (triedge).tri[6] | (unsigned long) 2l)

Definition at line 965 of file tlvisTrn_triangle.c.

Referenced by carveholes(), infecthull(), plague(), and regionplague().

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

Definition at line 975 of file tlvisTrn_triangle.c.

Referenced by carveholes(), infecthull(), plague(), and regionplague().

#define INPUTLINESIZE   512

Definition at line 253 of file tlvisTrn_triangle.c.

Referenced by formskeleton().

#define lnext (   triedge1,
  triedge2 
)
Value:
(triedge2).tri = (triedge1).tri;                                            \
  (triedge2).orient = plus1mod3[(triedge1).orient]

Definition at line 818 of file tlvisTrn_triangle.c.

Referenced by constrainededge(), delaunayfixup(), divconqrecurse(), flip(), insertsite(), mergehulls(), preciselocate(), removeghosts(), and scoutsegment().

#define lnextself (   triedge)    (triedge).orient = plus1mod3[(triedge).orient]
#define lprev (   triedge1,
  triedge2 
)
Value:
(triedge2).tri = (triedge1).tri;                                            \
  (triedge2).orient = minus1mod3[(triedge1).orient]

Definition at line 827 of file tlvisTrn_triangle.c.

Referenced by divconqrecurse(), flip(), insertsite(), mergehulls(), preciselocate(), and removeghosts().

#define lprevself (   triedge)    (triedge).orient = minus1mod3[(triedge).orient]
#define mark (   edge)    (* (int *) ((edge).sh + 6))
#define NO_TIMER   1

Definition at line 206 of file tlvisTrn_triangle.c.

#define ONETHIRD   0.333333333333333333333333333333333333333333333333333333333333

Definition at line 303 of file tlvisTrn_triangle.c.

#define onext (   triedge1,
  triedge2 
)
Value:
lprev(triedge1, triedge2);                                                  \
  symself(triedge2);

Definition at line 838 of file tlvisTrn_triangle.c.

Referenced by finddirection(), plague(), and triangulatepolygon().

#define onextself (   triedge)
Value:
lprevself(triedge);                                                         \
  symself(triedge);

Definition at line 842 of file tlvisTrn_triangle.c.

Referenced by finddirection(), plague(), segmentintersection(), and triangulatepolygon().

#define oprev (   triedge1,
  triedge2 
)
Value:
sym(triedge1, triedge2);                                                    \
  lnextself(triedge2);

Definition at line 850 of file tlvisTrn_triangle.c.

Referenced by constrainededge(), infecthull(), markhull(), plague(), and triangulatepolygon().

#define oprevself (   triedge)
Value:
symself(triedge);                                                           \
  lnextself(triedge);

Definition at line 854 of file tlvisTrn_triangle.c.

Referenced by constrainededge(), finddirection(), and plague().

#define org (   triedge,
  pointptr 
)    pointptr = (point) (triedge).tri[plus1mod3[(triedge).orient] + 3]
#define PI   3.141592653589793238462643383279502884197169399375105820974944592308
#define point2tri (   pt)    ((triangle *) (pt))[point2triindex]

Definition at line 1134 of file tlvisTrn_triangle.c.

Referenced by insertsegment().

#define pointmark (   pt)    ((int *) (pt))[pointmarkindex]
#define POINTPERBLOCK   4092

Definition at line 261 of file tlvisTrn_triangle.c.

Referenced by initializepointpool().

#define REAL   double
#define REDUCED

Definition at line 231 of file tlvisTrn_triangle.c.

#define rnext (   triedge1,
  triedge2 
)
Value:
sym(triedge1, triedge2);                                                    \
  lnextself(triedge2);                                                        \
  symself(triedge2);

Definition at line 886 of file tlvisTrn_triangle.c.

#define rnextself (   triedge)
Value:
symself(triedge);                                                           \
  lnextself(triedge);                                                         \
  symself(triedge);

Definition at line 891 of file tlvisTrn_triangle.c.

#define rprev (   triedge1,
  triedge2 
)
Value:
sym(triedge1, triedge2);                                                    \
  lprevself(triedge2);                                                        \
  symself(triedge2);

Definition at line 900 of file tlvisTrn_triangle.c.

#define rprevself (   triedge)
Value:
symself(triedge);                                                           \
  lprevself(triedge);                                                         \
  symself(triedge);

Definition at line 905 of file tlvisTrn_triangle.c.

#define SAMPLEFACTOR   11

Definition at line 287 of file tlvisTrn_triangle.c.

Referenced by locate().

#define SAMPLERATE   10

Definition at line 291 of file tlvisTrn_triangle.c.

#define sbond (   edge1,
  edge2 
)
Value:
(edge1).sh[(edge1).shorient] = sencode(edge2);                              \
  (edge2).sh[(edge2).shorient] = sencode(edge1)

Definition at line 1070 of file tlvisTrn_triangle.c.

Referenced by insertsite().

#define sdecode (   sptr,
  edge 
)
Value:
(edge).shorient = (int) ((unsigned long) (sptr) & (unsigned long) 1l);      \
  (edge).sh = (shelle *)                                                      \
              ((unsigned long) (sptr) & ~ (unsigned long) 3l)

Definition at line 1002 of file tlvisTrn_triangle.c.

Referenced by printshelle(), and printtriangle().

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

Definition at line 1051 of file tlvisTrn_triangle.c.

Referenced by printshelle(), and writepoly().

#define sdissolve (   edge)    (edge).sh[(edge).shorient] = (shelle) dummysh

Definition at line 1077 of file tlvisTrn_triangle.c.

#define sencode (   edge)    (shelle) ((unsigned long) (edge).sh | (unsigned long) (edge).shorient)

Definition at line 1011 of file tlvisTrn_triangle.c.

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

Definition at line 928 of file tlvisTrn_triangle.c.

Referenced by divconqrecurse(), flip(), insertsite(), and mergehulls().

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

Definition at line 990 of file tlvisTrn_triangle.c.

Referenced by insertsite(), maketriangle(), and regionplague().

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

Definition at line 925 of file tlvisTrn_triangle.c.

Referenced by divconqrecurse(), flip(), insertsite(), and mergehulls().

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

Definition at line 983 of file tlvisTrn_triangle.c.

Referenced by carveholes(), insertsite(), maketriangle(), and regionplague().

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

Definition at line 1065 of file tlvisTrn_triangle.c.

Referenced by infecthull(), insertshelle(), makeshelle(), and plague().

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

Definition at line 922 of file tlvisTrn_triangle.c.

Referenced by divconqrecurse(), flip(), insertsite(), mergehulls(), and plague().

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

Definition at line 1136 of file tlvisTrn_triangle.c.

Referenced by makepointmap().

#define setpointmark (   pt,
  value 
)    ((int *) (pt))[pointmarkindex] = value
#define setsdest (   edge,
  pointptr 
)    (edge).sh[3 - (edge).shorient] = (shelle) pointptr

Definition at line 1057 of file tlvisTrn_triangle.c.

Referenced by insertshelle(), and insertsite().

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

Definition at line 1054 of file tlvisTrn_triangle.c.

Referenced by insertshelle().

#define setvertices2null (   triedge)
Value:
(triedge).tri[3] = (triangle) NULL;                                         \
  (triedge).tri[4] = (triangle) NULL;                                         \
  (triedge).tri[5] = (triangle) NULL;

Definition at line 931 of file tlvisTrn_triangle.c.

#define shellecopy (   edge1,
  edge2 
)
Value:
(edge2).sh = (edge1).sh;                                                    \
  (edge2).shorient = (edge1).shorient

Definition at line 1082 of file tlvisTrn_triangle.c.

Referenced by insertsite().

#define shelleequal (   edge1,
  edge2 
)
Value:
(((edge1).sh == (edge2).sh) &&                                              \
   ((edge1).shorient == (edge2).shorient))

Definition at line 1088 of file tlvisTrn_triangle.c.

#define SHELLEPERBLOCK   508

Definition at line 260 of file tlvisTrn_triangle.c.

Referenced by initializetrisegpools().

#define snext (   edge1,
  edge2 
)
Value:
sptr = (edge1).sh[1 - (edge1).shorient];                                    \
  sdecode(sptr, edge2)

Definition at line 1037 of file tlvisTrn_triangle.c.

#define snextself (   edge)
Value:
sptr = (edge).sh[1 - (edge).shorient];                                      \
  sdecode(sptr, edge)

Definition at line 1041 of file tlvisTrn_triangle.c.

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

Definition at line 1048 of file tlvisTrn_triangle.c.

Referenced by printshelle(), and writepoly().

#define spivot (   edge1,
  edge2 
)
Value:
sptr = (edge1).sh[(edge1).shorient];                                        \
  sdecode(sptr, edge2)

Definition at line 1026 of file tlvisTrn_triangle.c.

Referenced by insertsite().

#define spivotself (   edge)
Value:
sptr = (edge).sh[(edge).shorient];                                          \
  sdecode(sptr, edge)

Definition at line 1030 of file tlvisTrn_triangle.c.

#define SPLAYNODEPERBLOCK   508

Definition at line 268 of file tlvisTrn_triangle.c.

#define Split (   a,
  ahi,
  alo 
)
Value:
c = (REAL) (splitter * a); \
  abig = (REAL) (c - a); \
  ahi = c - abig; \
  alo = a - ahi

Definition at line 3945 of file tlvisTrn_triangle.c.

Referenced by scale_expansion_zeroelim().

#define Square (   a,
  x,
 
)
Value:
x = (REAL) (a * a); \
  Square_Tail(a, x, y)

Definition at line 3982 of file tlvisTrn_triangle.c.

Referenced by incircleadapt().

#define Square_Tail (   a,
  x,
 
)
Value:
Split(a, ahi, alo); \
  err1 = x - (ahi * ahi); \
  err3 = err1 - ((ahi + ahi) * alo); \
  y = (alo * alo) - err3

Definition at line 3976 of file tlvisTrn_triangle.c.

#define SQUAREROOTTWO   1.4142135623730950488016887242096980785696718753769480732

Definition at line 299 of file tlvisTrn_triangle.c.

#define ssym (   edge1,
  edge2 
)
Value:
(edge2).sh = (edge1).sh;                                                    \
  (edge2).shorient = 1 - (edge1).shorient

Definition at line 1016 of file tlvisTrn_triangle.c.

#define ssymself (   edge)    (edge).shorient = 1 - (edge).shorient

Definition at line 1020 of file tlvisTrn_triangle.c.

Referenced by insertshelle(), and insertsite().

#define STARTINDEX   0

Referenced by parsecommandline().

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

Definition at line 1122 of file tlvisTrn_triangle.c.

Referenced by plague().

#define stpivot (   edge,
  triedge 
)
Value:
ptr = (triangle) (edge).sh[4 + (edge).shorient];                            \
  decode(ptr, triedge)

Definition at line 1105 of file tlvisTrn_triangle.c.

#define sym (   triedge1,
  triedge2 
)
Value:
ptr = (triedge1).tri[(triedge1).orient];                                    \
  decode(ptr, triedge2);

Definition at line 808 of file tlvisTrn_triangle.c.

Referenced by delaunayfixup(), flip(), highorder(), insertshelle(), insertsite(), mergehulls(), plague(), preciselocate(), regionplague(), removeghosts(), triangulatepolygon(), writeedges(), writeneighbors(), and writevoronoi().

#define symself (   triedge)
Value:
ptr = (triedge).tri[(triedge).orient];                                      \
  decode(ptr, triedge);

Definition at line 812 of file tlvisTrn_triangle.c.

Referenced by carveholes(), infecthull(), insertsegment(), insertsite(), locate(), markhull(), mergehulls(), and removeghosts().

#define triedgecopy (   triedge1,
  triedge2 
)
Value:
(triedge2).tri = (triedge1).tri;                                            \
  (triedge2).orient = (triedge1).orient

Definition at line 952 of file tlvisTrn_triangle.c.

Referenced by carveholes(), divconqrecurse(), infecthull(), insertsegment(), insertsite(), locate(), markhull(), mergehulls(), preciselocate(), removeghosts(), scoutsegment(), and triangulatepolygon().

#define triedgeequal (   triedge1,
  triedge2 
)
Value:
(((triedge1).tri == (triedge2).tri) &&                                      \
   ((triedge1).orient == (triedge2).orient))

Definition at line 958 of file tlvisTrn_triangle.c.

Referenced by infecthull(), markhull(), plague(), and removeghosts().

#define TRILIBRARY

Definition at line 220 of file tlvisTrn_triangle.c.

Referenced by writeelements().

#define TRIPERBLOCK   4092

Definition at line 259 of file tlvisTrn_triangle.c.

Referenced by initializetrisegpools(), and locate().

#define tsbond (   triedge,
  edge 
)
Value:
(triedge).tri[6 + (triedge).orient] = (triangle) sencode(edge);             \
  (edge).sh[4 + (edge).shorient] = (shelle) encode(triedge)

Definition at line 1111 of file tlvisTrn_triangle.c.

Referenced by flip(), insertshelle(), and insertsite().

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

Definition at line 1117 of file tlvisTrn_triangle.c.

Referenced by flip(), insertsite(), and plague().

#define tspivot (   triedge,
  edge 
)
Value:
sptr = (shelle) (triedge).tri[6 + (triedge).orient];                        \
  sdecode(sptr, edge)

Definition at line 1098 of file tlvisTrn_triangle.c.

Referenced by constrainededge(), delaunayfixup(), flip(), highorder(), infecthull(), insertshelle(), insertsite(), plague(), regionplague(), scoutsegment(), and writeedges().

#define Two_Diff (   a,
  b,
  x,
 
)
Value:
x = (REAL) (a - b); \
  Two_Diff_Tail(a, b, x, y)

Definition at line 3941 of file tlvisTrn_triangle.c.

#define Two_Diff_Tail (   a,
  b,
  x,
 
)
Value:
bvirt = (REAL) (a - x); \
  avirt = x + bvirt; \
  bround = bvirt - b; \
  around = a - avirt; \
  y = around + bround

Definition at line 3934 of file tlvisTrn_triangle.c.

Referenced by counterclockwiseadapt(), and incircleadapt().

#define Two_One_Diff (   a1,
  a0,
  b,
  x2,
  x1,
  x0 
)
Value:
Two_Diff(a0, b , _i, x0); \
  Two_Sum( a1, _i, x2, x1)

Definition at line 3993 of file tlvisTrn_triangle.c.

#define Two_One_Sum (   a1,
  a0,
  b,
  x2,
  x1,
  x0 
)
Value:
Two_Sum(a0, b , _i, x0); \
  Two_Sum(a1, _i, x2, x1)

Definition at line 3989 of file tlvisTrn_triangle.c.

#define Two_Product (   a,
  b,
  x,
 
)
Value:
x = (REAL) (a * b); \
  Two_Product_Tail(a, b, x, y)

Definition at line 3959 of file tlvisTrn_triangle.c.

Referenced by counterclockwiseadapt(), and incircleadapt().

#define Two_Product_Presplit (   a,
  b,
  bhi,
  blo,
  x,
 
)
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

Definition at line 3966 of file tlvisTrn_triangle.c.

Referenced by scale_expansion_zeroelim().

#define Two_Product_Tail (   a,
  b,
  x,
 
)
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

Definition at line 3951 of file tlvisTrn_triangle.c.

#define Two_Sum (   a,
  b,
  x,
 
)
Value:
x = (REAL) (a + b); \
  Two_Sum_Tail(a, b, x, y)

Definition at line 3930 of file tlvisTrn_triangle.c.

Referenced by fast_expansion_sum_zeroelim(), and scale_expansion_zeroelim().

#define Two_Sum_Tail (   a,
  b,
  x,
 
)
Value:
bvirt = (REAL) (x - a); \
  avirt = x - bvirt; \
  bround = b - bvirt; \
  around = a - avirt; \
  y = around + bround

Definition at line 3923 of file tlvisTrn_triangle.c.

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

Definition at line 4001 of file tlvisTrn_triangle.c.

Referenced by counterclockwiseadapt(), and incircleadapt().

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

Definition at line 3997 of file tlvisTrn_triangle.c.

Referenced by incircleadapt().

#define uninfect (   triedge)
Value:
(triedge).tri[6] = (triangle)                                               \
                     ((unsigned long) (triedge).tri[6] & ~ (unsigned long) 2l)

Definition at line 969 of file tlvisTrn_triangle.c.

Referenced by plague(), and regionplague().

#define VIRUSPERBLOCK   1020

Definition at line 262 of file tlvisTrn_triangle.c.

Referenced by carveholes().

#define VOID   int

Typedef Documentation

typedef REAL* point

Definition at line 515 of file tlvisTrn_triangle.c.

typedef REAL** shelle

Definition at line 498 of file tlvisTrn_triangle.c.

typedef REAL** triangle

Definition at line 482 of file tlvisTrn_triangle.c.


Enumeration Type Documentation

Enumerator:
OPPOSITEORG 
OPPOSITEDEST 
OPPOSITEAPEX 

Definition at line 366 of file tlvisTrn_triangle.c.

Enumerator:
WITHIN 
LEFTCOLLINEAR 
RIGHTCOLLINEAR 

Definition at line 361 of file tlvisTrn_triangle.c.

Enumerator:
SUCCESSFULPOINT 
ENCROACHINGPOINT 
VIOLATINGPOINT 
DUPLICATEPOINT 

Definition at line 353 of file tlvisTrn_triangle.c.

Enumerator:
INTRIANGLE 
ONEDGE 
ONVERTEX 
OUTSIDE 

Definition at line 346 of file tlvisTrn_triangle.c.

enum wordtype
Enumerator:
POINTER 
FLOATINGPOINT 

Definition at line 340 of file tlvisTrn_triangle.c.


Function Documentation

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

Definition at line 7103 of file tlvisTrn_triangle.c.

References pointmedian().

Referenced by divconqdelaunay().

{
  int divider;

  divider = arraysize >> 1;
  if (arraysize <= 3) {
    /* Recursive base case:  subsets of two or three points will be      */
    /*   handled specially, and should always be sorted by x-coordinate. */
    axis = 0;
  }
  /* Partition with a horizontal or vertical cut. */
  pointmedian(sortarray, arraysize, divider, axis);
  /* Recursively partition the subsets with a cross cut. */
  if (arraysize - divider >= 2) {
    if (divider >= 2) {
      alternateaxes(sortarray, divider, 1 - axis);
    }
    alternateaxes(&sortarray[divider], arraysize - divider, 1 - axis);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 10428 of file tlvisTrn_triangle.c.

References convex, counterclockwise(), dest, dummytri, exit(), free(), holes, infect, infected, infecthull(), memorypool::items, locate(), malloc(), noholes, org, triedge::orient, OUTSIDE, plague(), POINTER, poolalloc(), pooldeinit(), poolinit(), ptr, quiet, refine, regionattrib, regionplague(), regions, setelemattribute, symself, traversalinit(), triedge::tri, triangles, triangletraverse(), triedgecopy, vararea, verbose, viri, VIRUSPERBLOCK, xmax, ymax, and ymin.

Referenced by triangulate().

{
  struct triedge searchtri;
  struct triedge triangleloop;
  struct triedge *regiontris;
  triangle **holetri;
  triangle **regiontri;
  point searchorg, searchdest;
  enum locateresult intersect;
  int i;
  triangle ptr;                         /* Temporary variable used by sym(). */

  if (!(quiet || (noholes && convex))) {
    printf("Removing unwanted triangles.\n");
    if (verbose && (holes > 0)) {
      printf("  Marking holes for elimination.\n");
    }
  }

  if (regions > 0) {
    /* Allocate storage for the triangles in which region points fall. */
    regiontris = (struct triedge *) malloc(regions * sizeof(struct triedge));
    if (regiontris == (struct triedge *) NULL) {
      printf("Error:  Out of memory.\n");
      exit(1);
    }
  }

  if (((holes > 0) && !noholes) || !convex || (regions > 0)) {
    /* Initialize a pool of viri to be used for holes, concavities, */
    /*   regional attributes, and/or regional area constraints.     */
    poolinit(&viri, sizeof(triangle *), VIRUSPERBLOCK, POINTER, 0);
  }

  if (!convex) {
    /* Mark as infected any unprotected triangles on the boundary. */
    /*   This is one way by which concavities are created.         */
    infecthull();
  }

  if ((holes > 0) && !noholes) {
    /* Infect each triangle in which a hole lies. */
    for (i = 0; i < 2 * holes; i += 2) {
      /* Ignore holes that aren't within the bounds of the mesh. */
      if ((holelist[i] >= xmin) && (holelist[i] <= xmax)
          && (holelist[i + 1] >= ymin) && (holelist[i + 1] <= ymax)) {
        /* Start searching from some triangle on the outer boundary. */
        searchtri.tri = dummytri;
        searchtri.orient = 0;
        symself(searchtri);
        /* Ensure that the hole is to the left of this boundary edge; */
        /*   otherwise, locate() will falsely report that the hole    */
        /*   falls within the starting triangle.                      */
        org(searchtri, searchorg);
        dest(searchtri, searchdest);
        if (counterclockwise(searchorg, searchdest, &holelist[i]) > 0.0) {
          /* Find a triangle that contains the hole. */
          intersect = locate(&holelist[i], &searchtri);
          if ((intersect != OUTSIDE) && (!infected(searchtri))) {
            /* Infect the triangle.  This is done by marking the triangle */
            /*   as infect and including the triangle in the virus pool.  */
            infect(searchtri);
            holetri = (triangle **) poolalloc(&viri);
            *holetri = searchtri.tri;
          }
        }
      }
    }
  }

  /* Now, we have to find all the regions BEFORE we carve the holes, because */
  /*   locate() won't work when the triangulation is no longer convex.       */
  /*   (Incidentally, this is the reason why regional attributes and area    */
  /*   constraints can't be used when refining a preexisting mesh, which     */
  /*   might not be convex; they can only be used with a freshly             */
  /*   triangulated PSLG.)                                                   */
  if (regions > 0) {
    /* Find the starting triangle for each region. */
    for (i = 0; i < regions; i++) {
      regiontris[i].tri = dummytri;
      /* Ignore region points that aren't within the bounds of the mesh. */
      if ((regionlist[4 * i] >= xmin) && (regionlist[4 * i] <= xmax) &&
          (regionlist[4 * i + 1] >= ymin) && (regionlist[4 * i + 1] <= ymax)) {
        /* Start searching from some triangle on the outer boundary. */
        searchtri.tri = dummytri;
        searchtri.orient = 0;
        symself(searchtri);
        /* Ensure that the region point is to the left of this boundary */
        /*   edge; otherwise, locate() will falsely report that the     */
        /*   region point falls within the starting triangle.           */
        org(searchtri, searchorg);
        dest(searchtri, searchdest);
        if (counterclockwise(searchorg, searchdest, &regionlist[4 * i]) >
            0.0) {
          /* Find a triangle that contains the region point. */
          intersect = locate(&regionlist[4 * i], &searchtri);
          if ((intersect != OUTSIDE) && (!infected(searchtri))) {
            /* Record the triangle for processing after the */
            /*   holes have been carved.                    */
            triedgecopy(searchtri, regiontris[i]);
          }
        }
      }
    }
  }

  if (viri.items > 0) {
    /* Carve the holes and concavities. */
    plague();
  }
  /* The virus pool should be empty now. */

  if (regions > 0) {
    if (!quiet) {
      if (regionattrib) {
        if (vararea) {
          printf("Spreading regional attributes and area constraints.\n");
        } else {
          printf("Spreading regional attributes.\n");
        }
      } else { 
        printf("Spreading regional area constraints.\n");
      }
    }
    if (regionattrib && !refine) {
      /* Assign every triangle a regional attribute of zero. */
      traversalinit(&triangles);
      triangleloop.orient = 0;
      triangleloop.tri = triangletraverse();
      while (triangleloop.tri != (triangle *) NULL) {
        setelemattribute(triangleloop, eextras, 0.0);
        triangleloop.tri = triangletraverse();
      }
    }
    for (i = 0; i < regions; i++) {
      if (regiontris[i].tri != dummytri) {
        /* Make sure the triangle under consideration still exists. */
        /*   It may have been eaten by the virus.                   */
        if (regiontris[i].tri[3] != (triangle) NULL) {
          /* Put one triangle in the virus pool. */
          infect(regiontris[i]);
          regiontri = (triangle **) poolalloc(&viri);
          *regiontri = regiontris[i].tri;
          /* Apply one region's attribute and/or area constraint. */
          regionplague(regionlist[4 * i + 2], regionlist[4 * i + 3]);
          /* The virus pool should be empty now. */
        }
      }
    }
    if (regionattrib && !refine) {
      /* Note the fact that each triangle has an additional attribute. */
      eextras++;
    }
  }

  /* Free up memory. */
  if (((holes > 0) && !noholes) || !convex || (regions > 0)) {
    pooldeinit(&viri);
  }
  if (regions > 0) {
    free(regiontris);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 9666 of file tlvisTrn_triangle.c.

References area, counterclockwise(), delaunayfixup(), dummysh, flip(), insertshelle(), lnext, lprevself, oprev, oprevself, org, ptr, REAL, scoutsegment(), segmentintersection(), edge::sh, and tspivot.

Referenced by insertsegment().

{
  struct triedge fixuptri, fixuptri2;
  struct edge fixupedge;
  point endpoint1;
  point farpoint;
  REAL area;
  int collision;
  int done;
  triangle ptr;             /* Temporary variable used by sym() and oprev(). */
  shelle sptr;                      /* Temporary variable used by tspivot(). */

  org(*starttri, endpoint1);
  lnext(*starttri, fixuptri);
  flip(&fixuptri);
  /* `collision' indicates whether we have found a point directly */
  /*   between endpoint1 and endpoint2.                           */
  collision = 0;
  done = 0;
  do {
    org(fixuptri, farpoint);
    /* `farpoint' is the extreme point of the polygon we are "digging" */
    /*   to get from endpoint1 to endpoint2.                           */
    if ((farpoint[0] == endpoint2[0]) && (farpoint[1] == endpoint2[1])) {
      oprev(fixuptri, fixuptri2);
      /* Enforce the Delaunay condition around endpoint2. */
      delaunayfixup(&fixuptri, 0);
      delaunayfixup(&fixuptri2, 1);
      done = 1;
    } else {
      /* Check whether farpoint is to the left or right of the segment */
      /*   being inserted, to decide which edge of fixuptri to dig     */
      /*   through next.                                               */
      area = counterclockwise(endpoint1, endpoint2, farpoint);
      if (area == 0.0) {
        /* We've collided with a point between endpoint1 and endpoint2. */
        collision = 1;
        oprev(fixuptri, fixuptri2);
        /* Enforce the Delaunay condition around farpoint. */
        delaunayfixup(&fixuptri, 0);
        delaunayfixup(&fixuptri2, 1);
        done = 1;
      } else {
        if (area > 0.0) {         /* farpoint is to the left of the segment. */
          oprev(fixuptri, fixuptri2);
          /* Enforce the Delaunay condition around farpoint, on the */
          /*   left side of the segment only.                       */
          delaunayfixup(&fixuptri2, 1);
          /* Flip the edge that crosses the segment.  After the edge is */
          /*   flipped, one of its endpoints is the fan vertex, and the */
          /*   destination of fixuptri is the fan vertex.               */
          lprevself(fixuptri);
        } else {                 /* farpoint is to the right of the segment. */
          delaunayfixup(&fixuptri, 0);
          /* Flip the edge that crosses the segment.  After the edge is */
          /*   flipped, one of its endpoints is the fan vertex, and the */
          /*   destination of fixuptri is the fan vertex.               */
          oprevself(fixuptri);
        }
        /* Check for two intersecting segments. */
        tspivot(fixuptri, fixupedge);
        if (fixupedge.sh == dummysh) {
          flip(&fixuptri);   /* May create an inverted triangle on the left. */
        } else {
          /* We've collided with a segment between endpoint1 and endpoint2. */
          collision = 1;
          /* Insert a point at the intersection. */
          segmentintersection(&fixuptri, &fixupedge, endpoint2);
          done = 1;
        }
      }
    }
  } while (!done);
  /* Insert a shell edge to make the segment permanent. */
  insertshelle(&fixuptri, newmark);
  /* If there was a collision with an interceding vertex, install another */
  /*   segment connecting that vertex with endpoint2.                     */
  if (collision) {
    /* Insert the remainder of the segment. */
    if (!scoutsegment(&fixuptri, endpoint2, newmark)) {
      constrainededge(&fixuptri, endpoint2, newmark);
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 4335 of file tlvisTrn_triangle.c.

References ccwerrboundA, counterclockcount, counterclockwiseadapt(), noexact, and REAL.

Referenced by carveholes(), constrainededge(), delaunayfixup(), divconqrecurse(), findcircumcenter(), finddirection(), insertsite(), locate(), mergehulls(), preciselocate(), and quality_statistics().

{
  REAL detleft, detright, det;
  REAL detsum, errbound;

  counterclockcount++;

  detleft = (pa[0] - pc[0]) * (pb[1] - pc[1]);
  detright = (pa[1] - pc[1]) * (pb[0] - pc[0]);
  det = detleft - detright;

  if (noexact) {
    return det;
  }

  if (detleft > 0.0) {
    if (detright <= 0.0) {
      return det;
    } else {
      detsum = detleft + detright;
    }
  } else if (detleft < 0.0) {
    if (detright >= 0.0) {
      return det;
    } else {
      detsum = -detleft - detright;
    }
  } else {
    return det;
  }

  errbound = ccwerrboundA * detsum;
  if ((det >= errbound) || (-det >= errbound)) {
    return det;
  }

  return counterclockwiseadapt(pa, pb, pc, detsum);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 4251 of file tlvisTrn_triangle.c.

References Absolute, ccwerrboundB, ccwerrboundC, estimate(), fast_expansion_sum_zeroelim(), INEXACT, REAL, resulterrbound, Two_Diff_Tail, Two_Product, Two_Two_Diff, and u.

Referenced by counterclockwise().

{
  INEXACT REAL acx, acy, bcx, bcy;
  REAL acxtail, acytail, bcxtail, bcytail;
  INEXACT REAL detleft, detright;
  REAL detlefttail, detrighttail;
  REAL det, errbound;
  REAL B[4], C1[8], C2[12], D[16];
  INEXACT REAL B3;
  int C1length, C2length, Dlength;
  REAL u[4];
  INEXACT REAL u3;
  INEXACT REAL s1, t1;
  REAL s0, t0;

  INEXACT REAL bvirt;
  REAL avirt, bround, around;
  INEXACT REAL c;
  INEXACT REAL abig;
  REAL ahi, alo, bhi, blo;
  REAL err1, err2, err3;
  INEXACT REAL _i, _j;
  REAL _0;

  acx = (REAL) (pa[0] - pc[0]);
  bcx = (REAL) (pb[0] - pc[0]);
  acy = (REAL) (pa[1] - pc[1]);
  bcy = (REAL) (pb[1] - pc[1]);

  Two_Product(acx, bcy, detleft, detlefttail);
  Two_Product(acy, bcx, detright, detrighttail);

  Two_Two_Diff(detleft, detlefttail, detright, detrighttail,
               B3, B[2], B[1], B[0]);
  B[3] = B3;

  det = estimate(4, B);
  errbound = ccwerrboundB * detsum;
  if ((det >= errbound) || (-det >= errbound)) {
    return det;
  }

  Two_Diff_Tail(pa[0], pc[0], acx, acxtail);
  Two_Diff_Tail(pb[0], pc[0], bcx, bcxtail);
  Two_Diff_Tail(pa[1], pc[1], acy, acytail);
  Two_Diff_Tail(pb[1], pc[1], bcy, bcytail);

  if ((acxtail == 0.0) && (acytail == 0.0)
      && (bcxtail == 0.0) && (bcytail == 0.0)) {
    return det;
  }

  errbound = ccwerrboundC * detsum + resulterrbound * Absolute(det);
  det += (acx * bcytail + bcy * acxtail)
       - (acy * bcxtail + bcx * acytail);
  if ((det >= errbound) || (-det >= errbound)) {
    return det;
  }

  Two_Product(acxtail, bcy, s1, s0);
  Two_Product(acytail, bcx, t1, t0);
  Two_Two_Diff(s1, s0, t1, t0, u3, u[2], u[1], u[0]);
  u[3] = u3;
  C1length = fast_expansion_sum_zeroelim(4, B, 4, u, C1);

  Two_Product(acx, bcytail, s1, s0);
  Two_Product(acy, bcxtail, t1, t0);
  Two_Two_Diff(s1, s0, t1, t0, u3, u[2], u[1], u[0]);
  u[3] = u3;
  C2length = fast_expansion_sum_zeroelim(C1length, C1, 4, u, C2);

  Two_Product(acxtail, bcytail, s1, s0);
  Two_Product(acytail, bcxtail, t1, t0);
  Two_Two_Diff(s1, s0, t1, t0, u3, u[2], u[1], u[0]);
  u[3] = u3;
  Dlength = fast_expansion_sum_zeroelim(C2length, C2, 4, u, D);

  return(D[Dlength - 1]);
}

Here is the call graph for this function:

Here is the caller graph for this function:

long delaunay ( )

Definition at line 8632 of file tlvisTrn_triangle.c.

References divconqdelaunay(), eextras, incremental, initializetrisegpools(), quiet, and sweepline.

Referenced by triangulate().

{
  eextras = 0;
  initializetrisegpools();

#ifdef REDUCED
  if (!quiet) {
    printf(
      "Constructing Delaunay triangulation by divide-and-conquer method.\n");
  }
  return divconqdelaunay();
#else /* not REDUCED */
  if (!quiet) {
    printf("Constructing Delaunay triangulation ");
    if (incremental) {
      printf("by incremental method.\n");
    } else if (sweepline) {
      printf("by sweepline method.\n");
    } else {
      printf("by divide-and-conquer method.\n");
    }
  }
  if (incremental) {
    return incrementaldelaunay();
  } else if (sweepline) {
    return sweeplinedelaunay();
  } else {
    return divconqdelaunay();
  }
#endif /* not REDUCED */
}

Here is the call graph for this function:

Here is the caller graph for this function:

void delaunayfixup ( struct triedge fixuptri,
int  leftside 
)

Definition at line 9555 of file tlvisTrn_triangle.c.

References apex, counterclockwise(), dest, dummysh, dummytri, flip(), incircle(), lnext, lprevself, org, ptr, edge::sh, sym, triedge::tri, and tspivot.

Referenced by constrainededge().

{
  struct triedge neartri;
  struct triedge fartri;
  struct edge faredge;
  point nearpoint, leftpoint, rightpoint, farpoint;
  triangle ptr;                         /* Temporary variable used by sym(). */
  shelle sptr;                      /* Temporary variable used by tspivot(). */

  lnext(*fixuptri, neartri);
  sym(neartri, fartri);
  /* Check if the edge opposite the origin of fixuptri can be flipped. */
  if (fartri.tri == dummytri) {
    return;
  }
  tspivot(neartri, faredge);
  if (faredge.sh != dummysh) {
    return;
  }
  /* Find all the relevant vertices. */
  apex(neartri, nearpoint);
  org(neartri, leftpoint);
  dest(neartri, rightpoint);
  apex(fartri, farpoint);
  /* Check whether the previous polygon vertex is a reflex vertex. */
  if (leftside) {
    if (counterclockwise(nearpoint, leftpoint, farpoint) <= 0.0) {
      /* leftpoint is a reflex vertex too.  Nothing can */
      /*   be done until a convex section is found.     */
      return;
    }
  } else {
    if (counterclockwise(farpoint, rightpoint, nearpoint) <= 0.0) {
      /* rightpoint is a reflex vertex too.  Nothing can */
      /*   be done until a convex section is found.      */
      return;
    }
  }
  if (counterclockwise(rightpoint, leftpoint, farpoint) > 0.0) {
    /* fartri is not an inverted triangle, and farpoint is not a reflex */
    /*   vertex.  As there are no reflex vertices, fixuptri isn't an    */
    /*   inverted triangle, either.  Hence, test the edge between the   */
    /*   triangles to ensure it is locally Delaunay.                    */
    if (incircle(leftpoint, farpoint, rightpoint, nearpoint) <= 0.0) {
      return;
    }
    /* Not locally Delaunay; go on to an edge flip. */
  }        /* else fartri is inverted; remove it from the stack by flipping. */
  flip(&neartri);
  lprevself(*fixuptri);    /* Restore the origin of fixuptri after the flip. */
  /* Recursively process the two triangles that result from the flip. */
  delaunayfixup(fixuptri, leftside);
  delaunayfixup(&fartri, leftside);
}

Here is the call graph for this function:

Here is the caller graph for this function:

long divconqdelaunay ( )

Definition at line 7683 of file tlvisTrn_triangle.c.

References alternateaxes(), divconqrecurse(), dwyer, exit(), free(), inpoints, malloc(), points, pointsort(), pointtraverse(), quiet, removeghosts(), traversalinit(), and verbose.

Referenced by delaunay().

{
  point *sortarray;
  struct triedge hullleft, hullright;
  int divider;
  int i, j;

  /* Allocate an array of pointers to points for sorting. */
  sortarray = (point *) malloc(inpoints * sizeof(point));
  if (sortarray == (point *) NULL) {
    printf("Error:  Out of memory.\n");
    exit(1);
  }
  traversalinit(&points);
  for (i = 0; i < inpoints; i++) {
    sortarray[i] = pointtraverse();
  }
  if (verbose) {
    printf("  Sorting points.\n");
  }
  /* Sort the points. */
  pointsort(sortarray, inpoints);
  /* Discard duplicate points, which can really mess up the algorithm. */
  i = 0;
  for (j = 1; j < inpoints; j++) {
    if ((sortarray[i][0] == sortarray[j][0])
        && (sortarray[i][1] == sortarray[j][1])) {
      if (!quiet) {
        printf(
"Warning:  A duplicate point at (%.12g, %.12g) appeared and was ignored.\n",
               sortarray[j][0], sortarray[j][1]);
      }
/*  Commented out - would eliminate point from output .node file, but causes
    a failure if some segment has this point as an endpoint.
      setpointmark(sortarray[j], DEADPOINT);
*/
    } else {
      i++;
      sortarray[i] = sortarray[j];
    }
  }
  i++;
  if (dwyer) {
    /* Re-sort the array of points to accommodate alternating cuts. */
    divider = i >> 1;
    if (i - divider >= 2) {
      if (divider >= 2) {
        alternateaxes(sortarray, divider, 1);
      }
      alternateaxes(&sortarray[divider], i - divider, 1);
    }
  }
  if (verbose) {
    printf("  Forming triangulation.\n");
  }
  /* Form the Delaunay triangulation. */
  divconqrecurse(sortarray, i, 0, &hullleft, &hullright);
  free(sortarray);

  return removeghosts(&hullleft);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 7472 of file tlvisTrn_triangle.c.

References area, bond, counterclockwise(), lnext, lnextself, lprev, lprevself, maketriangle(), mergehulls(), printtriangle(), REAL, setapex, setdest, setorg, triedgecopy, and verbose.

Referenced by divconqdelaunay().

{
  struct triedge midtri, tri1, tri2, tri3;
  struct triedge innerleft, innerright;
  REAL area;
  int divider;

  if (verbose > 2) {
    printf("  Triangulating %d points.\n", vertices);
  }
  if (vertices == 2) {
    /* The triangulation of two vertices is an edge.  An edge is */
    /*   represented by two bounding triangles.                  */
    maketriangle(farleft);
    setorg(*farleft, sortarray[0]);
    setdest(*farleft, sortarray[1]);
    /* The apex is intentionally left NULL. */
    maketriangle(farright);
    setorg(*farright, sortarray[1]);
    setdest(*farright, sortarray[0]);
    /* The apex is intentionally left NULL. */
    bond(*farleft, *farright);
    lprevself(*farleft);
    lnextself(*farright);
    bond(*farleft, *farright);
    lprevself(*farleft);
    lnextself(*farright);
    bond(*farleft, *farright);
    if (verbose > 2) {
      printf("  Creating ");
      printtriangle(farleft);
      printf("  Creating ");
      printtriangle(farright);
    }
    /* Ensure that the origin of `farleft' is sortarray[0]. */
    lprev(*farright, *farleft);
    return;
  } else if (vertices == 3) {
    /* The triangulation of three vertices is either a triangle (with */
    /*   three bounding triangles) or two edges (with four bounding   */
    /*   triangles).  In either case, four triangles are created.     */
    maketriangle(&midtri);
    maketriangle(&tri1);
    maketriangle(&tri2);
    maketriangle(&tri3);
    area = counterclockwise(sortarray[0], sortarray[1], sortarray[2]);
    if (area == 0.0) {
      /* Three collinear points; the triangulation is two edges. */
      setorg(midtri, sortarray[0]);
      setdest(midtri, sortarray[1]);
      setorg(tri1, sortarray[1]);
      setdest(tri1, sortarray[0]);
      setorg(tri2, sortarray[2]);
      setdest(tri2, sortarray[1]);
      setorg(tri3, sortarray[1]);
      setdest(tri3, sortarray[2]);
      /* All apices are intentionally left NULL. */
      bond(midtri, tri1);
      bond(tri2, tri3);
      lnextself(midtri);
      lprevself(tri1);
      lnextself(tri2);
      lprevself(tri3);
      bond(midtri, tri3);
      bond(tri1, tri2);
      lnextself(midtri);
      lprevself(tri1);
      lnextself(tri2);
      lprevself(tri3);
      bond(midtri, tri1);
      bond(tri2, tri3);
      /* Ensure that the origin of `farleft' is sortarray[0]. */
      triedgecopy(tri1, *farleft);
      /* Ensure that the destination of `farright' is sortarray[2]. */
      triedgecopy(tri2, *farright);
    } else {
      /* The three points are not collinear; the triangulation is one */
      /*   triangle, namely `midtri'.                                 */
      setorg(midtri, sortarray[0]);
      setdest(tri1, sortarray[0]);
      setorg(tri3, sortarray[0]);
      /* Apices of tri1, tri2, and tri3 are left NULL. */
      if (area > 0.0) {
        /* The vertices are in counterclockwise order. */
        setdest(midtri, sortarray[1]);
        setorg(tri1, sortarray[1]);
        setdest(tri2, sortarray[1]);
        setapex(midtri, sortarray[2]);
        setorg(tri2, sortarray[2]);
        setdest(tri3, sortarray[2]);
      } else {
        /* The vertices are in clockwise order. */
        setdest(midtri, sortarray[2]);
        setorg(tri1, sortarray[2]);
        setdest(tri2, sortarray[2]);
        setapex(midtri, sortarray[1]);
        setorg(tri2, sortarray[1]);
        setdest(tri3, sortarray[1]);
      }
      /* The topology does not depend on how the vertices are ordered. */
      bond(midtri, tri1);
      lnextself(midtri);
      bond(midtri, tri2);
      lnextself(midtri);
      bond(midtri, tri3);
      lprevself(tri1);
      lnextself(tri2);
      bond(tri1, tri2);
      lprevself(tri1);
      lprevself(tri3);
      bond(tri1, tri3);
      lnextself(tri2);
      lprevself(tri3);
      bond(tri2, tri3);
      /* Ensure that the origin of `farleft' is sortarray[0]. */
      triedgecopy(tri1, *farleft);
      /* Ensure that the destination of `farright' is sortarray[2]. */
      if (area > 0.0) {
        triedgecopy(tri2, *farright);
      } else {
        lnext(*farleft, *farright);
      }
    }
    if (verbose > 2) {
      printf("  Creating ");
      printtriangle(&midtri);
      printf("  Creating ");
      printtriangle(&tri1);
      printf("  Creating ");
      printtriangle(&tri2);
      printf("  Creating ");
      printtriangle(&tri3);
    }
    return;
  } else {
    /* Split the vertices in half. */
    divider = vertices >> 1;
    /* Recursively triangulate each half. */
    divconqrecurse(sortarray, divider, 1 - axis, farleft, &innerleft);
    divconqrecurse(&sortarray[divider], vertices - divider, 1 - axis,
                   &innerright, farright);
    if (verbose > 1) {
      printf("  Joining triangulations with %d and %d vertices.\n", divider,
             vertices - divider);
    }
    /* Merge the two triangulations into one. */
    mergehulls(farleft, &innerleft, &innerright, farright, axis);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void dummyinit ( int  trianglewords,
int  shellewords 
)

Definition at line 3435 of file tlvisTrn_triangle.c.

References memorypool::alignbytes, dummysh, dummyshbase, dummytri, dummytribase, exit(), malloc(), shelles, shwords, triangles, triwords, and useshelles.

Referenced by initializetrisegpools().

{
  unsigned long alignptr;

  /* `triwords' and `shwords' are used by the mesh manipulation primitives */
  /*   to extract orientations of triangles and shell edges from pointers. */
  triwords = trianglewords;       /* Initialize `triwords' once and for all. */
  shwords = shellewords;           /* Initialize `shwords' once and for all. */

  /* Set up `dummytri', the `triangle' that occupies "outer space". */
  dummytribase = (triangle *) malloc(triwords * sizeof(triangle)
                                     + triangles.alignbytes);
  if (dummytribase == (triangle *) NULL) {
    printf("Error:  Out of memory.\n");
    exit(1);
  }
  /* Align `dummytri' on a `triangles.alignbytes'-byte boundary. */
  alignptr = (unsigned long) dummytribase;
  dummytri = (triangle *)
    (alignptr + (unsigned long) triangles.alignbytes
     - (alignptr % (unsigned long) triangles.alignbytes));
  /* Initialize the three adjoining triangles to be "outer space".  These  */
  /*   will eventually be changed by various bonding operations, but their */
  /*   values don't really matter, as long as they can legally be          */
  /*   dereferenced.                                                       */
  dummytri[0] = (triangle) dummytri;
  dummytri[1] = (triangle) dummytri;
  dummytri[2] = (triangle) dummytri;
  /* Three NULL vertex points. */
  dummytri[3] = (triangle) NULL;
  dummytri[4] = (triangle) NULL;
  dummytri[5] = (triangle) NULL;

  if (useshelles) {
    /* Set up `dummysh', the omnipresent "shell edge" pointed to by any      */
    /*   triangle side or shell edge end that isn't attached to a real shell */
    /*   edge.                                                               */
    dummyshbase = (shelle *) malloc(shwords * sizeof(shelle)
                                    + shelles.alignbytes);
    if (dummyshbase == (shelle *) NULL) {
      printf("Error:  Out of memory.\n");
      exit(1);
    }
    /* Align `dummysh' on a `shelles.alignbytes'-byte boundary. */
    alignptr = (unsigned long) dummyshbase;
    dummysh = (shelle *)
      (alignptr + (unsigned long) shelles.alignbytes
       - (alignptr % (unsigned long) shelles.alignbytes));
    /* Initialize the two adjoining shell edges to be the omnipresent shell */
    /*   edge.  These will eventually be changed by various bonding         */
    /*   operations, but their values don't really matter, as long as they  */
    /*   can legally be dereferenced.                                       */
    dummysh[0] = (shelle) dummysh;
    dummysh[1] = (shelle) dummysh;
    /* Two NULL vertex points. */
    dummysh[2] = (shelle) NULL;
    dummysh[3] = (shelle) NULL;
    /* Initialize the two adjoining triangles to be "outer space". */
    dummysh[4] = (shelle) dummytri;
    dummysh[5] = (shelle) dummytri;
    /* Set the boundary marker to zero. */
    * (int *) (dummysh + 6) = 0;

    /* Initialize the three adjoining shell edges of `dummytri' to be */
    /*   the omnipresent shell edge.                                  */
    dummytri[6] = (triangle) dummysh;
    dummytri[7] = (triangle) dummysh;
    dummytri[8] = (triangle) dummysh;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

REAL estimate ( int  elen,
REAL *  e 
)

Definition at line 4217 of file tlvisTrn_triangle.c.

References REAL.

Referenced by counterclockwiseadapt(), and incircleadapt().

{
  REAL Q;
  int eindex;

  Q = e[0];
  for (eindex = 1; eindex < elen; eindex++) {
    Q += e[eindex];
  }
  return Q;
}

Here is the caller graph for this function:

void exactinit ( )

Definition at line 4024 of file tlvisTrn_triangle.c.

References ccwerrboundA, ccwerrboundB, ccwerrboundC, epsilon, iccerrboundA, iccerrboundB, iccerrboundC, REAL, resulterrbound, splitter, and verbose.

Referenced by triangleinit().

{
  REAL half;
  REAL check, lastcheck;
  int every_other;

  every_other = 1;
  half = 0.5;
  epsilon = 1.0;
  splitter = 1.0;
  check = 1.0;
  /* Repeatedly divide `epsilon' by two until it is too small to add to      */
  /*   one without causing roundoff.  (Also check if the sum is equal to     */
  /*   the previous sum, for machines that round up instead of using exact   */
  /*   rounding.  Not that these routines will work on such machines anyway. */
  do {
    lastcheck = check;
    epsilon *= half;
    if (every_other) {
      splitter *= 2.0;
    }
    every_other = !every_other;
    check = 1.0 + epsilon;
  } while ((check != 1.0) && (check != lastcheck));
  splitter += 1.0;
  if (verbose > 1) {
    printf("Floating point roundoff is of magnitude %.17g\n", epsilon);
    printf("Floating point splitter is %.17g\n", splitter);
  }
  /* Error bounds for orientation and incircle tests. */
  resulterrbound = (3.0 + 8.0 * epsilon) * epsilon;
  ccwerrboundA = (3.0 + 16.0 * epsilon) * epsilon;
  ccwerrboundB = (2.0 + 12.0 * epsilon) * epsilon;
  ccwerrboundC = (9.0 + 64.0 * epsilon) * epsilon * epsilon;
  iccerrboundA = (10.0 + 96.0 * epsilon) * epsilon;
  iccerrboundB = (4.0 + 48.0 * epsilon) * epsilon;
  iccerrboundC = (44.0 + 576.0 * epsilon) * epsilon * epsilon;
}

Here is the caller graph for this function:

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

Definition at line 4077 of file tlvisTrn_triangle.c.

References Fast_Two_Sum, INEXACT, REAL, and Two_Sum.

Referenced by counterclockwiseadapt(), and incircleadapt().

{
  REAL Q;
  INEXACT REAL Qnew;
  INEXACT REAL hh;
  INEXACT REAL bvirt;
  REAL avirt, bround, around;
  int eindex, findex, hindex;
  REAL enow, fnow;

  enow = e[0];
  fnow = f[0];
  eindex = findex = 0;
  if ((fnow > enow) == (fnow > -enow)) {
    Q = enow;
    enow = e[++eindex];
  } else {
    Q = fnow;
    fnow = f[++findex];
  }
  hindex = 0;
  if ((eindex < elen) && (findex < flen)) {
    if ((fnow > enow) == (fnow > -enow)) {
      Fast_Two_Sum(enow, Q, Qnew, hh);
      enow = e[++eindex];
    } else {
      Fast_Two_Sum(fnow, Q, Qnew, hh);
      fnow = f[++findex];
    }
    Q = Qnew;
    if (hh != 0.0) {
      h[hindex++] = hh;
    }
    while ((eindex < elen) && (findex < flen)) {
      if ((fnow > enow) == (fnow > -enow)) {
        Two_Sum(Q, enow, Qnew, hh);
        enow = e[++eindex];
      } else {
        Two_Sum(Q, fnow, Qnew, hh);
        fnow = f[++findex];
      }
      Q = Qnew;
      if (hh != 0.0) {
        h[hindex++] = hh;
      }
    }
  }
  while (eindex < elen) {
    Two_Sum(Q, enow, Qnew, hh);
    enow = e[++eindex];
    Q = Qnew;
    if (hh != 0.0) {
      h[hindex++] = hh;
    }
  }
  while (findex < flen) {
    Two_Sum(Q, fnow, Qnew, hh);
    fnow = f[++findex];
    Q = Qnew;
    if (hh != 0.0) {
      h[hindex++] = hh;
    }
  }
  if ((Q != 0.0) || (hindex == 0)) {
    h[hindex++] = Q;
  }
  return hindex;
}

Here is the caller graph for this function:

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

Definition at line 10844 of file tlvisTrn_triangle.c.

References circumcentercount, counterclockcount, counterclockwise(), noexact, OPPOSITEAPEX, OPPOSITEDEST, OPPOSITEORG, and REAL.

Referenced by writevoronoi().

{
  REAL xdo, ydo, xao, yao, xad, yad;
  REAL dodist, aodist, addist;
  REAL denominator;
  REAL dx, dy;

  circumcentercount++;

  /* Compute the circumcenter of the triangle. */
  xdo = tdest[0] - torg[0];
  ydo = tdest[1] - torg[1];
  xao = tapex[0] - torg[0];
  yao = tapex[1] - torg[1];
  dodist = xdo * xdo + ydo * ydo;
  aodist = xao * xao + yao * yao;
  if (noexact) {
    denominator = 0.5 / (xdo * yao - xao * ydo);
  } else {
    /* Use the counterclockwise() routine to ensure a positive (and */
    /*   reasonably accurate) result, avoiding any possibility of   */
    /*   division by zero.                                          */
    denominator = 0.5 / counterclockwise(tdest, tapex, torg);
    /* Don't count the above as an orientation test. */
    counterclockcount--;
  }
  circumcenter[0] = torg[0] - (ydo * aodist - yao * dodist) * denominator;  
  circumcenter[1] = torg[1] + (xdo * aodist - xao * dodist) * denominator;  

  /* To interpolate point attributes for the new point inserted at  */
  /*   the circumcenter, define a coordinate system with a xi-axis, */
  /*   directed from the triangle's origin to its destination, and  */
  /*   an eta-axis, directed from its origin to its apex.           */
  /*   Calculate the xi and eta coordinates of the circumcenter.    */
  dx = circumcenter[0] - torg[0];
  dy = circumcenter[1] - torg[1];
  *xi = (dx * yao - xao * dy) * (2.0 * denominator);
  *eta = (xdo * dy - dx * ydo) * (2.0 * denominator);

  xad = tapex[0] - tdest[0];
  yad = tapex[1] - tdest[1];
  addist = xad * xad + yad * yad;
  if ((addist < dodist) && (addist < aodist)) {
    return OPPOSITEORG;
  } else if (dodist < aodist) {
    return OPPOSITEAPEX;
  } else {
    return OPPOSITEDEST;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

enum finddirectionresult finddirection ( struct triedge searchtri,
point  endpoint 
)

Definition at line 9174 of file tlvisTrn_triangle.c.

References apex, counterclockwise(), dest, dummytri, internalerror(), LEFTCOLLINEAR, onext, onextself, oprevself, org, ptr, REAL, RIGHTCOLLINEAR, triedge::tri, and WITHIN.

Referenced by scoutsegment(), and segmentintersection().

{
  struct triedge checktri;
  point startpoint;
  point leftpoint, rightpoint;
  REAL leftccw, rightccw;
  int leftflag, rightflag;
  triangle ptr;           /* Temporary variable used by onext() and oprev(). */

  org(*searchtri, startpoint);
  dest(*searchtri, rightpoint);
  apex(*searchtri, leftpoint);
  /* Is `endpoint' to the left? */
  leftccw = counterclockwise(endpoint, startpoint, leftpoint);
  leftflag = leftccw > 0.0;
  /* Is `endpoint' to the right? */
  rightccw = counterclockwise(startpoint, endpoint, rightpoint);
  rightflag = rightccw > 0.0;
  if (leftflag && rightflag) {
    /* `searchtri' faces directly away from `endpoint'.  We could go */
    /*   left or right.  Ask whether it's a triangle or a boundary   */
    /*   on the left.                                                */
    onext(*searchtri, checktri);
    if (checktri.tri == dummytri) {
      leftflag = 0;
    } else {
      rightflag = 0;
    }
  }
  while (leftflag) {
    /* Turn left until satisfied. */
    onextself(*searchtri);
    if (searchtri->tri == dummytri) {
      printf("Internal error in finddirection():  Unable to find a\n");
      printf("  triangle leading from (%.12g, %.12g) to", startpoint[0],
             startpoint[1]);
      printf("  (%.12g, %.12g).\n", endpoint[0], endpoint[1]);
      internalerror();
    }
    apex(*searchtri, leftpoint);
    rightccw = leftccw;
    leftccw = counterclockwise(endpoint, startpoint, leftpoint);
    leftflag = leftccw > 0.0;
  }
  while (rightflag) {
    /* Turn right until satisfied. */
    oprevself(*searchtri);
    if (searchtri->tri == dummytri) {
      printf("Internal error in finddirection():  Unable to find a\n");
      printf("  triangle leading from (%.12g, %.12g) to", startpoint[0],
             startpoint[1]);
      printf("  (%.12g, %.12g).\n", endpoint[0], endpoint[1]);
      internalerror();
    }
    dest(*searchtri, rightpoint);
    leftccw = rightccw;
    rightccw = counterclockwise(startpoint, endpoint, rightpoint);
    rightflag = rightccw > 0.0;
  }
  if (leftccw == 0.0) {
    return LEFTCOLLINEAR;
  } else if (rightccw == 0.0) {
    return RIGHTCOLLINEAR;
  } else {
    return WITHIN;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void flip ( struct triedge flipedge)

Definition at line 6008 of file tlvisTrn_triangle.c.

References apex, bond, checksegments, dest, dummysh, dummytri, lnext, lnextself, lprev, org, printtriangle(), ptr, setapex, setdest, setorg, edge::sh, sym, triedge::tri, tsbond, tsdissolve, tspivot, and verbose.

Referenced by constrainededge(), delaunayfixup(), and triangulatepolygon().

{
  struct triedge botleft, botright;
  struct triedge topleft, topright;
  struct triedge top;
  struct triedge botlcasing, botrcasing;
  struct triedge toplcasing, toprcasing;
  struct edge botlshelle, botrshelle;
  struct edge toplshelle, toprshelle;
  point leftpoint, rightpoint, botpoint;
  point farpoint;
  triangle ptr;                         /* Temporary variable used by sym(). */
  shelle sptr;                      /* Temporary variable used by tspivot(). */

  /* Identify the vertices of the quadrilateral. */
  org(*flipedge, rightpoint);
  dest(*flipedge, leftpoint);
  apex(*flipedge, botpoint);
  sym(*flipedge, top);
#ifdef SELF_CHECK
  if (top.tri == dummytri) {
    printf("Internal error in flip():  Attempt to flip on boundary.\n");
    lnextself(*flipedge);
    return;
  }
  if (checksegments) {
    tspivot(*flipedge, toplshelle);
    if (toplshelle.sh != dummysh) {
      printf("Internal error in flip():  Attempt to flip a segment.\n");
      lnextself(*flipedge);
      return;
    }
  }
#endif /* SELF_CHECK */
  apex(top, farpoint);

  /* Identify the casing of the quadrilateral. */
  lprev(top, topleft);
  sym(topleft, toplcasing);
  lnext(top, topright);
  sym(topright, toprcasing);
  lnext(*flipedge, botleft);
  sym(botleft, botlcasing);
  lprev(*flipedge, botright);
  sym(botright, botrcasing);
  /* Rotate the quadrilateral one-quarter turn counterclockwise. */
  bond(topleft, botlcasing);
  bond(botleft, botrcasing);
  bond(botright, toprcasing);
  bond(topright, toplcasing);

  if (checksegments) {
    /* Check for shell edges and rebond them to the quadrilateral. */
    tspivot(topleft, toplshelle);
    tspivot(botleft, botlshelle);
    tspivot(botright, botrshelle);
    tspivot(topright, toprshelle);
    if (toplshelle.sh == dummysh) {
      tsdissolve(topright);
    } else {
      tsbond(topright, toplshelle);
    }
    if (botlshelle.sh == dummysh) {
      tsdissolve(topleft);
    } else {
      tsbond(topleft, botlshelle);
    }
    if (botrshelle.sh == dummysh) {
      tsdissolve(botleft);
    } else {
      tsbond(botleft, botrshelle);
    }
    if (toprshelle.sh == dummysh) {
      tsdissolve(botright);
    } else {
      tsbond(botright, toprshelle);
    }
  }

  /* New point assignments for the rotated quadrilateral. */
  setorg(*flipedge, farpoint);
  setdest(*flipedge, botpoint);
  setapex(*flipedge, rightpoint);
  setorg(top, botpoint);
  setdest(top, farpoint);
  setapex(top, leftpoint);
  if (verbose > 2) {
    printf("  Edge flip results in left ");
    lnextself(topleft);
    printtriangle(&topleft);
    printf("  and right ");
    printtriangle(flipedge);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 9903 of file tlvisTrn_triangle.c.

References convex, exit(), firstnumber, getpoint(), inpoints, INPUTLINESIZE, insertsegment(), makepointmap(), markhull(), poly, quiet, strtol(), and verbose.

Referenced by triangulate().

{
#ifdef TRILIBRARY
  char polyfilename[6];
  int index;
#else /* not TRILIBRARY */
  char inputline[INPUTLINESIZE];
  char *stringptr;
#endif /* not TRILIBRARY */
  point endpoint1, endpoint2;
  int segments;
  int segmentmarkers;
  int end1, end2;
  int boundmarker;
  int i;

  if (poly) {
    if (!quiet) {
      printf("Inserting segments into Delaunay triangulation.\n");
    }
#ifdef TRILIBRARY
    strcpy(polyfilename, "input");
    segments = numberofsegments;
    segmentmarkers = segmentmarkerlist != (int *) NULL;
    index = 0;
#else /* not TRILIBRARY */
    /* Read the segments from a .poly file. */
    /* Read number of segments and number of boundary markers. */
    stringptr = freadline(inputline, polyfile, polyfilename);
    segments = (int) strtol (stringptr, &stringptr, 0);
    stringptr = findfield(stringptr);
    if (*stringptr == '\0') {
      segmentmarkers = 0;
    } else {
      segmentmarkers = (int) strtol (stringptr, &stringptr, 0);
    }
#endif /* not TRILIBRARY */
    /* If segments are to be inserted, compute a mapping */
    /*   from points to triangles.                       */
    if (segments > 0) {
      if (verbose) {
        printf("  Inserting PSLG segments.\n");
      }
      makepointmap();
    }

    boundmarker = 0;
    /* Read and insert the segments. */
    for (i = 1; i <= segments; i++) {
#ifdef TRILIBRARY
      end1 = segmentlist[index++];
      end2 = segmentlist[index++];
      if (segmentmarkers) {
        boundmarker = segmentmarkerlist[i - 1];
      }
#else /* not TRILIBRARY */
      stringptr = freadline(inputline, polyfile, inpolyfilename);
      stringptr = findfield(stringptr);
      if (*stringptr == '\0') {
        printf("Error:  Segment %d has no endpoints in %s.\n", i,
               polyfilename);
        exit(1);
      } else {
        end1 = (int) strtol (stringptr, &stringptr, 0);
      }
      stringptr = findfield(stringptr);
      if (*stringptr == '\0') {
        printf("Error:  Segment %d is missing its second endpoint in %s.\n", i,
               polyfilename);
        exit(1);
      } else {
        end2 = (int) strtol (stringptr, &stringptr, 0);
      }
      if (segmentmarkers) {
        stringptr = findfield(stringptr);
        if (*stringptr == '\0') {
          boundmarker = 0;
        } else {
          boundmarker = (int) strtol (stringptr, &stringptr, 0);
        }
      }
#endif /* not TRILIBRARY */
      if ((end1 < firstnumber) || (end1 >= firstnumber + inpoints)) {
        if (!quiet) {
          printf("Warning:  Invalid first endpoint of segment %d in %s.\n", i,
                 polyfilename);
        }
      } else if ((end2 < firstnumber) || (end2 >= firstnumber + inpoints)) {
        if (!quiet) {
          printf("Warning:  Invalid second endpoint of segment %d in %s.\n", i,
                 polyfilename);
        }
      } else {
        endpoint1 = getpoint(end1);
        endpoint2 = getpoint(end2);
        if ((endpoint1[0] == endpoint2[0]) && (endpoint1[1] == endpoint2[1])) {
          if (!quiet) {
            printf("Warning:  Endpoints of segment %d are coincident in %s.\n",
                   i, polyfilename);
          }
        } else {
          insertsegment(endpoint1, endpoint2, boundmarker);
        }
      }
    }
  } else {
    segments = 0;
  }
  if (convex || !poly) {
    /* Enclose the convex hull with shell edges. */
    if (verbose) {
      printf("  Enclosing convex hull with segments.\n");
    }
    markhull();
  }
  return segments;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void free ( )

Referenced by carveholes(), DeleteCoordList(), divconqdelaunay(), open_database_file(), pooldeinit(), triangledeinit(), and triangulate().

Here is the caller graph for this function:

point getpoint ( int  number)

Definition at line 3759 of file tlvisTrn_triangle.c.

References memorypool::alignbytes, memorypool::firstblock, firstnumber, memorypool::itemsperblock, memorypool::itemwords, points, and VOID.

Referenced by formskeleton().

{
  VOID **getblock;
  point foundpoint;
  unsigned long alignptr;
  int current;

  getblock = points.firstblock;
  current = firstnumber;
  /* Find the right block. */
  while (current + points.itemsperblock <= number) {
    getblock = (VOID **) *getblock;
    current += points.itemsperblock;
  }
  /* Now find the right point. */
  alignptr = (unsigned long) (getblock + 1);
  foundpoint = (point) (alignptr + (unsigned long) points.alignbytes
                        - (alignptr % (unsigned long) points.alignbytes));
  while (current < number) {
    foundpoint += points.itemwords;
    current++;
  }
  return foundpoint;
}

Here is the caller graph for this function:

void highorder ( )

Definition at line 11109 of file tlvisTrn_triangle.c.

References memorypool::deaditemstack, dest, dummysh, dummytri, highorderindex, mark, nextras, org, triedge::orient, points, poolalloc(), ptr, quiet, setpointmark, edge::sh, sym, traversalinit(), triedge::tri, triangles, triangletraverse(), tspivot, useshelles, verbose, and VOID.

Referenced by triangulate().

{
  struct triedge triangleloop, trisym;
  struct edge checkmark;
  point newpoint;
  point torg, tdest;
  int i;
  triangle ptr;                         /* Temporary variable used by sym(). */
  shelle sptr;                      /* Temporary variable used by tspivot(). */

  if (!quiet) {
    printf("Adding vertices for second-order triangles.\n");
  }
  /* The following line ensures that dead items in the pool of nodes    */
  /*   cannot be allocated for the extra nodes associated with high     */
  /*   order elements.  This ensures that the primary nodes (at the     */
  /*   corners of elements) will occur earlier in the output files, and */
  /*   have lower indices, than the extra nodes.                        */
  points.deaditemstack = (VOID *) NULL;

  traversalinit(&triangles);
  triangleloop.tri = triangletraverse();
  /* To loop over the set of edges, loop over all triangles, and look at   */
  /*   the three edges of each triangle.  If there isn't another triangle  */
  /*   adjacent to the edge, operate on the edge.  If there is another     */
  /*   adjacent triangle, operate on the edge only if the current triangle */
  /*   has a smaller pointer than its neighbor.  This way, each edge is    */
  /*   considered only once.                                               */
  while (triangleloop.tri != (triangle *) NULL) {
    for (triangleloop.orient = 0; triangleloop.orient < 3;
         triangleloop.orient++) {
      sym(triangleloop, trisym);
      if ((triangleloop.tri < trisym.tri) || (trisym.tri == dummytri)) {
        org(triangleloop, torg);
        dest(triangleloop, tdest);
        /* Create a new node in the middle of the edge.  Interpolate */
        /*   its attributes.                                         */
        newpoint = (point) poolalloc(&points);
        for (i = 0; i < 2 + nextras; i++) {
          newpoint[i] = 0.5 * (torg[i] + tdest[i]);
        }
        /* Set the new node's marker to zero or one, depending on */
        /*   whether it lies on a boundary.                       */
        setpointmark(newpoint, trisym.tri == dummytri);
        if (useshelles) {
          tspivot(triangleloop, checkmark);
          /* If this edge is a segment, transfer the marker to the new node. */
          if (checkmark.sh != dummysh) {
            setpointmark(newpoint, mark(checkmark));
          }
        }
        if (verbose > 1) {
          printf("  Creating (%.12g, %.12g).\n", newpoint[0], newpoint[1]);
        }
        /* Record the new node in the (one or two) adjacent elements. */
        triangleloop.tri[highorderindex + triangleloop.orient] =
                (triangle) newpoint;
        if (trisym.tri != dummytri) {
          trisym.tri[highorderindex + trisym.orient] = (triangle) newpoint;
        }
      }
    }
    triangleloop.tri = triangletraverse();
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 4970 of file tlvisTrn_triangle.c.

References Absolute, iccerrboundA, incircleadapt(), incirclecount, noexact, and REAL.

Referenced by delaunayfixup(), insertsite(), mergehulls(), and triangulatepolygon().

{
  REAL adx, bdx, cdx, ady, bdy, cdy;
  REAL bdxcdy, cdxbdy, cdxady, adxcdy, adxbdy, bdxady;
  REAL alift, blift, clift;
  REAL det;
  REAL permanent, errbound;

  incirclecount++;

  adx = pa[0] - pd[0];
  bdx = pb[0] - pd[0];
  cdx = pc[0] - pd[0];
  ady = pa[1] - pd[1];
  bdy = pb[1] - pd[1];
  cdy = pc[1] - pd[1];

  bdxcdy = bdx * cdy;
  cdxbdy = cdx * bdy;
  alift = adx * adx + ady * ady;

  cdxady = cdx * ady;
  adxcdy = adx * cdy;
  blift = bdx * bdx + bdy * bdy;

  adxbdy = adx * bdy;
  bdxady = bdx * ady;
  clift = cdx * cdx + cdy * cdy;

  det = alift * (bdxcdy - cdxbdy)
      + blift * (cdxady - adxcdy)
      + clift * (adxbdy - bdxady);

  if (noexact) {
    return det;
  }

  permanent = (Absolute(bdxcdy) + Absolute(cdxbdy)) * alift
            + (Absolute(cdxady) + Absolute(adxcdy)) * blift
            + (Absolute(adxbdy) + Absolute(bdxady)) * clift;
  errbound = iccerrboundA * permanent;
  if ((det > errbound) || (-det > errbound)) {
    return det;
  }

  return incircleadapt(pa, pb, pc, pd, permanent);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 4396 of file tlvisTrn_triangle.c.

References Absolute, bb, estimate(), fast_expansion_sum_zeroelim(), iccerrboundB, iccerrboundC, INEXACT, REAL, resulterrbound, scale_expansion_zeroelim(), Square, Two_Diff_Tail, Two_Product, Two_Two_Diff, Two_Two_Sum, and u.

Referenced by incircle().

{
  INEXACT REAL adx, bdx, cdx, ady, bdy, cdy;
  REAL det, errbound;

  INEXACT REAL bdxcdy1, cdxbdy1, cdxady1, adxcdy1, adxbdy1, bdxady1;
  REAL bdxcdy0, cdxbdy0, cdxady0, adxcdy0, adxbdy0, bdxady0;
  REAL bc[4], ca[4], ab[4];
  INEXACT REAL bc3, ca3, ab3;
  REAL axbc[8], axxbc[16], aybc[8], ayybc[16], adet[32];
  int axbclen, axxbclen, aybclen, ayybclen, alen;
  REAL bxca[8], bxxca[16], byca[8], byyca[16], bdet[32];
  int bxcalen, bxxcalen, bycalen, byycalen, blen;
  REAL cxab[8], cxxab[16], cyab[8], cyyab[16], cdet[32];
  int cxablen, cxxablen, cyablen, cyyablen, clen;
  REAL abdet[64];
  int ablen;
  REAL fin1[1152], fin2[1152];
  REAL *finnow, *finother, *finswap;
  int finlength;

  REAL adxtail, bdxtail, cdxtail, adytail, bdytail, cdytail;
  INEXACT REAL adxadx1, adyady1, bdxbdx1, bdybdy1, cdxcdx1, cdycdy1;
  REAL adxadx0, adyady0, bdxbdx0, bdybdy0, cdxcdx0, cdycdy0;
  REAL aa[4], bb[4], cc[4];
  INEXACT REAL aa3, bb3, cc3;
  INEXACT REAL ti1, tj1;
  REAL ti0, tj0;
  REAL u[4], v[4];
  INEXACT REAL u3, v3;
  REAL temp8[8], temp16a[16], temp16b[16], temp16c[16];
  REAL temp32a[32], temp32b[32], temp48[48], temp64[64];
  int temp8len, temp16alen, temp16blen, temp16clen;
  int temp32alen, temp32blen, temp48len, temp64len;
  REAL axtbb[8], axtcc[8], aytbb[8], aytcc[8];
  int axtbblen, axtcclen, aytbblen, aytcclen;
  REAL bxtaa[8], bxtcc[8], bytaa[8], bytcc[8];
  int bxtaalen, bxtcclen, bytaalen, bytcclen;
  REAL cxtaa[8], cxtbb[8], cytaa[8], cytbb[8];
  int cxtaalen, cxtbblen, cytaalen, cytbblen;
  REAL axtbc[8], aytbc[8], bxtca[8], bytca[8], cxtab[8], cytab[8];
  int axtbclen, aytbclen, bxtcalen, bytcalen, cxtablen, cytablen;
  REAL axtbct[16], aytbct[16], bxtcat[16], bytcat[16], cxtabt[16], cytabt[16];
  int axtbctlen, aytbctlen, bxtcatlen, bytcatlen, cxtabtlen, cytabtlen;
  REAL axtbctt[8], aytbctt[8], bxtcatt[8];
  REAL bytcatt[8], cxtabtt[8], cytabtt[8];
  int axtbcttlen, aytbcttlen, bxtcattlen, bytcattlen, cxtabttlen, cytabttlen;
  REAL abt[8], bct[8], cat[8];
  int abtlen, bctlen, catlen;
  REAL abtt[4], bctt[4], catt[4];
  int abttlen, bcttlen, cattlen;
  INEXACT REAL abtt3, bctt3, catt3;
  REAL negate;

  INEXACT REAL bvirt;
  REAL avirt, bround, around;
  INEXACT REAL c;
  INEXACT REAL abig;
  REAL ahi, alo, bhi, blo;
  REAL err1, err2, err3;
  INEXACT REAL _i, _j;
  REAL _0;

  adx = (REAL) (pa[0] - pd[0]);
  bdx = (REAL) (pb[0] - pd[0]);
  cdx = (REAL) (pc[0] - pd[0]);
  ady = (REAL) (pa[1] - pd[1]);
  bdy = (REAL) (pb[1] - pd[1]);
  cdy = (REAL) (pc[1] - pd[1]);

  Two_Product(bdx, cdy, bdxcdy1, bdxcdy0);
  Two_Product(cdx, bdy, cdxbdy1, cdxbdy0);
  Two_Two_Diff(bdxcdy1, bdxcdy0, cdxbdy1, cdxbdy0, bc3, bc[2], bc[1], bc[0]);
  bc[3] = bc3;
  axbclen = scale_expansion_zeroelim(4, bc, adx, axbc);
  axxbclen = scale_expansion_zeroelim(axbclen, axbc, adx, axxbc);
  aybclen = scale_expansion_zeroelim(4, bc, ady, aybc);
  ayybclen = scale_expansion_zeroelim(aybclen, aybc, ady, ayybc);
  alen = fast_expansion_sum_zeroelim(axxbclen, axxbc, ayybclen, ayybc, adet);

  Two_Product(cdx, ady, cdxady1, cdxady0);
  Two_Product(adx, cdy, adxcdy1, adxcdy0);
  Two_Two_Diff(cdxady1, cdxady0, adxcdy1, adxcdy0, ca3, ca[2], ca[1], ca[0]);
  ca[3] = ca3;
  bxcalen = scale_expansion_zeroelim(4, ca, bdx, bxca);
  bxxcalen = scale_expansion_zeroelim(bxcalen, bxca, bdx, bxxca);
  bycalen = scale_expansion_zeroelim(4, ca, bdy, byca);
  byycalen = scale_expansion_zeroelim(bycalen, byca, bdy, byyca);
  blen = fast_expansion_sum_zeroelim(bxxcalen, bxxca, byycalen, byyca, bdet);

  Two_Product(adx, bdy, adxbdy1, adxbdy0);
  Two_Product(bdx, ady, bdxady1, bdxady0);
  Two_Two_Diff(adxbdy1, adxbdy0, bdxady1, bdxady0, ab3, ab[2], ab[1], ab[0]);
  ab[3] = ab3;
  cxablen = scale_expansion_zeroelim(4, ab, cdx, cxab);
  cxxablen = scale_expansion_zeroelim(cxablen, cxab, cdx, cxxab);
  cyablen = scale_expansion_zeroelim(4, ab, cdy, cyab);
  cyyablen = scale_expansion_zeroelim(cyablen, cyab, cdy, cyyab);
  clen = fast_expansion_sum_zeroelim(cxxablen, cxxab, cyyablen, cyyab, cdet);

  ablen = fast_expansion_sum_zeroelim(alen, adet, blen, bdet, abdet);
  finlength = fast_expansion_sum_zeroelim(ablen, abdet, clen, cdet, fin1);

  det = estimate(finlength, fin1);
  errbound = iccerrboundB * permanent;
  if ((det >= errbound) || (-det >= errbound)) {
    return det;
  }

  Two_Diff_Tail(pa[0], pd[0], adx, adxtail);
  Two_Diff_Tail(pa[1], pd[1], ady, adytail);
  Two_Diff_Tail(pb[0], pd[0], bdx, bdxtail);
  Two_Diff_Tail(pb[1], pd[1], bdy, bdytail);
  Two_Diff_Tail(pc[0], pd[0], cdx, cdxtail);
  Two_Diff_Tail(pc[1], pd[1], cdy, cdytail);
  if ((adxtail == 0.0) && (bdxtail == 0.0) && (cdxtail == 0.0)
      && (adytail == 0.0) && (bdytail == 0.0) && (cdytail == 0.0)) {
    return det;
  }

  errbound = iccerrboundC * permanent + resulterrbound * Absolute(det);
  det += ((adx * adx + ady * ady) * ((bdx * cdytail + cdy * bdxtail)
                                     - (bdy * cdxtail + cdx * bdytail))
          + 2.0 * (adx * adxtail + ady * adytail) * (bdx * cdy - bdy * cdx))
       + ((bdx * bdx + bdy * bdy) * ((cdx * adytail + ady * cdxtail)
                                     - (cdy * adxtail + adx * cdytail))
          + 2.0 * (bdx * bdxtail + bdy * bdytail) * (cdx * ady - cdy * adx))
       + ((cdx * cdx + cdy * cdy) * ((adx * bdytail + bdy * adxtail)
                                     - (ady * bdxtail + bdx * adytail))
          + 2.0 * (cdx * cdxtail + cdy * cdytail) * (adx * bdy - ady * bdx));
  if ((det >= errbound) || (-det >= errbound)) {
    return det;
  }

  finnow = fin1;
  finother = fin2;

  if ((bdxtail != 0.0) || (bdytail != 0.0)
      || (cdxtail != 0.0) || (cdytail != 0.0)) {
    Square(adx, adxadx1, adxadx0);
    Square(ady, adyady1, adyady0);
    Two_Two_Sum(adxadx1, adxadx0, adyady1, adyady0, aa3, aa[2], aa[1], aa[0]);
    aa[3] = aa3;
  }
  if ((cdxtail != 0.0) || (cdytail != 0.0)
      || (adxtail != 0.0) || (adytail != 0.0)) {
    Square(bdx, bdxbdx1, bdxbdx0);
    Square(bdy, bdybdy1, bdybdy0);
    Two_Two_Sum(bdxbdx1, bdxbdx0, bdybdy1, bdybdy0, bb3, bb[2], bb[1], bb[0]);
    bb[3] = bb3;
  }
  if ((adxtail != 0.0) || (adytail != 0.0)
      || (bdxtail != 0.0) || (bdytail != 0.0)) {
    Square(cdx, cdxcdx1, cdxcdx0);
    Square(cdy, cdycdy1, cdycdy0);
    Two_Two_Sum(cdxcdx1, cdxcdx0, cdycdy1, cdycdy0, cc3, cc[2], cc[1], cc[0]);
    cc[3] = cc3;
  }

  if (adxtail != 0.0) {
    axtbclen = scale_expansion_zeroelim(4, bc, adxtail, axtbc);
    temp16alen = scale_expansion_zeroelim(axtbclen, axtbc, 2.0 * adx,
                                          temp16a);

    axtcclen = scale_expansion_zeroelim(4, cc, adxtail, axtcc);
    temp16blen = scale_expansion_zeroelim(axtcclen, axtcc, bdy, temp16b);

    axtbblen = scale_expansion_zeroelim(4, bb, adxtail, axtbb);
    temp16clen = scale_expansion_zeroelim(axtbblen, axtbb, -cdy, temp16c);

    temp32alen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                            temp16blen, temp16b, temp32a);
    temp48len = fast_expansion_sum_zeroelim(temp16clen, temp16c,
                                            temp32alen, temp32a, temp48);
    finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
                                            temp48, finother);
    finswap = finnow; finnow = finother; finother = finswap;
  }
  if (adytail != 0.0) {
    aytbclen = scale_expansion_zeroelim(4, bc, adytail, aytbc);
    temp16alen = scale_expansion_zeroelim(aytbclen, aytbc, 2.0 * ady,
                                          temp16a);

    aytbblen = scale_expansion_zeroelim(4, bb, adytail, aytbb);
    temp16blen = scale_expansion_zeroelim(aytbblen, aytbb, cdx, temp16b);

    aytcclen = scale_expansion_zeroelim(4, cc, adytail, aytcc);
    temp16clen = scale_expansion_zeroelim(aytcclen, aytcc, -bdx, temp16c);

    temp32alen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                            temp16blen, temp16b, temp32a);
    temp48len = fast_expansion_sum_zeroelim(temp16clen, temp16c,
                                            temp32alen, temp32a, temp48);
    finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
                                            temp48, finother);
    finswap = finnow; finnow = finother; finother = finswap;
  }
  if (bdxtail != 0.0) {
    bxtcalen = scale_expansion_zeroelim(4, ca, bdxtail, bxtca);
    temp16alen = scale_expansion_zeroelim(bxtcalen, bxtca, 2.0 * bdx,
                                          temp16a);

    bxtaalen = scale_expansion_zeroelim(4, aa, bdxtail, bxtaa);
    temp16blen = scale_expansion_zeroelim(bxtaalen, bxtaa, cdy, temp16b);

    bxtcclen = scale_expansion_zeroelim(4, cc, bdxtail, bxtcc);
    temp16clen = scale_expansion_zeroelim(bxtcclen, bxtcc, -ady, temp16c);

    temp32alen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                            temp16blen, temp16b, temp32a);
    temp48len = fast_expansion_sum_zeroelim(temp16clen, temp16c,
                                            temp32alen, temp32a, temp48);
    finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
                                            temp48, finother);
    finswap = finnow; finnow = finother; finother = finswap;
  }
  if (bdytail != 0.0) {
    bytcalen = scale_expansion_zeroelim(4, ca, bdytail, bytca);
    temp16alen = scale_expansion_zeroelim(bytcalen, bytca, 2.0 * bdy,
                                          temp16a);

    bytcclen = scale_expansion_zeroelim(4, cc, bdytail, bytcc);
    temp16blen = scale_expansion_zeroelim(bytcclen, bytcc, adx, temp16b);

    bytaalen = scale_expansion_zeroelim(4, aa, bdytail, bytaa);
    temp16clen = scale_expansion_zeroelim(bytaalen, bytaa, -cdx, temp16c);

    temp32alen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                            temp16blen, temp16b, temp32a);
    temp48len = fast_expansion_sum_zeroelim(temp16clen, temp16c,
                                            temp32alen, temp32a, temp48);
    finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
                                            temp48, finother);
    finswap = finnow; finnow = finother; finother = finswap;
  }
  if (cdxtail != 0.0) {
    cxtablen = scale_expansion_zeroelim(4, ab, cdxtail, cxtab);
    temp16alen = scale_expansion_zeroelim(cxtablen, cxtab, 2.0 * cdx,
                                          temp16a);

    cxtbblen = scale_expansion_zeroelim(4, bb, cdxtail, cxtbb);
    temp16blen = scale_expansion_zeroelim(cxtbblen, cxtbb, ady, temp16b);

    cxtaalen = scale_expansion_zeroelim(4, aa, cdxtail, cxtaa);
    temp16clen = scale_expansion_zeroelim(cxtaalen, cxtaa, -bdy, temp16c);

    temp32alen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                            temp16blen, temp16b, temp32a);
    temp48len = fast_expansion_sum_zeroelim(temp16clen, temp16c,
                                            temp32alen, temp32a, temp48);
    finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
                                            temp48, finother);
    finswap = finnow; finnow = finother; finother = finswap;
  }
  if (cdytail != 0.0) {
    cytablen = scale_expansion_zeroelim(4, ab, cdytail, cytab);
    temp16alen = scale_expansion_zeroelim(cytablen, cytab, 2.0 * cdy,
                                          temp16a);

    cytaalen = scale_expansion_zeroelim(4, aa, cdytail, cytaa);
    temp16blen = scale_expansion_zeroelim(cytaalen, cytaa, bdx, temp16b);

    cytbblen = scale_expansion_zeroelim(4, bb, cdytail, cytbb);
    temp16clen = scale_expansion_zeroelim(cytbblen, cytbb, -adx, temp16c);

    temp32alen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                            temp16blen, temp16b, temp32a);
    temp48len = fast_expansion_sum_zeroelim(temp16clen, temp16c,
                                            temp32alen, temp32a, temp48);
    finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
                                            temp48, finother);
    finswap = finnow; finnow = finother; finother = finswap;
  }

  if ((adxtail != 0.0) || (adytail != 0.0)) {
    if ((bdxtail != 0.0) || (bdytail != 0.0)
        || (cdxtail != 0.0) || (cdytail != 0.0)) {
      Two_Product(bdxtail, cdy, ti1, ti0);
      Two_Product(bdx, cdytail, tj1, tj0);
      Two_Two_Sum(ti1, ti0, tj1, tj0, u3, u[2], u[1], u[0]);
      u[3] = u3;
      negate = -bdy;
      Two_Product(cdxtail, negate, ti1, ti0);
      negate = -bdytail;
      Two_Product(cdx, negate, tj1, tj0);
      Two_Two_Sum(ti1, ti0, tj1, tj0, v3, v[2], v[1], v[0]);
      v[3] = v3;
      bctlen = fast_expansion_sum_zeroelim(4, u, 4, v, bct);

      Two_Product(bdxtail, cdytail, ti1, ti0);
      Two_Product(cdxtail, bdytail, tj1, tj0);
      Two_Two_Diff(ti1, ti0, tj1, tj0, bctt3, bctt[2], bctt[1], bctt[0]);
      bctt[3] = bctt3;
      bcttlen = 4;
    } else {
      bct[0] = 0.0;
      bctlen = 1;
      bctt[0] = 0.0;
      bcttlen = 1;
    }

    if (adxtail != 0.0) {
      temp16alen = scale_expansion_zeroelim(axtbclen, axtbc, adxtail, temp16a);
      axtbctlen = scale_expansion_zeroelim(bctlen, bct, adxtail, axtbct);
      temp32alen = scale_expansion_zeroelim(axtbctlen, axtbct, 2.0 * adx,
                                            temp32a);
      temp48len = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                              temp32alen, temp32a, temp48);
      finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
                                              temp48, finother);
      finswap = finnow; finnow = finother; finother = finswap;
      if (bdytail != 0.0) {
        temp8len = scale_expansion_zeroelim(4, cc, adxtail, temp8);
        temp16alen = scale_expansion_zeroelim(temp8len, temp8, bdytail,
                                              temp16a);
        finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp16alen,
                                                temp16a, finother);
        finswap = finnow; finnow = finother; finother = finswap;
      }
      if (cdytail != 0.0) {
        temp8len = scale_expansion_zeroelim(4, bb, -adxtail, temp8);
        temp16alen = scale_expansion_zeroelim(temp8len, temp8, cdytail,
                                              temp16a);
        finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp16alen,
                                                temp16a, finother);
        finswap = finnow; finnow = finother; finother = finswap;
      }

      temp32alen = scale_expansion_zeroelim(axtbctlen, axtbct, adxtail,
                                            temp32a);
      axtbcttlen = scale_expansion_zeroelim(bcttlen, bctt, adxtail, axtbctt);
      temp16alen = scale_expansion_zeroelim(axtbcttlen, axtbctt, 2.0 * adx,
                                            temp16a);
      temp16blen = scale_expansion_zeroelim(axtbcttlen, axtbctt, adxtail,
                                            temp16b);
      temp32blen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                              temp16blen, temp16b, temp32b);
      temp64len = fast_expansion_sum_zeroelim(temp32alen, temp32a,
                                              temp32blen, temp32b, temp64);
      finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp64len,
                                              temp64, finother);
      finswap = finnow; finnow = finother; finother = finswap;
    }
    if (adytail != 0.0) {
      temp16alen = scale_expansion_zeroelim(aytbclen, aytbc, adytail, temp16a);
      aytbctlen = scale_expansion_zeroelim(bctlen, bct, adytail, aytbct);
      temp32alen = scale_expansion_zeroelim(aytbctlen, aytbct, 2.0 * ady,
                                            temp32a);
      temp48len = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                              temp32alen, temp32a, temp48);
      finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
                                              temp48, finother);
      finswap = finnow; finnow = finother; finother = finswap;


      temp32alen = scale_expansion_zeroelim(aytbctlen, aytbct, adytail,
                                            temp32a);
      aytbcttlen = scale_expansion_zeroelim(bcttlen, bctt, adytail, aytbctt);
      temp16alen = scale_expansion_zeroelim(aytbcttlen, aytbctt, 2.0 * ady,
                                            temp16a);
      temp16blen = scale_expansion_zeroelim(aytbcttlen, aytbctt, adytail,
                                            temp16b);
      temp32blen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                              temp16blen, temp16b, temp32b);
      temp64len = fast_expansion_sum_zeroelim(temp32alen, temp32a,
                                              temp32blen, temp32b, temp64);
      finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp64len,
                                              temp64, finother);
      finswap = finnow; finnow = finother; finother = finswap;
    }
  }
  if ((bdxtail != 0.0) || (bdytail != 0.0)) {
    if ((cdxtail != 0.0) || (cdytail != 0.0)
        || (adxtail != 0.0) || (adytail != 0.0)) {
      Two_Product(cdxtail, ady, ti1, ti0);
      Two_Product(cdx, adytail, tj1, tj0);
      Two_Two_Sum(ti1, ti0, tj1, tj0, u3, u[2], u[1], u[0]);
      u[3] = u3;
      negate = -cdy;
      Two_Product(adxtail, negate, ti1, ti0);
      negate = -cdytail;
      Two_Product(adx, negate, tj1, tj0);
      Two_Two_Sum(ti1, ti0, tj1, tj0, v3, v[2], v[1], v[0]);
      v[3] = v3;
      catlen = fast_expansion_sum_zeroelim(4, u, 4, v, cat);

      Two_Product(cdxtail, adytail, ti1, ti0);
      Two_Product(adxtail, cdytail, tj1, tj0);
      Two_Two_Diff(ti1, ti0, tj1, tj0, catt3, catt[2], catt[1], catt[0]);
      catt[3] = catt3;
      cattlen = 4;
    } else {
      cat[0] = 0.0;
      catlen = 1;
      catt[0] = 0.0;
      cattlen = 1;
    }

    if (bdxtail != 0.0) {
      temp16alen = scale_expansion_zeroelim(bxtcalen, bxtca, bdxtail, temp16a);
      bxtcatlen = scale_expansion_zeroelim(catlen, cat, bdxtail, bxtcat);
      temp32alen = scale_expansion_zeroelim(bxtcatlen, bxtcat, 2.0 * bdx,
                                            temp32a);
      temp48len = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                              temp32alen, temp32a, temp48);
      finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
                                              temp48, finother);
      finswap = finnow; finnow = finother; finother = finswap;
      if (cdytail != 0.0) {
        temp8len = scale_expansion_zeroelim(4, aa, bdxtail, temp8);
        temp16alen = scale_expansion_zeroelim(temp8len, temp8, cdytail,
                                              temp16a);
        finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp16alen,
                                                temp16a, finother);
        finswap = finnow; finnow = finother; finother = finswap;
      }
      if (adytail != 0.0) {
        temp8len = scale_expansion_zeroelim(4, cc, -bdxtail, temp8);
        temp16alen = scale_expansion_zeroelim(temp8len, temp8, adytail,
                                              temp16a);
        finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp16alen,
                                                temp16a, finother);
        finswap = finnow; finnow = finother; finother = finswap;
      }

      temp32alen = scale_expansion_zeroelim(bxtcatlen, bxtcat, bdxtail,
                                            temp32a);
      bxtcattlen = scale_expansion_zeroelim(cattlen, catt, bdxtail, bxtcatt);
      temp16alen = scale_expansion_zeroelim(bxtcattlen, bxtcatt, 2.0 * bdx,
                                            temp16a);
      temp16blen = scale_expansion_zeroelim(bxtcattlen, bxtcatt, bdxtail,
                                            temp16b);
      temp32blen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                              temp16blen, temp16b, temp32b);
      temp64len = fast_expansion_sum_zeroelim(temp32alen, temp32a,
                                              temp32blen, temp32b, temp64);
      finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp64len,
                                              temp64, finother);
      finswap = finnow; finnow = finother; finother = finswap;
    }
    if (bdytail != 0.0) {
      temp16alen = scale_expansion_zeroelim(bytcalen, bytca, bdytail, temp16a);
      bytcatlen = scale_expansion_zeroelim(catlen, cat, bdytail, bytcat);
      temp32alen = scale_expansion_zeroelim(bytcatlen, bytcat, 2.0 * bdy,
                                            temp32a);
      temp48len = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                              temp32alen, temp32a, temp48);
      finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
                                              temp48, finother);
      finswap = finnow; finnow = finother; finother = finswap;


      temp32alen = scale_expansion_zeroelim(bytcatlen, bytcat, bdytail,
                                            temp32a);
      bytcattlen = scale_expansion_zeroelim(cattlen, catt, bdytail, bytcatt);
      temp16alen = scale_expansion_zeroelim(bytcattlen, bytcatt, 2.0 * bdy,
                                            temp16a);
      temp16blen = scale_expansion_zeroelim(bytcattlen, bytcatt, bdytail,
                                            temp16b);
      temp32blen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                              temp16blen, temp16b, temp32b);
      temp64len = fast_expansion_sum_zeroelim(temp32alen, temp32a,
                                              temp32blen, temp32b, temp64);
      finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp64len,
                                              temp64, finother);
      finswap = finnow; finnow = finother; finother = finswap;
    }
  }
  if ((cdxtail != 0.0) || (cdytail != 0.0)) {
    if ((adxtail != 0.0) || (adytail != 0.0)
        || (bdxtail != 0.0) || (bdytail != 0.0)) {
      Two_Product(adxtail, bdy, ti1, ti0);
      Two_Product(adx, bdytail, tj1, tj0);
      Two_Two_Sum(ti1, ti0, tj1, tj0, u3, u[2], u[1], u[0]);
      u[3] = u3;
      negate = -ady;
      Two_Product(bdxtail, negate, ti1, ti0);
      negate = -adytail;
      Two_Product(bdx, negate, tj1, tj0);
      Two_Two_Sum(ti1, ti0, tj1, tj0, v3, v[2], v[1], v[0]);
      v[3] = v3;
      abtlen = fast_expansion_sum_zeroelim(4, u, 4, v, abt);

      Two_Product(adxtail, bdytail, ti1, ti0);
      Two_Product(bdxtail, adytail, tj1, tj0);
      Two_Two_Diff(ti1, ti0, tj1, tj0, abtt3, abtt[2], abtt[1], abtt[0]);
      abtt[3] = abtt3;
      abttlen = 4;
    } else {
      abt[0] = 0.0;
      abtlen = 1;
      abtt[0] = 0.0;
      abttlen = 1;
    }

    if (cdxtail != 0.0) {
      temp16alen = scale_expansion_zeroelim(cxtablen, cxtab, cdxtail, temp16a);
      cxtabtlen = scale_expansion_zeroelim(abtlen, abt, cdxtail, cxtabt);
      temp32alen = scale_expansion_zeroelim(cxtabtlen, cxtabt, 2.0 * cdx,
                                            temp32a);
      temp48len = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                              temp32alen, temp32a, temp48);
      finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
                                              temp48, finother);
      finswap = finnow; finnow = finother; finother = finswap;
      if (adytail != 0.0) {
        temp8len = scale_expansion_zeroelim(4, bb, cdxtail, temp8);
        temp16alen = scale_expansion_zeroelim(temp8len, temp8, adytail,
                                              temp16a);
        finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp16alen,
                                                temp16a, finother);
        finswap = finnow; finnow = finother; finother = finswap;
      }
      if (bdytail != 0.0) {
        temp8len = scale_expansion_zeroelim(4, aa, -cdxtail, temp8);
        temp16alen = scale_expansion_zeroelim(temp8len, temp8, bdytail,
                                              temp16a);
        finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp16alen,
                                                temp16a, finother);
        finswap = finnow; finnow = finother; finother = finswap;
      }

      temp32alen = scale_expansion_zeroelim(cxtabtlen, cxtabt, cdxtail,
                                            temp32a);
      cxtabttlen = scale_expansion_zeroelim(abttlen, abtt, cdxtail, cxtabtt);
      temp16alen = scale_expansion_zeroelim(cxtabttlen, cxtabtt, 2.0 * cdx,
                                            temp16a);
      temp16blen = scale_expansion_zeroelim(cxtabttlen, cxtabtt, cdxtail,
                                            temp16b);
      temp32blen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                              temp16blen, temp16b, temp32b);
      temp64len = fast_expansion_sum_zeroelim(temp32alen, temp32a,
                                              temp32blen, temp32b, temp64);
      finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp64len,
                                              temp64, finother);
      finswap = finnow; finnow = finother; finother = finswap;
    }
    if (cdytail != 0.0) {
      temp16alen = scale_expansion_zeroelim(cytablen, cytab, cdytail, temp16a);
      cytabtlen = scale_expansion_zeroelim(abtlen, abt, cdytail, cytabt);
      temp32alen = scale_expansion_zeroelim(cytabtlen, cytabt, 2.0 * cdy,
                                            temp32a);
      temp48len = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                              temp32alen, temp32a, temp48);
      finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
                                              temp48, finother);
      finswap = finnow; finnow = finother; finother = finswap;


      temp32alen = scale_expansion_zeroelim(cytabtlen, cytabt, cdytail,
                                            temp32a);
      cytabttlen = scale_expansion_zeroelim(abttlen, abtt, cdytail, cytabtt);
      temp16alen = scale_expansion_zeroelim(cytabttlen, cytabtt, 2.0 * cdy,
                                            temp16a);
      temp16blen = scale_expansion_zeroelim(cytabttlen, cytabtt, cdytail,
                                            temp16b);
      temp32blen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
                                              temp16blen, temp16b, temp32b);
      temp64len = fast_expansion_sum_zeroelim(temp32alen, temp32a,
                                              temp32blen, temp32b, temp64);
      finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp64len,
                                              temp64, finother);
      finswap = finnow; finnow = finother; finother = finswap;
    }
  }

  return finnow[finlength - 1];
}

Here is the call graph for this function:

Here is the caller graph for this function:

void infecthull ( )

Definition at line 10049 of file tlvisTrn_triangle.c.

References dest, dummysh, dummytri, infect, infected, lnextself, mark, oprev, org, triedge::orient, pointmark, poolalloc(), ptr, setmark, setpointmark, edge::sh, symself, triedge::tri, triedgecopy, triedgeequal, tspivot, verbose, and viri.

Referenced by carveholes().

{
  struct triedge hulltri;
  struct triedge nexttri;
  struct triedge starttri;
  struct edge hulledge;
  triangle **deadtri;
  point horg, hdest;
  triangle ptr;                         /* Temporary variable used by sym(). */
  shelle sptr;                      /* Temporary variable used by tspivot(). */

  if (verbose) {
    printf("  Marking concavities (external triangles) for elimination.\n");
  }
  /* Find a triangle handle on the hull. */
  hulltri.tri = dummytri;
  hulltri.orient = 0;
  symself(hulltri);
  /* Remember where we started so we know when to stop. */
  triedgecopy(hulltri, starttri);
  /* Go once counterclockwise around the convex hull. */
  do {
    /* Ignore triangles that are already infected. */
    if (!infected(hulltri)) {
      /* Is the triangle protected by a shell edge? */
      tspivot(hulltri, hulledge);
      if (hulledge.sh == dummysh) {
        /* The triangle is not protected; infect it. */
        infect(hulltri);
        deadtri = (triangle **) poolalloc(&viri);
        *deadtri = hulltri.tri;
      } else {
        /* The triangle is protected; set boundary markers if appropriate. */
        if (mark(hulledge) == 0) {
          setmark(hulledge, 1);
          org(hulltri, horg);
          dest(hulltri, hdest);
          if (pointmark(horg) == 0) {
            setpointmark(horg, 1);
          }
          if (pointmark(hdest) == 0) {
            setpointmark(hdest, 1);
          }
        }
      }
    }
    /* To find the next hull edge, go clockwise around the next vertex. */
    lnextself(hulltri);
    oprev(hulltri, nexttri);
    while (nexttri.tri != dummytri) {
      triedgecopy(nexttri, hulltri);
      oprev(hulltri, nexttri);
    }
  } while (!triedgeequal(hulltri, starttri));
}

Here is the call graph for this function:

Here is the caller graph for this function:

void initializepointpool ( )

Definition at line 3518 of file tlvisTrn_triangle.c.

References FLOATINGPOINT, mesh_dim, nextras, point2triindex, POINTER, pointmarkindex, POINTPERBLOCK, points, poly, poolinit(), and REAL.

Referenced by transfernodes().

{
  int pointsize;

  /* The index within each point at which the boundary marker is found.  */
  /*   Ensure the point marker is aligned to a sizeof(int)-byte address. */
  pointmarkindex = ((mesh_dim + nextras) * sizeof(REAL) + sizeof(int) - 1)
                 / sizeof(int);
  pointsize = (pointmarkindex + 1) * sizeof(int);
  if (poly) {
    /* The index within each point at which a triangle pointer is found.   */
    /*   Ensure the pointer is aligned to a sizeof(triangle)-byte address. */
    point2triindex = (pointsize + sizeof(triangle) - 1) / sizeof(triangle);
    pointsize = (point2triindex + 1) * sizeof(triangle);
  }
  /* Initialize the pool of points. */
  poolinit(&points, pointsize, POINTPERBLOCK,
           (sizeof(REAL) >= sizeof(triangle)) ? FLOATINGPOINT : POINTER, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void initializetrisegpools ( )

Definition at line 3549 of file tlvisTrn_triangle.c.

References areaboundindex, dummyinit(), eextras, elemattribindex, highorderindex, memorypool::itemwords, neighbors, order, POINTER, poolinit(), REAL, regionattrib, SHELLEPERBLOCK, shelles, triangles, TRIPERBLOCK, useshelles, vararea, and voronoi.

Referenced by delaunay().

{
  int trisize;

  /* The index within each triangle at which the extra nodes (above three)  */
  /*   associated with high order elements are found.  There are three      */
  /*   pointers to other triangles, three pointers to corners, and possibly */
  /*   three pointers to shell edges before the extra nodes.                */
  highorderindex = 6 + (useshelles * 3);
  /* The number of bytes occupied by a triangle. */
  trisize = ((order + 1) * (order + 2) / 2 + (highorderindex - 3)) *
            sizeof(triangle);
  /* The index within each triangle at which its attributes are found, */
  /*   where the index is measured in REALs.                           */
  elemattribindex = (trisize + sizeof(REAL) - 1) / sizeof(REAL);
  /* The index within each triangle at which the maximum area constraint  */
  /*   is found, where the index is measured in REALs.  Note that if the  */
  /*   `regionattrib' flag is set, an additional attribute will be added. */
  areaboundindex = elemattribindex + eextras + regionattrib;
  /* If triangle attributes or an area bound are needed, increase the number */
  /*   of bytes occupied by a triangle.                                      */
  if (vararea) {
    trisize = (areaboundindex + 1) * sizeof(REAL);
  } else if (eextras + regionattrib > 0) {
    trisize = areaboundindex * sizeof(REAL);
  }
  /* If a Voronoi diagram or triangle neighbor graph is requested, make    */
  /*   sure there's room to store an integer index in each triangle.  This */
  /*   integer index can occupy the same space as the shell edges or       */
  /*   attributes or area constraint or extra nodes.                       */
  if ((voronoi || neighbors) &&
      (trisize < 6 * sizeof(triangle) + sizeof(int))) {
    trisize = 6 * sizeof(triangle) + sizeof(int);
  }
  /* Having determined the memory size of a triangle, initialize the pool. */
  poolinit(&triangles, trisize, TRIPERBLOCK, POINTER, 4);

  if (useshelles) {
    /* Initialize the pool of shell edges. */
    poolinit(&shelles, 6 * sizeof(triangle) + sizeof(int), SHELLEPERBLOCK,
             POINTER, 4);

    /* Initialize the "outer space" triangle and omnipresent shell edge. */
    dummyinit(triangles.itemwords, shelles.itemwords);
  } else {
    /* Initialize the "outer space" triangle. */
    dummyinit(triangles.itemwords, 0);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 9760 of file tlvisTrn_triangle.c.

References constrainededge(), decode, dummytri, internalerror(), locate(), ONVERTEX, org, triedge::orient, point2tri, ptr, recenttri, scoutsegment(), splitseg, symself, triedge::tri, triedgecopy, and verbose.

Referenced by formskeleton().

{
  struct triedge searchtri1, searchtri2;
  triangle encodedtri;
  point checkpoint;
  triangle ptr;                         /* Temporary variable used by sym(). */

  if (verbose > 1) {
    printf("  Connecting (%.12g, %.12g) to (%.12g, %.12g).\n",
           endpoint1[0], endpoint1[1], endpoint2[0], endpoint2[1]);
  }

  /* Find a triangle whose origin is the segment's first endpoint. */
  checkpoint = (point) NULL;
  encodedtri = point2tri(endpoint1);
  if (encodedtri != (triangle) NULL) {
    decode(encodedtri, searchtri1);
    org(searchtri1, checkpoint);
  }
  if (checkpoint != endpoint1) {
    /* Find a boundary triangle to search from. */
    searchtri1.tri = dummytri;
    searchtri1.orient = 0;
    symself(searchtri1);
    /* Search for the segment's first endpoint by point location. */
    if (locate(endpoint1, &searchtri1) != ONVERTEX) {
      printf(
        "Internal error in insertsegment():  Unable to locate PSLG point\n");
      printf("  (%.12g, %.12g) in triangulation.\n",
             endpoint1[0], endpoint1[1]);
      internalerror();
    }
  }
  /* Remember this triangle to improve subsequent point location. */
  triedgecopy(searchtri1, recenttri);
  /* Scout the beginnings of a path from the first endpoint */
  /*   toward the second.                                   */
  if (scoutsegment(&searchtri1, endpoint2, newmark)) {
    /* The segment was easily inserted. */
    return;
  }
  /* The first endpoint may have changed if a collision with an intervening */
  /*   vertex on the segment occurred.                                      */
  org(searchtri1, endpoint1);

  /* Find a triangle whose origin is the segment's second endpoint. */
  checkpoint = (point) NULL;
  encodedtri = point2tri(endpoint2);
  if (encodedtri != (triangle) NULL) {
    decode(encodedtri, searchtri2);
    org(searchtri2, checkpoint);
  }
  if (checkpoint != endpoint2) {
    /* Find a boundary triangle to search from. */
    searchtri2.tri = dummytri;
    searchtri2.orient = 0;
    symself(searchtri2);
    /* Search for the segment's second endpoint by point location. */
    if (locate(endpoint2, &searchtri2) != ONVERTEX) {
      printf(
        "Internal error in insertsegment():  Unable to locate PSLG point\n");
      printf("  (%.12g, %.12g) in triangulation.\n",
             endpoint2[0], endpoint2[1]);
      internalerror();
    }
  }
  /* Remember this triangle to improve subsequent point location. */
  triedgecopy(searchtri2, recenttri);
  /* Scout the beginnings of a path from the second endpoint */
  /*   toward the first.                                     */
  if (scoutsegment(&searchtri2, endpoint1, newmark)) {
    /* The segment was easily inserted. */
    return;
  }
  /* The second endpoint may have changed if a collision with an intervening */
  /*   vertex on the segment occurred.                                       */
  org(searchtri2, endpoint2);

#ifndef REDUCED
#ifndef CDT_ONLY
  if (splitseg) {
    /* Insert vertices to force the segment into the triangulation. */
    conformingedge(endpoint1, endpoint2, newmark);
  } else {
#endif /* not CDT_ONLY */
#endif /* not REDUCED */
    /* Insert the segment directly into the triangulation. */
    constrainededge(&searchtri1, endpoint2, newmark);
#ifndef REDUCED
#ifndef CDT_ONLY
  }
#endif /* not CDT_ONLY */
#endif /* not REDUCED */
}

Here is the call graph for this function:

Here is the caller graph for this function:

void insertshelle ( struct triedge tri,
int  shellemark 
)

Definition at line 5909 of file tlvisTrn_triangle.c.

References dest, dummysh, makeshelle(), mark, org, pointmark, printshelle(), ptr, setmark, setpointmark, setsdest, setsorg, edge::sh, ssymself, sym, tsbond, tspivot, and verbose.

Referenced by constrainededge(), insertsite(), markhull(), and scoutsegment().

{
  struct triedge oppotri;
  struct edge newshelle;
  point triorg, tridest;
  triangle ptr;                         /* Temporary variable used by sym(). */
  shelle sptr;                      /* Temporary variable used by tspivot(). */

  /* Mark points if possible. */
  org(*tri, triorg);
  dest(*tri, tridest);
  if (pointmark(triorg) == 0) {
    setpointmark(triorg, shellemark);
  }
  if (pointmark(tridest) == 0) {
    setpointmark(tridest, shellemark);
  }
  /* Check if there's already a shell edge here. */
  tspivot(*tri, newshelle);
  if (newshelle.sh == dummysh) {
    /* Make new shell edge and initialize its vertices. */
    makeshelle(&newshelle);
    setsorg(newshelle, tridest);
    setsdest(newshelle, triorg);
    /* Bond new shell edge to the two triangles it is sandwiched between. */
    /*   Note that the facing triangle `oppotri' might be equal to        */
    /*   `dummytri' (outer space), but the new shell edge is bonded to it */
    /*   all the same.                                                    */
    tsbond(*tri, newshelle);
    sym(*tri, oppotri);
    ssymself(newshelle);
    tsbond(oppotri, newshelle);
    setmark(newshelle, shellemark);
    if (verbose > 2) {
      printf("  Inserting new ");
      printshelle(&newshelle);
    }
  } else {
    if (mark(newshelle) == 0) {
      setmark(newshelle, shellemark);
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 6151 of file tlvisTrn_triangle.c.

References apex, area, areabound, badsegments, bond, checksegments, counterclockwise(), dest, dummysh, dummytri, DUPLICATEPOINT, eextras, elemattribute, ENCROACHINGPOINT, hullsize, incircle(), infpoint1, infpoint2, infpoint3, insertshelle(), lnext, lnextself, locate(), lprev, lprevself, maketriangle(), mark, nobisect, ONEDGE, ONVERTEX, org, triedge::orient, OUTSIDE, poolalloc(), preciselocate(), printtriangle(), ptr, REAL, recenttri, sbond, setapex, setareabound, setdest, setelemattribute, setorg, setsdest, edge::sh, shellecopy, spivot, ssymself, SUCCESSFULPOINT, sym, symself, triedge::tri, triedgecopy, tsbond, tsdissolve, tspivot, vararea, verbose, and VIOLATINGPOINT.

Referenced by segmentintersection().

{
  struct triedge horiz;
  struct triedge top;
  struct triedge botleft, botright;
  struct triedge topleft, topright;
  struct triedge newbotleft, newbotright;
  struct triedge newtopright;
  struct triedge botlcasing, botrcasing;
  struct triedge toplcasing, toprcasing;
  struct triedge testtri;
  struct edge botlshelle, botrshelle;
  struct edge toplshelle, toprshelle;
  struct edge brokenshelle;
  struct edge checkshelle;
  struct edge rightedge;
  struct edge newedge;
  struct edge *encroached;
  point first;
  point leftpoint, rightpoint, botpoint, toppoint, farpoint;
  REAL attrib;
  REAL area;
  enum insertsiteresult success;
  enum locateresult intersect;
  int doflip;
  int mirrorflag;
  int i;
  triangle ptr;                         /* Temporary variable used by sym(). */
  shelle sptr;         /* Temporary variable used by spivot() and tspivot(). */

  if (verbose > 1) {
    printf("  Inserting (%.12g, %.12g).\n", insertpoint[0], insertpoint[1]);
  }
  if (splitedge == (struct edge *) NULL) {
    /* Find the location of the point to be inserted.  Check if a good */
    /*   starting triangle has already been provided by the caller.    */
    if (searchtri->tri == (triangle *) NULL) {
      /* Find a boundary triangle. */
      horiz.tri = dummytri;
      horiz.orient = 0;
      symself(horiz);
      /* Search for a triangle containing `insertpoint'. */
      intersect = locate(insertpoint, &horiz);
    } else {
      /* Start searching from the triangle provided by the caller. */
      triedgecopy(*searchtri, horiz);
      intersect = preciselocate(insertpoint, &horiz);
    }
  } else {
    /* The calling routine provides the edge in which the point is inserted. */
    triedgecopy(*searchtri, horiz);
    intersect = ONEDGE;
  }
  if (intersect == ONVERTEX) {
    /* There's already a vertex there.  Return in `searchtri' a triangle */
    /*   whose origin is the existing vertex.                            */
    triedgecopy(horiz, *searchtri);
    triedgecopy(horiz, recenttri);
    return DUPLICATEPOINT;
  }
  if ((intersect == ONEDGE) || (intersect == OUTSIDE)) {
    /* The vertex falls on an edge or boundary. */
    if (checksegments && (splitedge == (struct edge *) NULL)) {
      /* Check whether the vertex falls on a shell edge. */
      tspivot(horiz, brokenshelle);
      if (brokenshelle.sh != dummysh) {
        /* The vertex falls on a shell edge. */
        if (segmentflaws) {
          if (nobisect == 0) {
            /* Add the shell edge to the list of encroached segments. */
            encroached = (struct edge *) poolalloc(&badsegments);
            shellecopy(brokenshelle, *encroached);
          } else if ((nobisect == 1) && (intersect == ONEDGE)) {
            /* This segment may be split only if it is an internal boundary. */
            sym(horiz, testtri);
            if (testtri.tri != dummytri) {
              /* Add the shell edge to the list of encroached segments. */
              encroached = (struct edge *) poolalloc(&badsegments);
              shellecopy(brokenshelle, *encroached);
            }
          }
        }
        /* Return a handle whose primary edge contains the point, */
        /*   which has not been inserted.                         */
        triedgecopy(horiz, *searchtri);
        triedgecopy(horiz, recenttri);
        return VIOLATINGPOINT;
      }
    }
    /* Insert the point on an edge, dividing one triangle into two (if */
    /*   the edge lies on a boundary) or two triangles into four.      */
    lprev(horiz, botright);
    sym(botright, botrcasing);
    sym(horiz, topright);
    /* Is there a second triangle?  (Or does this edge lie on a boundary?) */
    mirrorflag = topright.tri != dummytri;
    if (mirrorflag) {
      lnextself(topright);
      sym(topright, toprcasing);
      maketriangle(&newtopright);
    } else {
      /* Splitting the boundary edge increases the number of boundary edges. */
      hullsize++;
    }
    maketriangle(&newbotright);

    /* Set the vertices of changed and new triangles. */
    org(horiz, rightpoint);
    dest(horiz, leftpoint);
    apex(horiz, botpoint);
    setorg(newbotright, botpoint);
    setdest(newbotright, rightpoint);
    setapex(newbotright, insertpoint);
    setorg(horiz, insertpoint);
    for (i = 0; i < eextras; i++) {
      /* Set the element attributes of a new triangle. */
      setelemattribute(newbotright, i, elemattribute(botright, i));
    }
    if (vararea) {
      /* Set the area constraint of a new triangle. */
      setareabound(newbotright, areabound(botright));
    }
    if (mirrorflag) {
      dest(topright, toppoint);
      setorg(newtopright, rightpoint);
      setdest(newtopright, toppoint);
      setapex(newtopright, insertpoint);
      setorg(topright, insertpoint);
      for (i = 0; i < eextras; i++) {
        /* Set the element attributes of another new triangle. */
        setelemattribute(newtopright, i, elemattribute(topright, i));
      }
      if (vararea) {
        /* Set the area constraint of another new triangle. */
        setareabound(newtopright, areabound(topright));
      }
    }

    /* There may be shell edges that need to be bonded */
    /*   to the new triangle(s).                       */
    if (checksegments) {
      tspivot(botright, botrshelle);
      if (botrshelle.sh != dummysh) {
        tsdissolve(botright);
        tsbond(newbotright, botrshelle);
      }
      if (mirrorflag) {
        tspivot(topright, toprshelle);
        if (toprshelle.sh != dummysh) {
          tsdissolve(topright);
          tsbond(newtopright, toprshelle);
        }
      }
    }

    /* Bond the new triangle(s) to the surrounding triangles. */
    bond(newbotright, botrcasing);
    lprevself(newbotright);
    bond(newbotright, botright);
    lprevself(newbotright);
    if (mirrorflag) {
      bond(newtopright, toprcasing);
      lnextself(newtopright);
      bond(newtopright, topright);
      lnextself(newtopright);
      bond(newtopright, newbotright);
    }

    if (splitedge != (struct edge *) NULL) {
      /* Split the shell edge into two. */
      setsdest(*splitedge, insertpoint);
      ssymself(*splitedge);
      spivot(*splitedge, rightedge);
      insertshelle(&newbotright, mark(*splitedge));
      tspivot(newbotright, newedge);
      sbond(*splitedge, newedge);
      ssymself(newedge);
      sbond(newedge, rightedge);
      ssymself(*splitedge);
    }

#ifdef SELF_CHECK
    if (counterclockwise(rightpoint, leftpoint, botpoint) < 0.0) {
      printf("Internal error in insertsite():\n");
      printf("  Clockwise triangle prior to edge point insertion (bottom).\n");
    }
    if (mirrorflag) {
      if (counterclockwise(leftpoint, rightpoint, toppoint) < 0.0) {
        printf("Internal error in insertsite():\n");
        printf("  Clockwise triangle prior to edge point insertion (top).\n");
      }
      if (counterclockwise(rightpoint, toppoint, insertpoint) < 0.0) {
        printf("Internal error in insertsite():\n");
        printf("  Clockwise triangle after edge point insertion (top right).\n"
               );
      }
      if (counterclockwise(toppoint, leftpoint, insertpoint) < 0.0) {
        printf("Internal error in insertsite():\n");
        printf("  Clockwise triangle after edge point insertion (top left).\n"
               );
      }
    }
    if (counterclockwise(leftpoint, botpoint, insertpoint) < 0.0) {
      printf("Internal error in insertsite():\n");
      printf("  Clockwise triangle after edge point insertion (bottom left).\n"
             );
    }
    if (counterclockwise(botpoint, rightpoint, insertpoint) < 0.0) {
      printf("Internal error in insertsite():\n");
      printf(
        "  Clockwise triangle after edge point insertion (bottom right).\n");
    }
#endif /* SELF_CHECK */
    if (verbose > 2) {
      printf("  Updating bottom left ");
      printtriangle(&botright);
      if (mirrorflag) {
        printf("  Updating top left ");
        printtriangle(&topright);
        printf("  Creating top right ");
        printtriangle(&newtopright);
      }
      printf("  Creating bottom right ");
      printtriangle(&newbotright);
    }

    /* Position `horiz' on the first edge to check for */
    /*   the Delaunay property.                        */
    lnextself(horiz);
  } else {
    /* Insert the point in a triangle, splitting it into three. */
    lnext(horiz, botleft);
    lprev(horiz, botright);
    sym(botleft, botlcasing);
    sym(botright, botrcasing);
    maketriangle(&newbotleft);
    maketriangle(&newbotright);

    /* Set the vertices of changed and new triangles. */
    org(horiz, rightpoint);
    dest(horiz, leftpoint);
    apex(horiz, botpoint);
    setorg(newbotleft, leftpoint);
    setdest(newbotleft, botpoint);
    setapex(newbotleft, insertpoint);
    setorg(newbotright, botpoint);
    setdest(newbotright, rightpoint);
    setapex(newbotright, insertpoint);
    setapex(horiz, insertpoint);
    for (i = 0; i < eextras; i++) {
      /* Set the element attributes of the new triangles. */
      attrib = elemattribute(horiz, i);
      setelemattribute(newbotleft, i, attrib);
      setelemattribute(newbotright, i, attrib);
    }
    if (vararea) {
      /* Set the area constraint of the new triangles. */
      area = areabound(horiz);
      setareabound(newbotleft, area);
      setareabound(newbotright, area);
    }

    /* There may be shell edges that need to be bonded */
    /*   to the new triangles.                         */
    if (checksegments) {
      tspivot(botleft, botlshelle);
      if (botlshelle.sh != dummysh) {
        tsdissolve(botleft);
        tsbond(newbotleft, botlshelle);
      }
      tspivot(botright, botrshelle);
      if (botrshelle.sh != dummysh) {
        tsdissolve(botright);
        tsbond(newbotright, botrshelle);
      }
    }

    /* Bond the new triangles to the surrounding triangles. */
    bond(newbotleft, botlcasing);
    bond(newbotright, botrcasing);
    lnextself(newbotleft);
    lprevself(newbotright);
    bond(newbotleft, newbotright);
    lnextself(newbotleft);
    bond(botleft, newbotleft);
    lprevself(newbotright);
    bond(botright, newbotright);

#ifdef SELF_CHECK
    if (counterclockwise(rightpoint, leftpoint, botpoint) < 0.0) {
      printf("Internal error in insertsite():\n");
      printf("  Clockwise triangle prior to point insertion.\n");
    }
    if (counterclockwise(rightpoint, leftpoint, insertpoint) < 0.0) {
      printf("Internal error in insertsite():\n");
      printf("  Clockwise triangle after point insertion (top).\n");
    }
    if (counterclockwise(leftpoint, botpoint, insertpoint) < 0.0) {
      printf("Internal error in insertsite():\n");
      printf("  Clockwise triangle after point insertion (left).\n");
    }
    if (counterclockwise(botpoint, rightpoint, insertpoint) < 0.0) {
      printf("Internal error in insertsite():\n");
      printf("  Clockwise triangle after point insertion (right).\n");
    }
#endif /* SELF_CHECK */
    if (verbose > 2) {
      printf("  Updating top ");
      printtriangle(&horiz);
      printf("  Creating left ");
      printtriangle(&newbotleft);
      printf("  Creating right ");
      printtriangle(&newbotright);
    }
  }

  /* The insertion is successful by default, unless an encroached */
  /*   edge is found.                                             */
  success = SUCCESSFULPOINT;
  /* Circle around the newly inserted vertex, checking each edge opposite */
  /*   it for the Delaunay property.  Non-Delaunay edges are flipped.     */
  /*   `horiz' is always the edge being checked.  `first' marks where to  */
  /*   stop circling.                                                     */
  org(horiz, first);
  rightpoint = first;
  dest(horiz, leftpoint);
  /* Circle until finished. */
  while (1) {
    /* By default, the edge will be flipped. */
    doflip = 1;
    if (checksegments) {
      /* Check for a segment, which cannot be flipped. */
      tspivot(horiz, checkshelle);
      if (checkshelle.sh != dummysh) {
        /* The edge is a segment and cannot be flipped. */
        doflip = 0;
#ifndef CDT_ONLY
        if (segmentflaws) {
          /* Does the new point encroach upon this segment? */
          if (checkedge4encroach(&checkshelle)) {
            success = ENCROACHINGPOINT;
          }
        }
#endif /* not CDT_ONLY */
      }
    }
    if (doflip) {
      /* Check if the edge is a boundary edge. */
      sym(horiz, top);
      if (top.tri == dummytri) {
        /* The edge is a boundary edge and cannot be flipped. */
        doflip = 0;
      } else {
        /* Find the point on the other side of the edge. */
        apex(top, farpoint);
        /* In the incremental Delaunay triangulation algorithm, any of    */
        /*   `leftpoint', `rightpoint', and `farpoint' could be vertices  */
        /*   of the triangular bounding box.  These vertices must be      */
        /*   treated as if they are infinitely distant, even though their */
        /*   "coordinates" are not.                                       */
        if ((leftpoint == infpoint1) || (leftpoint == infpoint2)
                   || (leftpoint == infpoint3)) {
          /* `leftpoint' is infinitely distant.  Check the convexity of */
          /*   the boundary of the triangulation.  'farpoint' might be  */
          /*   infinite as well, but trust me, this same condition      */
          /*   should be applied.                                       */
          doflip = counterclockwise(insertpoint, rightpoint, farpoint) > 0.0;
        } else if ((rightpoint == infpoint1) || (rightpoint == infpoint2)
                   || (rightpoint == infpoint3)) {
          /* `rightpoint' is infinitely distant.  Check the convexity of */
          /*   the boundary of the triangulation.  'farpoint' might be  */
          /*   infinite as well, but trust me, this same condition      */
          /*   should be applied.                                       */
          doflip = counterclockwise(farpoint, leftpoint, insertpoint) > 0.0;
        } else if ((farpoint == infpoint1) || (farpoint == infpoint2)
            || (farpoint == infpoint3)) {
          /* `farpoint' is infinitely distant and cannot be inside */
          /*   the circumcircle of the triangle `horiz'.           */
          doflip = 0;
        } else {
          /* Test whether the edge is locally Delaunay. */
          doflip = incircle(leftpoint, insertpoint, rightpoint, farpoint)
                   > 0.0;
        }
        if (doflip) {
          /* We made it!  Flip the edge `horiz' by rotating its containing */
          /*   quadrilateral (the two triangles adjacent to `horiz').      */
          /* Identify the casing of the quadrilateral. */
          lprev(top, topleft);
          sym(topleft, toplcasing);
          lnext(top, topright);
          sym(topright, toprcasing);
          lnext(horiz, botleft);
          sym(botleft, botlcasing);
          lprev(horiz, botright);
          sym(botright, botrcasing);
          /* Rotate the quadrilateral one-quarter turn counterclockwise. */
          bond(topleft, botlcasing);
          bond(botleft, botrcasing);
          bond(botright, toprcasing);
          bond(topright, toplcasing);
          if (checksegments) {
            /* Check for shell edges and rebond them to the quadrilateral. */
            tspivot(topleft, toplshelle);
            tspivot(botleft, botlshelle);
            tspivot(botright, botrshelle);
            tspivot(topright, toprshelle);
            if (toplshelle.sh == dummysh) {
              tsdissolve(topright);
            } else {
              tsbond(topright, toplshelle);
            }
            if (botlshelle.sh == dummysh) {
              tsdissolve(topleft);
            } else {
              tsbond(topleft, botlshelle);
            }
            if (botrshelle.sh == dummysh) {
              tsdissolve(botleft);
            } else {
              tsbond(botleft, botrshelle);
            }
            if (toprshelle.sh == dummysh) {
              tsdissolve(botright);
            } else {
              tsbond(botright, toprshelle);
            }
          }
          /* New point assignments for the rotated quadrilateral. */
          setorg(horiz, farpoint);
          setdest(horiz, insertpoint);
          setapex(horiz, rightpoint);
          setorg(top, insertpoint);
          setdest(top, farpoint);
          setapex(top, leftpoint);
          for (i = 0; i < eextras; i++) {
            /* Take the average of the two triangles' attributes. */
            attrib = 0.5 * (elemattribute(top, i) + elemattribute(horiz, i));
            setelemattribute(top, i, attrib);
            setelemattribute(horiz, i, attrib);
          }
          if (vararea) {
            if ((areabound(top) <= 0.0) || (areabound(horiz) <= 0.0)) {
              area = -1.0;
            } else {
              /* Take the average of the two triangles' area constraints.    */
              /*   This prevents small area constraints from migrating a     */
              /*   long, long way from their original location due to flips. */
              area = 0.5 * (areabound(top) + areabound(horiz));
            }
            setareabound(top, area);
            setareabound(horiz, area);
          }
#ifdef SELF_CHECK
          if (insertpoint != (point) NULL) {
            if (counterclockwise(leftpoint, insertpoint, rightpoint) < 0.0) {
              printf("Internal error in insertsite():\n");
              printf("  Clockwise triangle prior to edge flip (bottom).\n");
            }
            /* The following test has been removed because constrainededge() */
            /*   sometimes generates inverted triangles that insertsite()    */
            /*   removes.                                                    */
/*
            if (counterclockwise(rightpoint, farpoint, leftpoint) < 0.0) {
              printf("Internal error in insertsite():\n");
              printf("  Clockwise triangle prior to edge flip (top).\n");
            }
*/
            if (counterclockwise(farpoint, leftpoint, insertpoint) < 0.0) {
              printf("Internal error in insertsite():\n");
              printf("  Clockwise triangle after edge flip (left).\n");
            }
            if (counterclockwise(insertpoint, rightpoint, farpoint) < 0.0) {
              printf("Internal error in insertsite():\n");
              printf("  Clockwise triangle after edge flip (right).\n");
            }
          }
#endif /* SELF_CHECK */
          if (verbose > 2) {
            printf("  Edge flip results in left ");
            lnextself(topleft);
            printtriangle(&topleft);
            printf("  and right ");
            printtriangle(&horiz);
          }
          /* On the next iterations, consider the two edges that were  */
          /*   exposed (this is, are now visible to the newly inserted */
          /*   point) by the edge flip.                                */
          lprevself(horiz);
          leftpoint = farpoint;
        }
      }
    }
    if (!doflip) {
      /* The handle `horiz' is accepted as locally Delaunay. */
#ifndef CDT_ONLY
      if (triflaws) {
        /* Check the triangle `horiz' for quality. */
        testtriangle(&horiz);
      }
#endif /* not CDT_ONLY */
      /* Look for the next edge around the newly inserted point. */
      lnextself(horiz);
      sym(horiz, testtri);
      /* Check for finishing a complete revolution about the new point, or */
      /*   falling off the edge of the triangulation.  The latter will     */
      /*   happen when a point is inserted at a boundary.                  */
      if ((leftpoint == first) || (testtri.tri == dummytri)) {
        /* We're done.  Return a triangle whose origin is the new point. */
        lnext(horiz, *searchtri);
        lnext(horiz, recenttri);
        return success;
      }
      /* Finish finding the next edge around the newly inserted point. */
      lnext(testtri, horiz);
      rightpoint = leftpoint;
      dest(horiz, leftpoint);
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void internalerror ( )

Definition at line 2657 of file tlvisTrn_triangle.c.

References exit().

Referenced by finddirection(), insertsegment(), and segmentintersection().

{
  printf("  Please report this bug to jrs@cs.cmu.edu\n");
  printf("  Include the message above, your input data set, and the exact\n");
  printf("    command line you used to run Triangle.\n");
  exit(1);
}

Here is the call graph for this function:

Here is the caller graph for this function:

enum locateresult locate ( point  searchpoint,
struct triedge searchtri 
)

Definition at line 5771 of file tlvisTrn_triangle.c.

References memorypool::alignbytes, counterclockwise(), dest, dist(), memorypool::firstblock, memorypool::items, memorypool::itemwords, lnextself, memorypool::maxitems, ONEDGE, ONVERTEX, org, triedge::orient, preciselocate(), ptr, randomnation(), REAL, recenttri, SAMPLEFACTOR, samples, symself, triedge::tri, triangles, triedgecopy, TRIPERBLOCK, verbose, and VOID.

Referenced by carveholes(), insertsegment(), and insertsite().

{
  VOID **sampleblock;
  triangle *firsttri;
  struct triedge sampletri;
  point torg, tdest;
  unsigned long alignptr;
  REAL searchdist, dist;
  REAL ahead;
  long sampleblocks, samplesperblock, samplenum;
  long triblocks;
  long i, j;
  triangle ptr;                         /* Temporary variable used by sym(). */

  if (verbose > 2) {
    printf("  Randomly sampling for a triangle near point (%.12g, %.12g).\n",
           searchpoint[0], searchpoint[1]);
  }
  /* Record the distance from the suggested starting triangle to the */
  /*   point we seek.                                                */
  org(*searchtri, torg);
  searchdist = (searchpoint[0] - torg[0]) * (searchpoint[0] - torg[0])
             + (searchpoint[1] - torg[1]) * (searchpoint[1] - torg[1]);
  if (verbose > 2) {
    printf("    Boundary triangle has origin (%.12g, %.12g).\n",
           torg[0], torg[1]);
  }

  /* If a recently encountered triangle has been recorded and has not been */
  /*   deallocated, test it as a good starting point.                      */
  if (recenttri.tri != (triangle *) NULL) {
    if (recenttri.tri[3] != (triangle) NULL) {
      org(recenttri, torg);
      if ((torg[0] == searchpoint[0]) && (torg[1] == searchpoint[1])) {
        triedgecopy(recenttri, *searchtri);
        return ONVERTEX;
      }
      dist = (searchpoint[0] - torg[0]) * (searchpoint[0] - torg[0])
           + (searchpoint[1] - torg[1]) * (searchpoint[1] - torg[1]);
      if (dist < searchdist) {
        triedgecopy(recenttri, *searchtri);
        searchdist = dist;
        if (verbose > 2) {
          printf("    Choosing recent triangle with origin (%.12g, %.12g).\n",
                 torg[0], torg[1]);
        }
      }
    }
  }

  /* The number of random samples taken is proportional to the cube root of */
  /*   the number of triangles in the mesh.  The next bit of code assumes   */
  /*   that the number of triangles increases monotonically.                */
  while (SAMPLEFACTOR * samples * samples * samples < triangles.items) {
    samples++;
  }
  triblocks = (triangles.maxitems + TRIPERBLOCK - 1) / TRIPERBLOCK;
  samplesperblock = 1 + (samples / triblocks);
  sampleblocks = samples / samplesperblock;
  sampleblock = triangles.firstblock;
  sampletri.orient = 0;
  for (i = 0; i < sampleblocks; i++) {
    alignptr = (unsigned long) (sampleblock + 1);
    firsttri = (triangle *) (alignptr + (unsigned long) triangles.alignbytes
                          - (alignptr % (unsigned long) triangles.alignbytes));
    for (j = 0; j < samplesperblock; j++) {
      if (i == triblocks - 1) {
        samplenum = randomnation((int)
                                 (triangles.maxitems - (i * TRIPERBLOCK)));
      } else {
        samplenum = randomnation(TRIPERBLOCK);
      }
      sampletri.tri = (triangle *)
                      (firsttri + (samplenum * triangles.itemwords));
      if (sampletri.tri[3] != (triangle) NULL) {
        org(sampletri, torg);
        dist = (searchpoint[0] - torg[0]) * (searchpoint[0] - torg[0])
             + (searchpoint[1] - torg[1]) * (searchpoint[1] - torg[1]);
        if (dist < searchdist) {
          triedgecopy(sampletri, *searchtri);
          searchdist = dist;
          if (verbose > 2) {
            printf("    Choosing triangle with origin (%.12g, %.12g).\n",
                   torg[0], torg[1]);
          }
        }
      }
    }
    sampleblock = (VOID **) *sampleblock;
  }
  /* Where are we? */
  org(*searchtri, torg);
  dest(*searchtri, tdest);
  /* Check the starting triangle's vertices. */
  if ((torg[0] == searchpoint[0]) && (torg[1] == searchpoint[1])) {
    return ONVERTEX;
  }
  if ((tdest[0] == searchpoint[0]) && (tdest[1] == searchpoint[1])) {
    lnextself(*searchtri);
    return ONVERTEX;
  }
  /* Orient `searchtri' to fit the preconditions of calling preciselocate(). */
  ahead = counterclockwise(torg, tdest, searchpoint);
  if (ahead < 0.0) {
    /* Turn around so that `searchpoint' is to the left of the */
    /*   edge specified by `searchtri'.                        */
    symself(*searchtri);
  } else if (ahead == 0.0) {
    /* Check if `searchpoint' is between `torg' and `tdest'. */
    if (((torg[0] < searchpoint[0]) == (searchpoint[0] < tdest[0]))
        && ((torg[1] < searchpoint[1]) == (searchpoint[1] < tdest[1]))) {
      return ONEDGE;
    }
  }
  return preciselocate(searchpoint, searchtri);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void makepointmap ( )

Definition at line 5552 of file tlvisTrn_triangle.c.

References encode, org, triedge::orient, setpoint2tri, traversalinit(), triedge::tri, triangles, triangletraverse(), and verbose.

Referenced by formskeleton().

{
  struct triedge triangleloop;
  point triorg;

  if (verbose) {
    printf("    Constructing mapping from points to triangles.\n");
  }
  traversalinit(&triangles);
  triangleloop.tri = triangletraverse();
  while (triangleloop.tri != (triangle *) NULL) {
    /* Check all three points of the triangle. */
    for (triangleloop.orient = 0; triangleloop.orient < 3;
         triangleloop.orient++) {
      org(triangleloop, triorg);
      setpoint2tri(triorg, encode(triangleloop));
    }
    triangleloop.tri = triangletraverse();
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void makeshelle ( struct edge newedge)

Definition at line 3861 of file tlvisTrn_triangle.c.

References dummysh, dummytri, poolalloc(), setmark, edge::sh, and shelles.

Referenced by insertshelle().

{
  newedge->sh = (shelle *) poolalloc(&shelles);
  /* Initialize the two adjoining shell edges to be the omnipresent */
  /*   shell edge.                                                  */
  newedge->sh[0] = (shelle) dummysh;
  newedge->sh[1] = (shelle) dummysh;
  /* Two NULL vertex points. */
  newedge->sh[2] = (shelle) NULL;
  newedge->sh[3] = (shelle) NULL;
  /* Initialize the two adjoining triangles to be "outer space". */
  newedge->sh[4] = (shelle) dummytri;
  newedge->sh[5] = (shelle) dummytri;
  /* Set the boundary marker to zero. */
  setmark(*newedge, 0);

  newedge->shorient = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void maketriangle ( struct triedge newtriedge)

Definition at line 3824 of file tlvisTrn_triangle.c.

References dummysh, dummytri, eextras, poolalloc(), setareabound, setelemattribute, triedge::tri, triangles, useshelles, and vararea.

Referenced by divconqrecurse(), insertsite(), and mergehulls().

{
  int i;

  newtriedge->tri = (triangle *) poolalloc(&triangles);
  /* Initialize the three adjoining triangles to be "outer space". */
  newtriedge->tri[0] = (triangle) dummytri;
  newtriedge->tri[1] = (triangle) dummytri;
  newtriedge->tri[2] = (triangle) dummytri;
  /* Three NULL vertex points. */
  newtriedge->tri[3] = (triangle) NULL;
  newtriedge->tri[4] = (triangle) NULL;
  newtriedge->tri[5] = (triangle) NULL;
  /* Initialize the three adjoining shell edges to be the omnipresent */
  /*   shell edge.                                                    */
  if (useshelles) {
    newtriedge->tri[6] = (triangle) dummysh;
    newtriedge->tri[7] = (triangle) dummysh;
    newtriedge->tri[8] = (triangle) dummysh;
  }
  for (i = 0; i < eextras; i++) {
    setelemattribute(*newtriedge, i, 0.0);
  }
  if (vararea) {
    setareabound(*newtriedge, -1.0);
  }

  newtriedge->orient = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* malloc ( )
void markhull ( )

Definition at line 9864 of file tlvisTrn_triangle.c.

References dummytri, insertshelle(), lnextself, oprev, triedge::orient, ptr, symself, triedge::tri, triedgecopy, and triedgeequal.

Referenced by formskeleton().

{
  struct triedge hulltri;
  struct triedge nexttri;
  struct triedge starttri;
  triangle ptr;             /* Temporary variable used by sym() and oprev(). */

  /* Find a triangle handle on the hull. */
  hulltri.tri = dummytri;
  hulltri.orient = 0;
  symself(hulltri);
  /* Remember where we started so we know when to stop. */
  triedgecopy(hulltri, starttri);
  /* Go once counterclockwise around the convex hull. */
  do {
    /* Create a shell edge if there isn't already one here. */
    insertshelle(&hulltri, 1);
    /* To find the next hull edge, go clockwise around the next vertex. */
    lnextself(hulltri);
    oprev(hulltri, nexttri);
    while (nexttri.tri != dummytri) {
      triedgecopy(nexttri, hulltri);
      oprev(hulltri, nexttri);
    }
  } while (!triedgeequal(hulltri, starttri));
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 7162 of file tlvisTrn_triangle.c.

References apex, bond, counterclockwise(), dest, dwyer, incircle(), lnext, lnextself, lprev, lprevself, maketriangle(), org, printtriangle(), ptr, setapex, setdest, setorg, sym, symself, triedgecopy, and verbose.

Referenced by divconqrecurse().

{
  struct triedge leftcand, rightcand;
  struct triedge baseedge;
  struct triedge nextedge;
  struct triedge sidecasing, topcasing, outercasing;
  struct triedge checkedge;
  point innerleftdest;
  point innerrightorg;
  point innerleftapex, innerrightapex;
  point farleftpt, farrightpt;
  point farleftapex, farrightapex;
  point lowerleft, lowerright;
  point upperleft, upperright;
  point nextapex;
  point checkvertex;
  int changemade;
  int badedge;
  int leftfinished, rightfinished;
  triangle ptr;                         /* Temporary variable used by sym(). */

  dest(*innerleft, innerleftdest);
  apex(*innerleft, innerleftapex);
  org(*innerright, innerrightorg);
  apex(*innerright, innerrightapex);
  /* Special treatment for horizontal cuts. */
  if (dwyer && (axis == 1)) {
    org(*farleft, farleftpt);
    apex(*farleft, farleftapex);
    dest(*farright, farrightpt);
    apex(*farright, farrightapex);
    /* The pointers to the extremal points are shifted to point to the */
    /*   topmost and bottommost point of each hull, rather than the    */
    /*   leftmost and rightmost points.                                */
    while (farleftapex[1] < farleftpt[1]) {
      lnextself(*farleft);
      symself(*farleft);
      farleftpt = farleftapex;
      apex(*farleft, farleftapex);
    }
    sym(*innerleft, checkedge);
    apex(checkedge, checkvertex);
    while (checkvertex[1] > innerleftdest[1]) {
      lnext(checkedge, *innerleft);
      innerleftapex = innerleftdest;
      innerleftdest = checkvertex;
      sym(*innerleft, checkedge);
      apex(checkedge, checkvertex);
    }
    while (innerrightapex[1] < innerrightorg[1]) {
      lnextself(*innerright);
      symself(*innerright);
      innerrightorg = innerrightapex;
      apex(*innerright, innerrightapex);
    }
    sym(*farright, checkedge);
    apex(checkedge, checkvertex);
    while (checkvertex[1] > farrightpt[1]) {
      lnext(checkedge, *farright);
      farrightapex = farrightpt;
      farrightpt = checkvertex;
      sym(*farright, checkedge);
      apex(checkedge, checkvertex);
    }
  }
  /* Find a line tangent to and below both hulls. */
  do {
    changemade = 0;
    /* Make innerleftdest the "bottommost" point of the left hull. */
    if (counterclockwise(innerleftdest, innerleftapex, innerrightorg) > 0.0) {
      lprevself(*innerleft);
      symself(*innerleft);
      innerleftdest = innerleftapex;
      apex(*innerleft, innerleftapex);
      changemade = 1;
    }
    /* Make innerrightorg the "bottommost" point of the right hull. */
    if (counterclockwise(innerrightapex, innerrightorg, innerleftdest) > 0.0) {
      lnextself(*innerright);
      symself(*innerright);
      innerrightorg = innerrightapex;
      apex(*innerright, innerrightapex);
      changemade = 1;
    }
  } while (changemade);
  /* Find the two candidates to be the next "gear tooth". */
  sym(*innerleft, leftcand);
  sym(*innerright, rightcand);
  /* Create the bottom new bounding triangle. */
  maketriangle(&baseedge);
  /* Connect it to the bounding boxes of the left and right triangulations. */
  bond(baseedge, *innerleft);
  lnextself(baseedge);
  bond(baseedge, *innerright);
  lnextself(baseedge);
  setorg(baseedge, innerrightorg);
  setdest(baseedge, innerleftdest);
  /* Apex is intentionally left NULL. */
  if (verbose > 2) {
    printf("  Creating base bounding ");
    printtriangle(&baseedge);
  }
  /* Fix the extreme triangles if necessary. */
  org(*farleft, farleftpt);
  if (innerleftdest == farleftpt) {
    lnext(baseedge, *farleft);
  }
  dest(*farright, farrightpt);
  if (innerrightorg == farrightpt) {
    lprev(baseedge, *farright);
  }
  /* The vertices of the current knitting edge. */
  lowerleft = innerleftdest;
  lowerright = innerrightorg;
  /* The candidate vertices for knitting. */
  apex(leftcand, upperleft);
  apex(rightcand, upperright);
  /* Walk up the gap between the two triangulations, knitting them together. */
  while (1) {
    /* Have we reached the top?  (This isn't quite the right question,       */
    /*   because even though the left triangulation might seem finished now, */
    /*   moving up on the right triangulation might reveal a new point of    */
    /*   the left triangulation.  And vice-versa.)                           */
    leftfinished = counterclockwise(upperleft, lowerleft, lowerright) <= 0.0;
    rightfinished = counterclockwise(upperright, lowerleft, lowerright) <= 0.0;
    if (leftfinished && rightfinished) {
      /* Create the top new bounding triangle. */
      maketriangle(&nextedge);
      setorg(nextedge, lowerleft);
      setdest(nextedge, lowerright);
      /* Apex is intentionally left NULL. */
      /* Connect it to the bounding boxes of the two triangulations. */
      bond(nextedge, baseedge);
      lnextself(nextedge);
      bond(nextedge, rightcand);
      lnextself(nextedge);
      bond(nextedge, leftcand);
      if (verbose > 2) {
        printf("  Creating top bounding ");
        printtriangle(&baseedge);
      }
      /* Special treatment for horizontal cuts. */
      if (dwyer && (axis == 1)) {
        org(*farleft, farleftpt);
        apex(*farleft, farleftapex);
        dest(*farright, farrightpt);
        apex(*farright, farrightapex);
        sym(*farleft, checkedge);
        apex(checkedge, checkvertex);
        /* The pointers to the extremal points are restored to the leftmost */
        /*   and rightmost points (rather than topmost and bottommost).     */
        while (checkvertex[0] < farleftpt[0]) {
          lprev(checkedge, *farleft);
          farleftapex = farleftpt;
          farleftpt = checkvertex;
          sym(*farleft, checkedge);
          apex(checkedge, checkvertex);
        }
        while (farrightapex[0] > farrightpt[0]) {
          lprevself(*farright);
          symself(*farright);
          farrightpt = farrightapex;
          apex(*farright, farrightapex);
        }
      }
      return;
    }
    /* Consider eliminating edges from the left triangulation. */
    if (!leftfinished) {
      /* What vertex would be exposed if an edge were deleted? */
      lprev(leftcand, nextedge);
      symself(nextedge);
      apex(nextedge, nextapex);
      /* If nextapex is NULL, then no vertex would be exposed; the */
      /*   triangulation would have been eaten right through.      */
      if (nextapex != (point) NULL) {
        /* Check whether the edge is Delaunay. */
        badedge = incircle(lowerleft, lowerright, upperleft, nextapex) > 0.0;
        while (badedge) {
          /* Eliminate the edge with an edge flip.  As a result, the    */
          /*   left triangulation will have one more boundary triangle. */
          lnextself(nextedge);
          sym(nextedge, topcasing);
          lnextself(nextedge);
          sym(nextedge, sidecasing);
          bond(nextedge, topcasing);
          bond(leftcand, sidecasing);
          lnextself(leftcand);
          sym(leftcand, outercasing);
          lprevself(nextedge);
          bond(nextedge, outercasing);
          /* Correct the vertices to reflect the edge flip. */
          setorg(leftcand, lowerleft);
          setdest(leftcand, NULL);
          setapex(leftcand, nextapex);
          setorg(nextedge, NULL);
          setdest(nextedge, upperleft);
          setapex(nextedge, nextapex);
          /* Consider the newly exposed vertex. */
          upperleft = nextapex;
          /* What vertex would be exposed if another edge were deleted? */
          triedgecopy(sidecasing, nextedge);
          apex(nextedge, nextapex);
          if (nextapex != (point) NULL) {
            /* Check whether the edge is Delaunay. */
            badedge = incircle(lowerleft, lowerright, upperleft, nextapex)
                      > 0.0;
          } else {
            /* Avoid eating right through the triangulation. */
            badedge = 0;
          }
        }
      }
    }
    /* Consider eliminating edges from the right triangulation. */
    if (!rightfinished) {
      /* What vertex would be exposed if an edge were deleted? */
      lnext(rightcand, nextedge);
      symself(nextedge);
      apex(nextedge, nextapex);
      /* If nextapex is NULL, then no vertex would be exposed; the */
      /*   triangulation would have been eaten right through.      */
      if (nextapex != (point) NULL) {
        /* Check whether the edge is Delaunay. */
        badedge = incircle(lowerleft, lowerright, upperright, nextapex) > 0.0;
        while (badedge) {
          /* Eliminate the edge with an edge flip.  As a result, the     */
          /*   right triangulation will have one more boundary triangle. */
          lprevself(nextedge);
          sym(nextedge, topcasing);
          lprevself(nextedge);
          sym(nextedge, sidecasing);
          bond(nextedge, topcasing);
          bond(rightcand, sidecasing);
          lprevself(rightcand);
          sym(rightcand, outercasing);
          lnextself(nextedge);
          bond(nextedge, outercasing);
          /* Correct the vertices to reflect the edge flip. */
          setorg(rightcand, NULL);
          setdest(rightcand, lowerright);
          setapex(rightcand, nextapex);
          setorg(nextedge, upperright);
          setdest(nextedge, NULL);
          setapex(nextedge, nextapex);
          /* Consider the newly exposed vertex. */
          upperright = nextapex;
          /* What vertex would be exposed if another edge were deleted? */
          triedgecopy(sidecasing, nextedge);
          apex(nextedge, nextapex);
          if (nextapex != (point) NULL) {
            /* Check whether the edge is Delaunay. */
            badedge = incircle(lowerleft, lowerright, upperright, nextapex)
                      > 0.0;
          } else {
            /* Avoid eating right through the triangulation. */
            badedge = 0;
          }
        }
      }
    }
    if (leftfinished || (!rightfinished &&
           (incircle(upperleft, lowerleft, lowerright, upperright) > 0.0))) {
      /* Knit the triangulations, adding an edge from `lowerleft' */
      /*   to `upperright'.                                       */
      bond(baseedge, rightcand);
      lprev(rightcand, baseedge);
      setdest(baseedge, lowerleft);
      lowerright = upperright;
      sym(baseedge, rightcand);
      apex(rightcand, upperright);
    } else {
      /* Knit the triangulations, adding an edge from `upperleft' */
      /*   to `lowerright'.                                       */
      bond(baseedge, leftcand);
      lnext(leftcand, baseedge);
      setorg(baseedge, lowerright);
      lowerleft = upperleft;
      sym(baseedge, leftcand);
      apex(leftcand, upperleft);
    }
    if (verbose > 2) {
      printf("  Connecting ");
      printtriangle(&baseedge);
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void numbernodes ( )

Definition at line 11799 of file tlvisTrn_triangle.c.

References firstnumber, points, pointtraverse(), setpointmark, and traversalinit().

Referenced by triangulate().

{
  point pointloop;
  int pointnumber;

  traversalinit(&points);
  pointloop = pointtraverse();
  pointnumber = firstnumber;
  while (pointloop != (point) NULL) {
    setpointmark(pointloop, pointnumber);
    pointloop = pointtraverse();
    pointnumber++;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void parsecommandline ( int  argc,
char **  argv 
)

Definition at line 2674 of file tlvisTrn_triangle.c.

References convex, docheck, dwyer, edgesout, exit(), FILENAMESIZE, firstnumber, fixedarea, geomview, goodangle, incremental, maxarea, minangle, neighbors, nobisect, nobound, noelewritten, noexact, noholes, noiterationnum, nonodewritten, nopolywritten, order, PI, poly, quality, quiet, REAL, refine, regionattrib, splitseg, STARTINDEX, steiner, steinerleft, strtod(), sweepline, useshelles, vararea, verbose, and voronoi.

Referenced by triangulate().

{
#ifdef TRILIBRARY
#define STARTINDEX 0
#else /* not TRILIBRARY */
#define STARTINDEX 1
  int increment;
  int meshnumber;
#endif /* not TRILIBRARY */
  int i, j, k;
  char workstring[FILENAMESIZE];

  poly = refine = quality = vararea = fixedarea = regionattrib = convex = 0;
  firstnumber = 1;
  edgesout = voronoi = neighbors = geomview = 0;
  nobound = nopolywritten = nonodewritten = noelewritten = noiterationnum = 0;
  noholes = noexact = 0;
  incremental = sweepline = 0;
  dwyer = 1;
  splitseg = 0;
  docheck = 0;
  nobisect = 0;
  steiner = -1;
  order = 1;
  minangle = 0.0;
  maxarea = -1.0;
  quiet = verbose = 0;
#ifndef TRILIBRARY
  innodefilename[0] = '\0';
#endif /* not TRILIBRARY */

  for (i = STARTINDEX; i < argc; i++) {
#ifndef TRILIBRARY
    if (argv[i][0] == '-') {
#endif /* not TRILIBRARY */
      for (j = STARTINDEX; argv[i][j] != '\0'; j++) {
        if (argv[i][j] == 'p') {
          poly = 1;
        }
#ifndef CDT_ONLY
        if (argv[i][j] == 'r') {
          refine = 1;
        }
        if (argv[i][j] == 'q') {
          quality = 1;
          if (((argv[i][j + 1] >= '0') && (argv[i][j + 1] <= '9')) ||
              (argv[i][j + 1] == '.')) {
            k = 0;
            while (((argv[i][j + 1] >= '0') && (argv[i][j + 1] <= '9')) ||
                   (argv[i][j + 1] == '.')) {
              j++;
              workstring[k] = argv[i][j];
              k++;
            }
            workstring[k] = '\0';
            minangle = (REAL) strtod(workstring, (char **) NULL);
          } else {
            minangle = 20.0;
          }
        }
        if (argv[i][j] == 'a') {
          quality = 1;
          if (((argv[i][j + 1] >= '0') && (argv[i][j + 1] <= '9')) ||
              (argv[i][j + 1] == '.')) {
            fixedarea = 1;
            k = 0;
            while (((argv[i][j + 1] >= '0') && (argv[i][j + 1] <= '9')) ||
                   (argv[i][j + 1] == '.')) {
              j++;
              workstring[k] = argv[i][j];
              k++;
            }
            workstring[k] = '\0';
            maxarea = (REAL) strtod(workstring, (char **) NULL);
            if (maxarea <= 0.0) {
              printf("Error:  Maximum area must be greater than zero.\n");
              exit(1);
            }
          } else {
            vararea = 1;
          }
        }
#endif /* not CDT_ONLY */
        if (argv[i][j] == 'A') {
          regionattrib = 1;
        }
        if (argv[i][j] == 'c') {
          convex = 1;
        }
        if (argv[i][j] == 'z') {
          firstnumber = 0;
        }
        if (argv[i][j] == 'e') {
          edgesout = 1;
        }
        if (argv[i][j] == 'v') {
          voronoi = 1;
        }
        if (argv[i][j] == 'n') {
          neighbors = 1;
        }
        if (argv[i][j] == 'g') {
          geomview = 1;
        }
        if (argv[i][j] == 'B') {
          nobound = 1;
        }
        if (argv[i][j] == 'P') {
          nopolywritten = 1;
        }
        if (argv[i][j] == 'N') {
          nonodewritten = 1;
        }
        if (argv[i][j] == 'E') {
          noelewritten = 1;
        }
#ifndef TRILIBRARY
        if (argv[i][j] == 'I') {
          noiterationnum = 1;
        }
#endif /* not TRILIBRARY */
        if (argv[i][j] == 'O') {
          noholes = 1;
        }
        if (argv[i][j] == 'X') {
          noexact = 1;
        }
        if (argv[i][j] == 'o') {
          if (argv[i][j + 1] == '2') {
            j++;
            order = 2;
          }
        }
#ifndef CDT_ONLY
        if (argv[i][j] == 'Y') {
          nobisect++;
        }
        if (argv[i][j] == 'S') {
          steiner = 0;
          while ((argv[i][j + 1] >= '0') && (argv[i][j + 1] <= '9')) {
            j++;
            steiner = steiner * 10 + (int) (argv[i][j] - '0');
          }
        }
#endif /* not CDT_ONLY */
#ifndef REDUCED
        if (argv[i][j] == 'i') {
          incremental = 1;
        }
        if (argv[i][j] == 'F') {
          sweepline = 1;
        }
#endif /* not REDUCED */
        if (argv[i][j] == 'l') {
          dwyer = 0;
        }
#ifndef REDUCED
#ifndef CDT_ONLY
        if (argv[i][j] == 's') {
          splitseg = 1;
        }
#endif /* not CDT_ONLY */
        if (argv[i][j] == 'C') {
          docheck = 1;
        }
#endif /* not REDUCED */
        if (argv[i][j] == 'Q') {
          quiet = 1;
        }
        if (argv[i][j] == 'V') {
          verbose++;
        }
#ifndef TRILIBRARY
        if ((argv[i][j] == 'h') || (argv[i][j] == 'H') ||
            (argv[i][j] == '?')) {
          info();
        }
#endif /* not TRILIBRARY */
      }
#ifndef TRILIBRARY
    } else {
      strncpy(innodefilename, argv[i], FILENAMESIZE - 1);
      innodefilename[FILENAMESIZE - 1] = '\0';
    }
#endif /* not TRILIBRARY */
  }
#ifndef TRILIBRARY
  if (innodefilename[0] == '\0') {
    syntax();
  }
  if (!strcmp(&innodefilename[strlen(innodefilename) - 5], ".node")) {
    innodefilename[strlen(innodefilename) - 5] = '\0';
  }
  if (!strcmp(&innodefilename[strlen(innodefilename) - 5], ".poly")) {
    innodefilename[strlen(innodefilename) - 5] = '\0';
    poly = 1;
  }
#ifndef CDT_ONLY
  if (!strcmp(&innodefilename[strlen(innodefilename) - 4], ".ele")) {
    innodefilename[strlen(innodefilename) - 4] = '\0';
    refine = 1;
  }
  if (!strcmp(&innodefilename[strlen(innodefilename) - 5], ".area")) {
    innodefilename[strlen(innodefilename) - 5] = '\0';
    refine = 1;
    quality = 1;
    vararea = 1;
  }
#endif /* not CDT_ONLY */
#endif /* not TRILIBRARY */
  steinerleft = steiner;
  useshelles = poly || refine || quality || convex;
  goodangle = cos(minangle * PI / 180.0);
  goodangle *= goodangle;
  if (refine && noiterationnum) {
    printf(
      "Error:  You cannot use the -I switch when refining a triangulation.\n");
    exit(1);
  }
  /* Be careful not to allocate space for element area constraints that */
  /*   will never be assigned any value (other than the default -1.0).  */
  if (!refine && !poly) {
    vararea = 0;
  }
  /* Be careful not to add an extra attribute to each element unless the */
  /*   input supports it (PSLG in, but not refining a preexisting mesh). */
  if (refine || !poly) {
    regionattrib = 0;
  }

#ifndef TRILIBRARY
  strcpy(inpolyfilename, innodefilename);
  strcpy(inelefilename, innodefilename);
  strcpy(areafilename, innodefilename);
  increment = 0;
  strcpy(workstring, innodefilename);
  j = 1;
  while (workstring[j] != '\0') {
    if ((workstring[j] == '.') && (workstring[j + 1] != '\0')) {
      increment = j + 1;
    }
    j++;
  }
  meshnumber = 0;
  if (increment > 0) {
    j = increment;
    do {
      if ((workstring[j] >= '0') && (workstring[j] <= '9')) {
        meshnumber = meshnumber * 10 + (int) (workstring[j] - '0');
      } else {
        increment = 0;
      }
      j++;
    } while (workstring[j] != '\0');
  }
  if (noiterationnum) {
    strcpy(outnodefilename, innodefilename);
    strcpy(outelefilename, innodefilename);
    strcpy(edgefilename, innodefilename);
    strcpy(vnodefilename, innodefilename);
    strcpy(vedgefilename, innodefilename);
    strcpy(neighborfilename, innodefilename);
    strcpy(offfilename, innodefilename);
    strcat(outnodefilename, ".node");
    strcat(outelefilename, ".ele");
    strcat(edgefilename, ".edge");
    strcat(vnodefilename, ".v.node");
    strcat(vedgefilename, ".v.edge");
    strcat(neighborfilename, ".neigh");
    strcat(offfilename, ".off");
  } else if (increment == 0) {
    strcpy(outnodefilename, innodefilename);
    strcpy(outpolyfilename, innodefilename);
    strcpy(outelefilename, innodefilename);
    strcpy(edgefilename, innodefilename);
    strcpy(vnodefilename, innodefilename);
    strcpy(vedgefilename, innodefilename);
    strcpy(neighborfilename, innodefilename);
    strcpy(offfilename, innodefilename);
    strcat(outnodefilename, ".1.node");
    strcat(outpolyfilename, ".1.poly");
    strcat(outelefilename, ".1.ele");
    strcat(edgefilename, ".1.edge");
    strcat(vnodefilename, ".1.v.node");
    strcat(vedgefilename, ".1.v.edge");
    strcat(neighborfilename, ".1.neigh");
    strcat(offfilename, ".1.off");
  } else {
    workstring[increment] = '%';
    workstring[increment + 1] = 'd';
    workstring[increment + 2] = '\0';
    sprintf(outnodefilename, workstring, meshnumber + 1);
    strcpy(outpolyfilename, outnodefilename);
    strcpy(outelefilename, outnodefilename);
    strcpy(edgefilename, outnodefilename);
    strcpy(vnodefilename, outnodefilename);
    strcpy(vedgefilename, outnodefilename);
    strcpy(neighborfilename, outnodefilename);
    strcpy(offfilename, outnodefilename);
    strcat(outnodefilename, ".node");
    strcat(outpolyfilename, ".poly");
    strcat(outelefilename, ".ele");
    strcat(edgefilename, ".edge");
    strcat(vnodefilename, ".v.node");
    strcat(vedgefilename, ".v.edge");
    strcat(neighborfilename, ".neigh");
    strcat(offfilename, ".off");
  }
  strcat(innodefilename, ".node");
  strcat(inpolyfilename, ".poly");
  strcat(inelefilename, ".ele");
  strcat(areafilename, ".area");
#endif /* not TRILIBRARY */
}

Here is the call graph for this function:

Here is the caller graph for this function:

void plague ( )

Definition at line 10122 of file tlvisTrn_triangle.c.

References apex, dest, dissolve, dummysh, dummytri, infect, infected, mark, onext, onextself, oprev, oprevself, org, triedge::orient, pointdealloc(), pointmark, poolalloc(), poolrestart(), ptr, setmark, setorg, setpointmark, edge::sh, shelledealloc(), stdissolve, sym, traversalinit(), traverse(), triedge::tri, triangledealloc(), triedgeequal, tsdissolve, tspivot, uninfect, verbose, and viri.

Referenced by carveholes().

{
  struct triedge testtri;
  struct triedge neighbor;
  triangle **virusloop;
  triangle **deadtri;
  struct edge neighborshelle;
  point testpoint;
  point norg, ndest;
  point deadorg, deaddest, deadapex;
  int killorg;
  triangle ptr;             /* Temporary variable used by sym() and onext(). */
  shelle sptr;                      /* Temporary variable used by tspivot(). */

  if (verbose) {
    printf("  Marking neighbors of marked triangles.\n");
  }
  /* Loop through all the infected triangles, spreading the virus to */
  /*   their neighbors, then to their neighbors' neighbors.          */
  traversalinit(&viri);
  virusloop = (triangle **) traverse(&viri);
  while (virusloop != (triangle **) NULL) {
    testtri.tri = *virusloop;
    /* A triangle is marked as infected by messing with one of its shell */
    /*   edges, setting it to an illegal value.  Hence, we have to       */
    /*   temporarily uninfect this triangle so that we can examine its   */
    /*   adjacent shell edges.                                           */
    uninfect(testtri);
    if (verbose > 2) {
      /* Assign the triangle an orientation for convenience in */
      /*   checking its points.                                */
      testtri.orient = 0;
      org(testtri, deadorg);
      dest(testtri, deaddest);
      apex(testtri, deadapex);
      printf("    Checking (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
             deadorg[0], deadorg[1], deaddest[0], deaddest[1],
             deadapex[0], deadapex[1]);
    }
    /* Check each of the triangle's three neighbors. */
    for (testtri.orient = 0; testtri.orient < 3; testtri.orient++) {
      /* Find the neighbor. */
      sym(testtri, neighbor);
      /* Check for a shell between the triangle and its neighbor. */
      tspivot(testtri, neighborshelle);
      /* Check if the neighbor is nonexistent or already infected. */
      if ((neighbor.tri == dummytri) || infected(neighbor)) {
        if (neighborshelle.sh != dummysh) {
          /* There is a shell edge separating the triangle from its */
          /*   neighbor, but both triangles are dying, so the shell */
          /*   edge dies too.                                       */
          shelledealloc(neighborshelle.sh);
          if (neighbor.tri != dummytri) {
            /* Make sure the shell edge doesn't get deallocated again */
            /*   later when the infected neighbor is visited.         */
            uninfect(neighbor);
            tsdissolve(neighbor);
            infect(neighbor);
          }
        }
      } else {                   /* The neighbor exists and is not infected. */
        if (neighborshelle.sh == dummysh) {
          /* There is no shell edge protecting the neighbor, so */
          /*   the neighbor becomes infected.                   */
          if (verbose > 2) {
            org(neighbor, deadorg);
            dest(neighbor, deaddest);
            apex(neighbor, deadapex);
            printf(
              "    Marking (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
                   deadorg[0], deadorg[1], deaddest[0], deaddest[1],
                   deadapex[0], deadapex[1]);
          }
          infect(neighbor);
          /* Ensure that the neighbor's neighbors will be infected. */
          deadtri = (triangle **) poolalloc(&viri);
          *deadtri = neighbor.tri;
        } else {               /* The neighbor is protected by a shell edge. */
          /* Remove this triangle from the shell edge. */
          stdissolve(neighborshelle);
          /* The shell edge becomes a boundary.  Set markers accordingly. */
          if (mark(neighborshelle) == 0) {
            setmark(neighborshelle, 1);
          }
          org(neighbor, norg);
          dest(neighbor, ndest);
          if (pointmark(norg) == 0) {
            setpointmark(norg, 1);
          }
          if (pointmark(ndest) == 0) {
            setpointmark(ndest, 1);
          }
        }
      }
    }
    /* Remark the triangle as infected, so it doesn't get added to the */
    /*   virus pool again.                                             */
    infect(testtri);
    virusloop = (triangle **) traverse(&viri);
  }

  if (verbose) {
    printf("  Deleting marked triangles.\n");
  }
  traversalinit(&viri);
  virusloop = (triangle **) traverse(&viri);
  while (virusloop != (triangle **) NULL) {
    testtri.tri = *virusloop;

    /* Check each of the three corners of the triangle for elimination. */
    /*   This is done by walking around each point, checking if it is   */
    /*   still connected to at least one live triangle.                 */
    for (testtri.orient = 0; testtri.orient < 3; testtri.orient++) {
      org(testtri, testpoint);
      /* Check if the point has already been tested. */
      if (testpoint != (point) NULL) {
        killorg = 1;
        /* Mark the corner of the triangle as having been tested. */
        setorg(testtri, NULL);
        /* Walk counterclockwise about the point. */
        onext(testtri, neighbor);
        /* Stop upon reaching a boundary or the starting triangle. */
        while ((neighbor.tri != dummytri)
               && (!triedgeequal(neighbor, testtri))) {
          if (infected(neighbor)) {
            /* Mark the corner of this triangle as having been tested. */
            setorg(neighbor, NULL);
          } else {
            /* A live triangle.  The point survives. */
            killorg = 0;
          }
          /* Walk counterclockwise about the point. */
          onextself(neighbor);
        }
        /* If we reached a boundary, we must walk clockwise as well. */
        if (neighbor.tri == dummytri) {
          /* Walk clockwise about the point. */
          oprev(testtri, neighbor);
          /* Stop upon reaching a boundary. */
          while (neighbor.tri != dummytri) {
            if (infected(neighbor)) {
            /* Mark the corner of this triangle as having been tested. */
              setorg(neighbor, NULL);
            } else {
              /* A live triangle.  The point survives. */
              killorg = 0;
            }
            /* Walk clockwise about the point. */
            oprevself(neighbor);
          }
        }
        if (killorg) {
          if (verbose > 1) {
            printf("    Deleting point (%.12g, %.12g)\n",
                   testpoint[0], testpoint[1]);
          }
          pointdealloc(testpoint);
        }
      }
    }

    /* Record changes in the number of boundary edges, and disconnect */
    /*   dead triangles from their neighbors.                         */
    for (testtri.orient = 0; testtri.orient < 3; testtri.orient++) {
      sym(testtri, neighbor);
      if (neighbor.tri == dummytri) {
        /* There is no neighboring triangle on this edge, so this edge    */
        /*   is a boundary edge.  This triangle is being deleted, so this */
        /*   boundary edge is deleted.                                    */
        hullsize--;
      } else {
        /* Disconnect the triangle from its neighbor. */
        dissolve(neighbor);
        /* There is a neighboring triangle on this edge, so this edge */
        /*   becomes a boundary edge when this triangle is deleted.   */
        hullsize++;
      }
    }
    /* Return the dead triangle to the pool of triangles. */
    triangledealloc(testtri.tri);
    virusloop = (triangle **) traverse(&viri);
  }
  /* Empty the virus pool. */
  poolrestart(&viri);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void pointdealloc ( point  dyingpoint)

Definition at line 3676 of file tlvisTrn_triangle.c.

References DEADPOINT, points, pooldealloc(), setpointmark, and VOID.

Referenced by plague().

{
  /* Mark the point as dead.  This makes it possible to detect dead points */
  /*   when traversing the list of all points.                             */
  setpointmark(dyingpoint, DEADPOINT);
  pooldealloc(&points, (VOID *) dyingpoint);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 7030 of file tlvisTrn_triangle.c.

References randomnation(), and REAL.

Referenced by alternateaxes().

{
  int left, right;
  int pivot;
  REAL pivot1, pivot2;
  point temp;

  if (arraysize == 2) {
    /* Recursive base case. */
    if ((sortarray[0][axis] > sortarray[1][axis]) ||
        ((sortarray[0][axis] == sortarray[1][axis]) &&
         (sortarray[0][1 - axis] > sortarray[1][1 - axis]))) {
      temp = sortarray[1];
      sortarray[1] = sortarray[0];
      sortarray[0] = temp;
    }
    return;
  }
  /* Choose a random pivot to split the array. */
  pivot = (int) randomnation(arraysize);
  pivot1 = sortarray[pivot][axis];
  pivot2 = sortarray[pivot][1 - axis];
  /* Split the array. */
  left = -1;
  right = arraysize;
  while (left < right) {
    /* Search for a point whose x-coordinate is too large for the left. */
    do {
      left++;
    } while ((left <= right) && ((sortarray[left][axis] < pivot1) ||
                                 ((sortarray[left][axis] == pivot1) &&
                                  (sortarray[left][1 - axis] < pivot2))));
    /* Search for a point whose x-coordinate is too small for the right. */
    do {
      right--;
    } while ((left <= right) && ((sortarray[right][axis] > pivot1) ||
                                 ((sortarray[right][axis] == pivot1) &&
                                  (sortarray[right][1 - axis] > pivot2))));
    if (left < right) {
      /* Swap the left and right points. */
      temp = sortarray[left];
      sortarray[left] = sortarray[right];
      sortarray[right] = temp;
    }
  }
  /* Unlike in pointsort(), at most one of the following */
  /*   conditionals is true.                             */
  if (left > median) {
    /* Recursively shuffle the left subset. */
    pointmedian(sortarray, left, median, axis);
  }
  if (right < median - 1) {
    /* Recursively shuffle the right subset. */
    pointmedian(&sortarray[right + 1], arraysize - right - 1,
                median - right - 1, axis);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void pointsort ( point sortarray,
int  arraysize 
)

Definition at line 6961 of file tlvisTrn_triangle.c.

References randomnation(), and REAL.

Referenced by divconqdelaunay().

{
  int left, right;
  int pivot;
  REAL pivotx, pivoty;
  point temp;

  if (arraysize == 2) {
    /* Recursive base case. */
    if ((sortarray[0][0] > sortarray[1][0]) ||
        ((sortarray[0][0] == sortarray[1][0]) &&
         (sortarray[0][1] > sortarray[1][1]))) {
      temp = sortarray[1];
      sortarray[1] = sortarray[0];
      sortarray[0] = temp;
    }
    return;
  }
  /* Choose a random pivot to split the array. */
  pivot = (int) randomnation(arraysize);
  pivotx = sortarray[pivot][0];
  pivoty = sortarray[pivot][1];
  /* Split the array. */
  left = -1;
  right = arraysize;
  while (left < right) {
    /* Search for a point whose x-coordinate is too large for the left. */
    do {
      left++;
    } while ((left <= right) && ((sortarray[left][0] < pivotx) ||
                                 ((sortarray[left][0] == pivotx) &&
                                  (sortarray[left][1] < pivoty))));
    /* Search for a point whose x-coordinate is too small for the right. */
    do {
      right--;
    } while ((left <= right) && ((sortarray[right][0] > pivotx) ||
                                 ((sortarray[right][0] == pivotx) &&
                                  (sortarray[right][1] > pivoty))));
    if (left < right) {
      /* Swap the left and right points. */
      temp = sortarray[left];
      sortarray[left] = sortarray[right];
      sortarray[right] = temp;
    }
  }
  if (left > 1) {
    /* Recursively sort the left subset. */
    pointsort(sortarray, left);
  }
  if (right < arraysize - 2) {
    /* Recursively sort the right subset. */
    pointsort(&sortarray[right + 1], arraysize - right - 1);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

point pointtraverse ( )

Definition at line 3691 of file tlvisTrn_triangle.c.

References DEADPOINT, pointmark, points, and traverse().

Referenced by divconqdelaunay(), numbernodes(), and writenodes().

{
  point newpoint;

  do {
    newpoint = (point) traverse(&points);
    if (newpoint == (point) NULL) {
      return (point) NULL;
    }
  } while (pointmark(newpoint) == DEADPOINT);             /* Skip dead ones. */
  return newpoint;
}

Here is the call graph for this function:

Here is the caller graph for this function:

VOID* poolalloc ( struct memorypool pool)

Definition at line 3272 of file tlvisTrn_triangle.c.

References exit(), malloc(), POINTER, REAL, and VOID.

Referenced by carveholes(), highorder(), infecthull(), insertsite(), makeshelle(), maketriangle(), plague(), regionplague(), segmentintersection(), and transfernodes().

{
  VOID *newitem;
  VOID **newblock;
  unsigned long alignptr;

  /* First check the linked list of dead items.  If the list is not   */
  /*   empty, allocate an item from the list rather than a fresh one. */
  if (pool->deaditemstack != (VOID *) NULL) {
    newitem = pool->deaditemstack;               /* Take first item in list. */
    pool->deaditemstack = * (VOID **) pool->deaditemstack;
  } else {
    /* Check if there are any free items left in the current block. */
    if (pool->unallocateditems == 0) {
      /* Check if another block must be allocated. */
      if (*(pool->nowblock) == (VOID *) NULL) {
        /* Allocate a new block of items, pointed to by the previous block. */
        newblock = (VOID **) malloc(pool->itemsperblock * pool->itembytes
                                    + sizeof(VOID *) + pool->alignbytes);
        if (newblock == (VOID **) NULL) {
          printf("Error:  Out of memory.\n");
          exit(1);
        }
        *(pool->nowblock) = (VOID *) newblock;
        /* The next block pointer is NULL. */
        *newblock = (VOID *) NULL;
      }
      /* Move to the new block. */
      pool->nowblock = (VOID **) *(pool->nowblock);
      /* Find the first item in the block.    */
      /*   Increment by the size of (VOID *). */
      alignptr = (unsigned long) (pool->nowblock + 1);
      /* Align the item on an `alignbytes'-byte boundary. */
      pool->nextitem = (VOID *)
        (alignptr + (unsigned long) pool->alignbytes
         - (alignptr % (unsigned long) pool->alignbytes));
      /* There are lots of unallocated items left in this block. */
      pool->unallocateditems = pool->itemsperblock;
    }
    /* Allocate a new item. */
    newitem = pool->nextitem;
    /* Advance `nextitem' pointer to next free item in block. */
    if (pool->itemwordtype == POINTER) {
      pool->nextitem = (VOID *) ((VOID **) pool->nextitem + pool->itemwords);
    } else {
      pool->nextitem = (VOID *) ((REAL *) pool->nextitem + pool->itemwords);
    }
    pool->unallocateditems--;
    pool->maxitems++;
  }
  pool->items++;
  return newitem;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void pooldealloc ( struct memorypool pool,
VOID *  dyingitem 
)

Definition at line 3335 of file tlvisTrn_triangle.c.

References VOID.

Referenced by pointdealloc(), shelledealloc(), and triangledealloc().

{
  /* Push freshly killed item onto stack. */
  *((VOID **) dyingitem) = pool->deaditemstack;
  pool->deaditemstack = dyingitem;
  pool->items--;
}

Here is the caller graph for this function:

void pooldeinit ( struct memorypool pool)

Definition at line 3256 of file tlvisTrn_triangle.c.

References free(), memorypool::nowblock, and VOID.

Referenced by carveholes(), and triangledeinit().

{
  while (pool->firstblock != (VOID **) NULL) {
    pool->nowblock = (VOID **) *(pool->firstblock);
    free(pool->firstblock);
    pool->firstblock = pool->nowblock;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 3174 of file tlvisTrn_triangle.c.

References exit(), memorypool::itemwordtype, malloc(), POINTER, poolrestart(), REAL, and VOID.

Referenced by carveholes(), initializepointpool(), and initializetrisegpools().

{
  int wordsize;

  /* Initialize values in the pool. */
  pool->itemwordtype = wtype;
  wordsize = (pool->itemwordtype == POINTER) ? sizeof(VOID *) : sizeof(REAL);
  /* Find the proper alignment, which must be at least as large as:   */
  /*   - The parameter `alignment'.                                   */
  /*   - The primary word type, to avoid unaligned accesses.          */
  /*   - sizeof(VOID *), so the stack of dead items can be maintained */
  /*       without unaligned accesses.                                */
  if (alignment > wordsize) {
    pool->alignbytes = alignment;
  } else {
    pool->alignbytes = wordsize;
  }
  if (sizeof(VOID *) > pool->alignbytes) {
    pool->alignbytes = sizeof(VOID *);
  }
  pool->itemwords = ((bytecount + pool->alignbytes - 1) / pool->alignbytes)
                  * (pool->alignbytes / wordsize);
  pool->itembytes = pool->itemwords * wordsize;
  pool->itemsperblock = itemcount;

  /* Allocate a block of items.  Space for `itemsperblock' items and one    */
  /*   pointer (to point to the next block) are allocated, as well as space */
  /*   to ensure alignment of the items.                                    */
  pool->firstblock = (VOID **) malloc(pool->itemsperblock * pool->itembytes
                                      + sizeof(VOID *) + pool->alignbytes);
  if (pool->firstblock == (VOID **) NULL) {
    printf("Error:  Out of memory.\n");
    exit(1);
  }
  /* Set the next block pointer to NULL. */
  *(pool->firstblock) = (VOID *) NULL;
  poolrestart(pool);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void poolrestart ( )

Referenced by plague(), poolinit(), and regionplague().

Here is the caller graph for this function:

void poolrestart ( struct memorypool pool)

Definition at line 3228 of file tlvisTrn_triangle.c.

References memorypool::items, and VOID.

{
  unsigned long alignptr;

  pool->items = 0;
  pool->maxitems = 0;

  /* Set the currently active block. */
  pool->nowblock = pool->firstblock;
  /* Find the first item in the pool.  Increment by the size of (VOID *). */
  alignptr = (unsigned long) (pool->nowblock + 1);
  /* Align the item on an `alignbytes'-byte boundary. */
  pool->nextitem = (VOID *)
    (alignptr + (unsigned long) pool->alignbytes
     - (alignptr % (unsigned long) pool->alignbytes));
  /* There are lots of unallocated items left in this block. */
  pool->unallocateditems = pool->itemsperblock;
  /* The stack of deallocated items is empty. */
  pool->deaditemstack = (VOID *) NULL;
}
enum locateresult preciselocate ( point  searchpoint,
struct triedge searchtri 
)

Definition at line 5637 of file tlvisTrn_triangle.c.

References apex, counterclockwise(), dest, dummytri, INTRIANGLE, lnext, lnextself, lprev, lprevself, ONEDGE, ONVERTEX, org, OUTSIDE, ptr, REAL, sym, triedge::tri, triedgecopy, and verbose.

Referenced by insertsite(), and locate().

{
  struct triedge backtracktri;
  point forg, fdest, fapex;
  point swappoint;
  REAL orgorient, destorient;
  int moveleft;
  triangle ptr;                         /* Temporary variable used by sym(). */

  if (verbose > 2) {
    printf("  Searching for point (%.12g, %.12g).\n",
           searchpoint[0], searchpoint[1]);
  }
  /* Where are we? */
  org(*searchtri, forg);
  dest(*searchtri, fdest);
  apex(*searchtri, fapex);
  while (1) {
    if (verbose > 2) {
      printf("    At (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
             forg[0], forg[1], fdest[0], fdest[1], fapex[0], fapex[1]);
    }
    /* Check whether the apex is the point we seek. */
    if ((fapex[0] == searchpoint[0]) && (fapex[1] == searchpoint[1])) {
      lprevself(*searchtri);
      return ONVERTEX;
    }
    /* Does the point lie on the other side of the line defined by the */
    /*   triangle edge opposite the triangle's destination?            */
    destorient = counterclockwise(forg, fapex, searchpoint);
    /* Does the point lie on the other side of the line defined by the */
    /*   triangle edge opposite the triangle's origin?                 */
    orgorient = counterclockwise(fapex, fdest, searchpoint);
    if (destorient > 0.0) {
      if (orgorient > 0.0) {
        /* Move left if the inner product of (fapex - searchpoint) and  */
        /*   (fdest - forg) is positive.  This is equivalent to drawing */
        /*   a line perpendicular to the line (forg, fdest) passing     */
        /*   through `fapex', and determining which side of this line   */
        /*   `searchpoint' falls on.                                    */
        moveleft = (fapex[0] - searchpoint[0]) * (fdest[0] - forg[0]) +
                   (fapex[1] - searchpoint[1]) * (fdest[1] - forg[1]) > 0.0;
      } else {
        moveleft = 1;
      }
    } else {
      if (orgorient > 0.0) {
        moveleft = 0;
      } else {
        /* The point we seek must be on the boundary of or inside this */
        /*   triangle.                                                 */
        if (destorient == 0.0) {
          lprevself(*searchtri);
          return ONEDGE;
        }
        if (orgorient == 0.0) {
          lnextself(*searchtri);
          return ONEDGE;
        }
        return INTRIANGLE;
      }
    }

    /* Move to another triangle.  Leave a trace `backtracktri' in case */
    /*   floating-point roundoff or some such bogey causes us to walk  */
    /*   off a boundary of the triangulation.  We can just bounce off  */
    /*   the boundary as if it were an elastic band.                   */
    if (moveleft) {
      lprev(*searchtri, backtracktri);
      fdest = fapex;
    } else {
      lnext(*searchtri, backtracktri);
      forg = fapex;
    }
    sym(backtracktri, *searchtri);

    /* Check for walking off the edge. */
    if (searchtri->tri == dummytri) {
      /* Turn around. */
      triedgecopy(backtracktri, *searchtri);
      swappoint = forg;
      forg = fdest;
      fdest = swappoint;
      apex(*searchtri, fapex);
      /* Check if the point really is beyond the triangulation boundary. */
      destorient = counterclockwise(forg, fapex, searchpoint);
      orgorient = counterclockwise(fapex, fdest, searchpoint);
      if ((orgorient < 0.0) && (destorient < 0.0)) {
        return OUTSIDE;
      }
    } else {
      apex(*searchtri, fapex);
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void printshelle ( struct edge s)

Definition at line 3094 of file tlvisTrn_triangle.c.

References decode, dummysh, dummytri, mark, triedge::orient, sdecode, sdest, edge::sh, edge::shorient, sorg, and triedge::tri.

Referenced by insertshelle().

{
  struct edge printsh;
  struct triedge printtri;
  point printpoint;

  printf("shell edge x%lx with orientation %d and mark %d:\n",
         (unsigned long) s->sh, s->shorient, mark(*s));
  sdecode(s->sh[0], printsh);
  if (printsh.sh == dummysh) {
    printf("    [0] = No shell\n");
  } else {
    printf("    [0] = x%lx  %d\n", (unsigned long) printsh.sh,
           printsh.shorient);
  }
  sdecode(s->sh[1], printsh);
  if (printsh.sh == dummysh) {
    printf("    [1] = No shell\n");
  } else {
    printf("    [1] = x%lx  %d\n", (unsigned long) printsh.sh,
           printsh.shorient);
  }
  sorg(*s, printpoint);
  if (printpoint == (point) NULL)
    printf("    Origin[%d] = NULL\n", 2 + s->shorient);
  else
    printf("    Origin[%d] = x%lx  (%.12g, %.12g)\n",
           2 + s->shorient, (unsigned long) printpoint,
           printpoint[0], printpoint[1]);
  sdest(*s, printpoint);
  if (printpoint == (point) NULL)
    printf("    Dest  [%d] = NULL\n", 3 - s->shorient);
  else
    printf("    Dest  [%d] = x%lx  (%.12g, %.12g)\n",
           3 - s->shorient, (unsigned long) printpoint,
           printpoint[0], printpoint[1]);
  decode(s->sh[4], printtri);
  if (printtri.tri == dummytri) {
    printf("    [4] = Outer space\n");
  } else {
    printf("    [4] = x%lx  %d\n", (unsigned long) printtri.tri,
           printtri.orient);
  }
  decode(s->sh[5], printtri);
  if (printtri.tri == dummytri) {
    printf("    [5] = Outer space\n");
  } else {
    printf("    [5] = x%lx  %d\n", (unsigned long) printtri.tri,
           printtri.orient);
  }
}

Here is the caller graph for this function:

void printtriangle ( struct triedge t)

Definition at line 3010 of file tlvisTrn_triangle.c.

References apex, areabound, decode, dest, dummysh, dummytri, org, triedge::orient, sdecode, edge::sh, edge::shorient, triedge::tri, useshelles, and vararea.

Referenced by divconqrecurse(), flip(), insertsite(), and mergehulls().

{
  struct triedge printtri;
  struct edge printsh;
  point printpoint;

  printf("triangle x%lx with orientation %d:\n", (unsigned long) t->tri,
         t->orient);
  decode(t->tri[0], printtri);
  if (printtri.tri == dummytri) {
    printf("    [0] = Outer space\n");
  } else {
    printf("    [0] = x%lx  %d\n", (unsigned long) printtri.tri,
           printtri.orient);
  }
  decode(t->tri[1], printtri);
  if (printtri.tri == dummytri) {
    printf("    [1] = Outer space\n");
  } else {
    printf("    [1] = x%lx  %d\n", (unsigned long) printtri.tri,
           printtri.orient);
  }
  decode(t->tri[2], printtri);
  if (printtri.tri == dummytri) {
    printf("    [2] = Outer space\n");
  } else {
    printf("    [2] = x%lx  %d\n", (unsigned long) printtri.tri,
           printtri.orient);
  }
  org(*t, printpoint);
  if (printpoint == (point) NULL)
    printf("    Origin[%d] = NULL\n", (t->orient + 1) % 3 + 3);
  else
    printf("    Origin[%d] = x%lx  (%.12g, %.12g)\n",
           (t->orient + 1) % 3 + 3, (unsigned long) printpoint,
           printpoint[0], printpoint[1]);
  dest(*t, printpoint);
  if (printpoint == (point) NULL)
    printf("    Dest  [%d] = NULL\n", (t->orient + 2) % 3 + 3);
  else
    printf("    Dest  [%d] = x%lx  (%.12g, %.12g)\n",
           (t->orient + 2) % 3 + 3, (unsigned long) printpoint,
           printpoint[0], printpoint[1]);
  apex(*t, printpoint);
  if (printpoint == (point) NULL)
    printf("    Apex  [%d] = NULL\n", t->orient + 3);
  else
    printf("    Apex  [%d] = x%lx  (%.12g, %.12g)\n",
           t->orient + 3, (unsigned long) printpoint,
           printpoint[0], printpoint[1]);
  if (useshelles) {
    sdecode(t->tri[6], printsh);
    if (printsh.sh != dummysh) {
      printf("    [6] = x%lx  %d\n", (unsigned long) printsh.sh,
             printsh.shorient);
    }
    sdecode(t->tri[7], printsh);
    if (printsh.sh != dummysh) {
      printf("    [7] = x%lx  %d\n", (unsigned long) printsh.sh,
             printsh.shorient);
    }
    sdecode(t->tri[8], printsh);
    if (printsh.sh != dummysh) {
      printf("    [8] = x%lx  %d\n", (unsigned long) printsh.sh,
             printsh.shorient);
    }
  }
  if (vararea) {
    printf("    Area constraint:  %.4g\n", areabound(*t));
  }
}

Here is the caller graph for this function:

void quality_statistics ( )

Definition at line 12614 of file tlvisTrn_triangle.c.

References apex, counterclockwise(), dest, minus1mod3, org, triedge::orient, PI, plus1mod3, REAL, traversalinit(), triedge::tri, triangles, triangletraverse(), xmax, ymax, and ymin.

Referenced by statistics().

{
  struct triedge triangleloop;
  point p[3];
  REAL cossquaretable[8];
  REAL ratiotable[16];
  REAL dx[3], dy[3];
  REAL edgelength[3];
  REAL dotproduct;
  REAL cossquare;
  REAL triarea;
  REAL shortest, longest;
  REAL trilongest2;
  REAL smallestarea, biggestarea;
  REAL triminaltitude2;
  REAL minaltitude;
  REAL triaspect2;
  REAL worstaspect;
  REAL smallestangle, biggestangle;
  REAL radconst, degconst;
  int angletable[18];
  int aspecttable[16];
  int aspectindex;
  int tendegree;
  int acutebiggest;
  int i, ii, j, k;

  printf("Mesh quality statistics:\n\n");
  radconst = PI / 18.0;
  degconst = 180.0 / PI;
  for (i = 0; i < 8; i++) {
    cossquaretable[i] = cos(radconst * (REAL) (i + 1));
    cossquaretable[i] = cossquaretable[i] * cossquaretable[i];
  }
  for (i = 0; i < 18; i++) {
    angletable[i] = 0;
  }

  ratiotable[0]  =      1.5;      ratiotable[1]  =     2.0;
  ratiotable[2]  =      2.5;      ratiotable[3]  =     3.0;
  ratiotable[4]  =      4.0;      ratiotable[5]  =     6.0;
  ratiotable[6]  =     10.0;      ratiotable[7]  =    15.0;
  ratiotable[8]  =     25.0;      ratiotable[9]  =    50.0;
  ratiotable[10] =    100.0;      ratiotable[11] =   300.0;
  ratiotable[12] =   1000.0;      ratiotable[13] = 10000.0;
  ratiotable[14] = 100000.0;      ratiotable[15] =     0.0;
  for (i = 0; i < 16; i++) {
    aspecttable[i] = 0;
  }

  worstaspect = 0.0;
  minaltitude = xmax - xmin + ymax - ymin;
  minaltitude = minaltitude * minaltitude;
  shortest = minaltitude;
  longest = 0.0;
  smallestarea = minaltitude;
  biggestarea = 0.0;
  worstaspect = 0.0;
  smallestangle = 0.0;
  biggestangle = 2.0;
  acutebiggest = 1;

  traversalinit(&triangles);
  triangleloop.tri = triangletraverse();
  triangleloop.orient = 0;
  while (triangleloop.tri != (triangle *) NULL) {
    org(triangleloop, p[0]);
    dest(triangleloop, p[1]);
    apex(triangleloop, p[2]);
    trilongest2 = 0.0;

    for (i = 0; i < 3; i++) {
      j = plus1mod3[i];
      k = minus1mod3[i];
      dx[i] = p[j][0] - p[k][0];
      dy[i] = p[j][1] - p[k][1];
      edgelength[i] = dx[i] * dx[i] + dy[i] * dy[i];
      if (edgelength[i] > trilongest2) {
        trilongest2 = edgelength[i];
      }
      if (edgelength[i] > longest) {
        longest = edgelength[i];
      }
      if (edgelength[i] < shortest) {
        shortest = edgelength[i];
      }
    }

    triarea = counterclockwise(p[0], p[1], p[2]);
    if (triarea < smallestarea) {
      smallestarea = triarea;
    }
    if (triarea > biggestarea) {
      biggestarea = triarea;
    }
    triminaltitude2 = triarea * triarea / trilongest2;
    if (triminaltitude2 < minaltitude) {
      minaltitude = triminaltitude2;
    }
    triaspect2 = trilongest2 / triminaltitude2;
    if (triaspect2 > worstaspect) {
      worstaspect = triaspect2;
    }
    aspectindex = 0;
    while ((triaspect2 > ratiotable[aspectindex] * ratiotable[aspectindex])
           && (aspectindex < 15)) {
      aspectindex++;
    }
    aspecttable[aspectindex]++;

    for (i = 0; i < 3; i++) {
      j = plus1mod3[i];
      k = minus1mod3[i];
      dotproduct = dx[j] * dx[k] + dy[j] * dy[k];
      cossquare = dotproduct * dotproduct / (edgelength[j] * edgelength[k]);
      tendegree = 8;
      for (ii = 7; ii >= 0; ii--) {
        if (cossquare > cossquaretable[ii]) {
          tendegree = ii;
        }
      }
      if (dotproduct <= 0.0) {
        angletable[tendegree]++;
        if (cossquare > smallestangle) {
          smallestangle = cossquare;
        }
        if (acutebiggest && (cossquare < biggestangle)) {
          biggestangle = cossquare;
        }
      } else {
        angletable[17 - tendegree]++;
        if (acutebiggest || (cossquare > biggestangle)) {
          biggestangle = cossquare;
          acutebiggest = 0;
        }
      }
    }
    triangleloop.tri = triangletraverse();
  }

  shortest = sqrt(shortest);
  longest = sqrt(longest);
  minaltitude = sqrt(minaltitude);
  worstaspect = sqrt(worstaspect);
  smallestarea *= 2.0;
  biggestarea *= 2.0;
  if (smallestangle >= 1.0) {
    smallestangle = 0.0;
  } else {
    smallestangle = degconst * acos(sqrt(smallestangle));
  }
  if (biggestangle >= 1.0) {
    biggestangle = 180.0;
  } else {
    if (acutebiggest) {
      biggestangle = degconst * acos(sqrt(biggestangle));
    } else {
      biggestangle = 180.0 - degconst * acos(sqrt(biggestangle));
    }
  }

  printf("  Smallest area: %16.5g   |  Largest area: %16.5g\n",
         smallestarea, biggestarea);
  printf("  Shortest edge: %16.5g   |  Longest edge: %16.5g\n",
         shortest, longest);
  printf("  Shortest altitude: %12.5g   |  Largest aspect ratio: %8.5g\n\n",
         minaltitude, worstaspect);
  printf("  Aspect ratio histogram:\n");
  printf("  1.1547 - %-6.6g    :  %8d    | %6.6g - %-6.6g     :  %8d\n",
         ratiotable[0], aspecttable[0], ratiotable[7], ratiotable[8],
         aspecttable[8]);
  for (i = 1; i < 7; i++) {
    printf("  %6.6g - %-6.6g    :  %8d    | %6.6g - %-6.6g     :  %8d\n",
           ratiotable[i - 1], ratiotable[i], aspecttable[i],
           ratiotable[i + 7], ratiotable[i + 8], aspecttable[i + 8]);
  }
  printf("  %6.6g - %-6.6g    :  %8d    | %6.6g -            :  %8d\n",
         ratiotable[6], ratiotable[7], aspecttable[7], ratiotable[14],
         aspecttable[15]);
  printf(
"  (Triangle aspect ratio is longest edge divided by shortest altitude)\n\n");
  printf("  Smallest angle: %15.5g   |  Largest angle: %15.5g\n\n",
         smallestangle, biggestangle);
  printf("  Angle histogram:\n");
  for (i = 0; i < 9; i++) {
    printf("    %3d - %3d degrees:  %8d    |    %3d - %3d degrees:  %8d\n",
           i * 10, i * 10 + 10, angletable[i],
           i * 10 + 90, i * 10 + 100, angletable[i + 9]);
  }
  printf("\n");
}

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned long randomnation ( unsigned int  choices)

Definition at line 5058 of file tlvisTrn_triangle.c.

References randomseed.

Referenced by locate(), pointmedian(), and pointsort().

{
  randomseed = (randomseed * 1366l + 150889l) % 714025l;
  return randomseed / (714025l / choices + 1);
}

Here is the caller graph for this function:

void regionplague ( REAL  attribute,
REAL  area 
)

Definition at line 10323 of file tlvisTrn_triangle.c.

References apex, dest, dummysh, dummytri, infect, infected, org, triedge::orient, poolalloc(), poolrestart(), ptr, regionattrib, setareabound, setelemattribute, edge::sh, sym, traversalinit(), traverse(), triedge::tri, tspivot, uninfect, vararea, verbose, and viri.

Referenced by carveholes().

{
  struct triedge testtri;
  struct triedge neighbor;
  triangle **virusloop;
  triangle **regiontri;
  struct edge neighborshelle;
  point regionorg, regiondest, regionapex;
  triangle ptr;             /* Temporary variable used by sym() and onext(). */
  shelle sptr;                      /* Temporary variable used by tspivot(). */

  if (verbose > 1) {
    printf("  Marking neighbors of marked triangles.\n");
  }
  /* Loop through all the infected triangles, spreading the attribute      */
  /*   and/or area constraint to their neighbors, then to their neighbors' */
  /*   neighbors.                                                          */
  traversalinit(&viri);
  virusloop = (triangle **) traverse(&viri);
  while (virusloop != (triangle **) NULL) {
    testtri.tri = *virusloop;
    /* A triangle is marked as infected by messing with one of its shell */
    /*   edges, setting it to an illegal value.  Hence, we have to       */
    /*   temporarily uninfect this triangle so that we can examine its   */
    /*   adjacent shell edges.                                           */
    uninfect(testtri);
    if (regionattrib) {
      /* Set an attribute. */
      setelemattribute(testtri, eextras, attribute);
    }
    if (vararea) {
      /* Set an area constraint. */
      setareabound(testtri, area);
    }
    if (verbose > 2) {
      /* Assign the triangle an orientation for convenience in */
      /*   checking its points.                                */
      testtri.orient = 0;
      org(testtri, regionorg);
      dest(testtri, regiondest);
      apex(testtri, regionapex);
      printf("    Checking (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
             regionorg[0], regionorg[1], regiondest[0], regiondest[1],
             regionapex[0], regionapex[1]);
    }
    /* Check each of the triangle's three neighbors. */
    for (testtri.orient = 0; testtri.orient < 3; testtri.orient++) {
      /* Find the neighbor. */
      sym(testtri, neighbor);
      /* Check for a shell between the triangle and its neighbor. */
      tspivot(testtri, neighborshelle);
      /* Make sure the neighbor exists, is not already infected, and */
      /*   isn't protected by a shell edge.                          */
      if ((neighbor.tri != dummytri) && !infected(neighbor)
          && (neighborshelle.sh == dummysh)) {
        if (verbose > 2) {
          org(neighbor, regionorg);
          dest(neighbor, regiondest);
          apex(neighbor, regionapex);
          printf("    Marking (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
                 regionorg[0], regionorg[1], regiondest[0], regiondest[1],
                 regionapex[0], regionapex[1]);
        }
        /* Infect the neighbor. */
        infect(neighbor);
        /* Ensure that the neighbor's neighbors will be infected. */
        regiontri = (triangle **) poolalloc(&viri);
        *regiontri = neighbor.tri;
      }
    }
    /* Remark the triangle as infected, so it doesn't get added to the */
    /*   virus pool again.                                             */
    infect(testtri);
    virusloop = (triangle **) traverse(&viri);
  }

  /* Uninfect all triangles. */
  if (verbose > 1) {
    printf("  Unmarking marked triangles.\n");
  }
  traversalinit(&viri);
  virusloop = (triangle **) traverse(&viri);
  while (virusloop != (triangle **) NULL) {
    testtri.tri = *virusloop;
    uninfect(testtri);
    virusloop = (triangle **) traverse(&viri);
  }
  /* Empty the virus pool. */
  poolrestart(&viri);
}

Here is the call graph for this function:

Here is the caller graph for this function:

long removeghosts ( struct triedge startghost)