#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 /* Nothing */ |
| #define | FILENAMESIZE 512 |
| #define | INPUTLINESIZE 512 |
| #define | TRIPERBLOCK 4092 /* Number of triangles allocated at once. */ |
| #define | SHELLEPERBLOCK 508 /* Number of shell edges allocated at once. */ |
| #define | POINTPERBLOCK 4092 /* Number of points allocated at once. */ |
| #define | VIRUSPERBLOCK 1020 /* Number of virus triangles allocated at once. */ |
| #define | BADSEGMENTPERBLOCK 252 |
| #define | BADTRIPERBLOCK 4092 |
| #define | SPLAYNODEPERBLOCK 508 |
| #define | DEADPOINT -1073741824 |
| #define | VOID int |
| #define | SAMPLEFACTOR 11 |
| #define | SAMPLERATE 10 |
| #define | PI 3.141592653589793238462643383279502884197169399375105820974944592308 |
| #define | SQUAREROOTTWO 1.4142135623730950488016887242096980785696718753769480732 |
| #define | ONETHIRD 0.333333333333333333333333333333333333333333333333333333333333 |
| #define | decode(ptr, triedge) |
| #define | encode(triedge) (triangle) ((unsigned long) (triedge).tri | (unsigned long) (triedge).orient) |
| #define | sym(triedge1, triedge2) |
| #define | symself(triedge) |
| #define | lnext(triedge1, triedge2) |
| #define | lnextself(triedge) (triedge).orient = plus1mod3[(triedge).orient] |
| #define | lprev(triedge1, triedge2) |
| #define | lprevself(triedge) (triedge).orient = minus1mod3[(triedge).orient] |
| #define | onext(triedge1, triedge2) |
| #define | onextself(triedge) |
| #define | oprev(triedge1, triedge2) |
| #define | oprevself(triedge) |
| #define | dnext(triedge1, triedge2) |
| #define | dnextself(triedge) |
| #define | dprev(triedge1, triedge2) |
| #define | dprevself(triedge) |
| #define | rnext(triedge1, triedge2) |
| #define | rnextself(triedge) |
| #define | rprev(triedge1, triedge2) |
| #define | rprevself(triedge) |
| #define | org(triedge, pointptr) pointptr = (point) (triedge).tri[plus1mod3[(triedge).orient] + 3] |
| #define | dest(triedge, pointptr) pointptr = (point) (triedge).tri[minus1mod3[(triedge).orient] + 3] |
| #define | apex(triedge, pointptr) pointptr = (point) (triedge).tri[(triedge).orient + 3] |
| #define | setorg(triedge, pointptr) (triedge).tri[plus1mod3[(triedge).orient] + 3] = (triangle) pointptr |
| #define | setdest(triedge, pointptr) (triedge).tri[minus1mod3[(triedge).orient] + 3] = (triangle) pointptr |
| #define | setapex(triedge, pointptr) (triedge).tri[(triedge).orient + 3] = (triangle) pointptr |
| #define | setvertices2null(triedge) |
| #define | bond(triedge1, triedge2) |
| #define | dissolve(triedge) (triedge).tri[(triedge).orient] = (triangle) dummytri |
| #define | triedgecopy(triedge1, triedge2) |
| #define | triedgeequal(triedge1, triedge2) |
| #define | infect(triedge) |
| #define | uninfect(triedge) |
| #define | infected(triedge) (((unsigned long) (triedge).tri[6] & (unsigned long) 2l) != 0) |
| #define | elemattribute(triedge, attnum) ((REAL *) (triedge).tri)[elemattribindex + (attnum)] |
| #define | setelemattribute(triedge, attnum, value) ((REAL *) (triedge).tri)[elemattribindex + (attnum)] = value |
| #define | areabound(triedge) ((REAL *) (triedge).tri)[areaboundindex] |
| #define | setareabound(triedge, value) ((REAL *) (triedge).tri)[areaboundindex] = value |
| #define | sdecode(sptr, edge) |
| #define | sencode(edge) (shelle) ((unsigned long) (edge).sh | (unsigned long) (edge).shorient) |
| #define | ssym(edge1, edge2) |
| #define | ssymself(edge) (edge).shorient = 1 - (edge).shorient |
| #define | spivot(edge1, edge2) |
| #define | spivotself(edge) |
| #define | snext(edge1, edge2) |
| #define | snextself(edge) |
| #define | sorg(edge, pointptr) pointptr = (point) (edge).sh[2 + (edge).shorient] |
| #define | sdest(edge, pointptr) pointptr = (point) (edge).sh[3 - (edge).shorient] |
| #define | setsorg(edge, pointptr) (edge).sh[2 + (edge).shorient] = (shelle) pointptr |
| #define | setsdest(edge, pointptr) (edge).sh[3 - (edge).shorient] = (shelle) pointptr |
| #define | mark(edge) (* (int *) ((edge).sh + 6)) |
| #define | setmark(edge, value) * (int *) ((edge).sh + 6) = value |
| #define | sbond(edge1, edge2) |
| #define | sdissolve(edge) (edge).sh[(edge).shorient] = (shelle) dummysh |
| #define | shellecopy(edge1, edge2) |
| #define | shelleequal(edge1, edge2) |
| #define | tspivot(triedge, edge) |
| #define | stpivot(edge, triedge) |
| #define | tsbond(triedge, edge) |
| #define | tsdissolve(triedge) (triedge).tri[6 + (triedge).orient] = (triangle) dummysh |
| #define | stdissolve(edge) (edge).sh[4 + (edge).shorient] = (shelle) dummytri |
| #define | pointmark(pt) ((int *) (pt))[pointmarkindex] |
| #define | setpointmark(pt, value) ((int *) (pt))[pointmarkindex] = value |
| #define | point2tri(pt) ((triangle *) (pt))[point2triindex] |
| #define | setpoint2tri(pt, value) ((triangle *) (pt))[point2triindex] = value |
| #define | STARTINDEX 0 |
| #define | Absolute(a) ((a) >= 0.0 ? (a) : -(a)) |
| #define | Fast_Two_Sum_Tail(a, b, x, y) |
| #define | Fast_Two_Sum(a, b, x, y) |
| #define | Two_Sum_Tail(a, b, x, y) |
| #define | Two_Sum(a, b, x, y) |
| #define | Two_Diff_Tail(a, b, x, y) |
| #define | Two_Diff(a, b, x, y) |
| #define | Split(a, ahi, alo) |
| #define | Two_Product_Tail(a, b, x, y) |
| #define | Two_Product(a, b, x, y) |
| #define | Two_Product_Presplit(a, b, bhi, blo, x, y) |
| #define | Square_Tail(a, x, y) |
| #define | Square(a, x, y) |
| #define | Two_One_Sum(a1, a0, b, x2, x1, x0) |
| #define | Two_One_Diff(a1, a0, b, x2, x1, x0) |
| #define | Two_Two_Sum(a1, a0, b1, b0, x3, x2, x1, x0) |
| #define | Two_Two_Diff(a1, a0, b1, b0, x3, x2, x1, x0) |
Typedefs | |
| typedef REAL ** | triangle |
| typedef REAL ** | shelle |
| typedef REAL * | point |
Enumerations | |
| enum | wordtype { POINTER, FLOATINGPOINT } |
| enum | locateresult { INTRIANGLE, ONEDGE, ONVERTEX, OUTSIDE } |
| enum | insertsiteresult { SUCCESSFULPOINT, ENCROACHINGPOINT, VIOLATINGPOINT, DUPLICATEPOINT } |
| enum | finddirectionresult { WITHIN, LEFTCOLLINEAR, RIGHTCOLLINEAR } |
| enum | circumcenterresult { OPPOSITEORG, OPPOSITEDEST, OPPOSITEAPEX } |
Functions | |
| void * | 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) |
| triangle * | triangletraverse () |
| void | shelledealloc (shelle *dyingshelle) |
| shelle * | shelletraverse () |
| void | pointdealloc (point dyingpoint) |
| point | pointtraverse () |
| point | getpoint (int number) |
| void | triangledeinit () |
| void | maketriangle (struct triedge *newtriedge) |
| void | makeshelle (struct edge *newedge) |
| void | exactinit () |
| int | fast_expansion_sum_zeroelim (int elen, REAL *e, int flen, REAL *f, REAL *h) |
| int | scale_expansion_zeroelim (int elen, REAL *e, REAL b, REAL *h) |
| REAL | estimate (int elen, REAL *e) |
| REAL | counterclockwiseadapt (point pa, point pb, point pc, REAL detsum) |
| REAL | counterclockwise (point pa, point pb, point pc) |
| REAL | incircleadapt (point pa, point pb, point pc, point pd, REAL permanent) |
| REAL | incircle (point pa, point pb, point pc, point pd) |
| void | triangleinit () |
| unsigned long | randomnation (unsigned int choices) |
| void | makepointmap () |
| enum locateresult | preciselocate (point searchpoint, struct triedge *searchtri) |
| enum locateresult | locate (point searchpoint, struct triedge *searchtri) |
| void | insertshelle (struct triedge *tri, int shellemark) |
| void | flip (struct triedge *flipedge) |
| enum insertsiteresult | insertsite (point insertpoint, struct triedge *searchtri, struct edge *splitedge, int segmentflaws, int triflaws) |
| void | triangulatepolygon (struct triedge *firstedge, struct triedge *lastedge, int edgecount, int doflip, int triflaws) |
| void | pointsort (point *sortarray, int arraysize) |
| void | pointmedian (point *sortarray, int arraysize, int median, int axis) |
| void | alternateaxes (point *sortarray, int arraysize, int axis) |
| void | mergehulls (struct triedge *farleft, struct triedge *innerleft, struct triedge *innerright, struct triedge *farright, int axis) |
| void | divconqrecurse (point *sortarray, int vertices, int axis, struct triedge *farleft, struct triedge *farright) |
| long | removeghosts (struct triedge *startghost) |
| long | divconqdelaunay () |
| long | delaunay () |
| enum finddirectionresult | finddirection (struct triedge *searchtri, point endpoint) |
| void | segmentintersection (struct triedge *splittri, struct edge *splitshelle, point endpoint2) |
| int | scoutsegment (struct triedge *searchtri, point endpoint2, int newmark) |
| void | delaunayfixup (struct triedge *fixuptri, int leftside) |
| void | constrainededge (struct triedge *starttri, point endpoint2, int newmark) |
| void | insertsegment (point endpoint1, point endpoint2, int newmark) |
| void | markhull () |
| int | formskeleton (int *segmentlist, int *segmentmarkerlist, int numberofsegments) |
| void | infecthull () |
| void | plague () |
| void | regionplague (REAL attribute, REAL area) |
| void | carveholes (REAL *holelist, int holes, REAL *regionlist, int regions) |
| enum circumcenterresult | findcircumcenter (point torg, point tdest, point tapex, point circumcenter, REAL *xi, REAL *eta) |
| void | highorder () |
| void | transfernodes (REAL *pointlist, REAL *pointattriblist, int *pointmarkerlist, int numberofpoints, int numberofpointattribs) |
| void | writenodes (REAL **pointlist, REAL **pointattriblist, int **pointmarkerlist) |
| void | numbernodes () |
| void | writeelements (int **trianglelist, REAL **triangleattriblist) |
| void | writepoly (int **segmentlist, int **segmentmarkerlist) |
| void | writeedges (int **edgelist, int **edgemarkerlist) |
| void | writevoronoi (REAL **vpointlist, REAL **vpointattriblist, int **vpointmarkerlist, int **vedgelist, int **vedgemarkerlist, REAL **vnormlist) |
| void | writeneighbors (int **neighborlist) |
| void | quality_statistics () |
| void | statistics () |
| void | triangulate (char *triswitches, struct triangulateio *in, struct triangulateio *out, struct triangulateio *vorout) |
Variables | |
| memorypool | triangles |
| memorypool | shelles |
| memorypool | points |
| memorypool | viri |
| memorypool | badsegments |
| memorypool | badtriangles |
| memorypool | splaynodes |
| badface * | queuefront [64] |
| badface ** | queuetail [64] |
| REAL | xmin |
| REAL | xmax |
| REAL | ymin |
| REAL | ymax |
| REAL | xminextreme |
| int | inpoints |
| int | inelements |
| int | insegments |
| int | holes |
| int | regions |
| long | edges |
| int | mesh_dim |
| int | nextras |
| int | eextras |
| long | hullsize |
| int | triwords |
| int | shwords |
| int | pointmarkindex |
| int | point2triindex |
| int | highorderindex |
| int | elemattribindex |
| int | areaboundindex |
| int | checksegments |
| int | readnodefile |
| long | samples |
| unsigned long | randomseed |
| REAL | splitter |
| REAL | epsilon |
| REAL | resulterrbound |
| REAL | ccwerrboundA |
| REAL | ccwerrboundB |
| REAL | ccwerrboundC |
| REAL | iccerrboundA |
| REAL | iccerrboundB |
| REAL | iccerrboundC |
| long | incirclecount |
| long | counterclockcount |
| long | hyperbolacount |
| long | circumcentercount |
| long | circletopcount |
| int | poly |
| int | refine |
| int | quality |
| int | vararea |
| int | fixedarea |
| int | regionattrib |
| int | convex |
| int | firstnumber |
| int | edgesout |
| int | voronoi |
| int | neighbors |
| int | geomview |
| int | nobound |
| int | nopolywritten |
| int | nonodewritten |
| int | noelewritten |
| int | noiterationnum |
| int | noholes |
| int | noexact |
| int | incremental |
| int | sweepline |
| int | dwyer |
| int | splitseg |
| int | docheck |
| int | quiet |
| int | verbose |
| int | useshelles |
| int | order |
| int | nobisect |
| int | steiner |
| int | steinerleft |
| REAL | minangle |
| REAL | goodangle |
| REAL | maxarea |
| point | infpoint1 |
| point | infpoint2 |
| point | infpoint3 |
| triangle * | dummytri |
| triangle * | dummytribase |
| shelle * | dummysh |
| shelle * | dummyshbase |
| triedge | recenttri |
| int | plus1mod3 [3] = {1, 2, 0} |
| int | minus1mod3 [3] = {2, 0, 1} |
|
|
* Definition at line 3904 of file tlvisTrn_triangle.c. Referenced by counterclockwiseadapt(), incircle(), and incircleadapt(). |
|
|
Definition at line 924 of file tlvisTrn_triangle.c. Referenced by insertsite(), mergehulls(), triangulatepolygon(), writeelements(), and writevoronoi(). |
|
|
Definition at line 993 of file tlvisTrn_triangle.c. Referenced by insertsite(). |
|
|
Definition at line 269 of file tlvisTrn_triangle.c. |
|
|
Definition at line 271 of file tlvisTrn_triangle.c. |
|
|
Value: (triedge1).tri[(triedge1).orient] = encode(triedge2); \ (triedge2).tri[(triedge2).orient] = encode(triedge1) Definition at line 943 of file tlvisTrn_triangle.c. Referenced by divconqrecurse(), insertsite(), and mergehulls(). |
|
|
Definition at line 232 of file tlvisTrn_triangle.c. |
|
|
Definition at line 279 of file tlvisTrn_triangle.c. |
|
|
Value: (triedge).orient = (int) ((unsigned long) (ptr) & (unsigned long) 3l); \ (triedge).tri = (triangle *) \ ((unsigned long) (ptr) ^ (unsigned long) (triedge).orient) Definition at line 793 of file tlvisTrn_triangle.c. |
|
|
Definition at line 921 of file tlvisTrn_triangle.c. Referenced by carveholes(), insertsite(), mergehulls(), triangulatepolygon(), writeedges(), writeelements(), and writevoronoi(). |
|
|
Definition at line 952 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 867 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 871 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 879 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 883 of file tlvisTrn_triangle.c. |
|
|
Definition at line 985 of file tlvisTrn_triangle.c. Referenced by insertsite(), and writeelements(). |
|
|
Definition at line 802 of file tlvisTrn_triangle.c. |
|
|
Value: x = (REAL) (a + b); \ Fast_Two_Sum_Tail(a, b, x, y) Definition at line 3924 of file tlvisTrn_triangle.c. Referenced by fast_expansion_sum_zeroelim(), and scale_expansion_zeroelim(). |
|
|
Value: bvirt = x - a; \ y = b - bvirt Definition at line 3920 of file tlvisTrn_triangle.c. |
|
|
Definition at line 249 of file tlvisTrn_triangle.c. Referenced by parsecommandline(). |
|
|
Definition at line 243 of file tlvisTrn_triangle.c. Referenced by counterclockwiseadapt(), fast_expansion_sum_zeroelim(), incircleadapt(), and scale_expansion_zeroelim(). |
|
|
Value: Definition at line 970 of file tlvisTrn_triangle.c. Referenced by carveholes(). |
|
|
Definition at line 980 of file tlvisTrn_triangle.c. Referenced by carveholes(). |
|
|
Definition at line 254 of file tlvisTrn_triangle.c. Referenced by formskeleton(). |
|
|
Value: (triedge2).tri = (triedge1).tri; \ (triedge2).orient = plus1mod3[(triedge1).orient] Definition at line 823 of file tlvisTrn_triangle.c. Referenced by divconqrecurse(), insertsite(), and mergehulls(). |
|
|
Definition at line 827 of file tlvisTrn_triangle.c. Referenced by divconqrecurse(), insertsite(), and mergehulls(). |
|
|
Value: (triedge2).tri = (triedge1).tri; \ (triedge2).orient = minus1mod3[(triedge1).orient] Definition at line 832 of file tlvisTrn_triangle.c. Referenced by divconqrecurse(), insertsite(), and mergehulls(). |
|
|
Definition at line 836 of file tlvisTrn_triangle.c. Referenced by divconqrecurse(), insertsite(), and mergehulls(). |
|
|
Definition at line 1068 of file tlvisTrn_triangle.c. Referenced by insertsite(), printshelle(), textsw_print(), textsw_print_sw(), writeedges(), and writepoly(). |
|
|
Definition at line 206 of file tlvisTrn_triangle.c. |
|
|
Definition at line 308 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 843 of file tlvisTrn_triangle.c. Referenced by triangulatepolygon(). |
|
|
Value: Definition at line 847 of file tlvisTrn_triangle.c. Referenced by triangulatepolygon(). |
|
|
Value: Definition at line 855 of file tlvisTrn_triangle.c. Referenced by triangulatepolygon(). |
|
|
Value: Definition at line 859 of file tlvisTrn_triangle.c. |
|
|
Definition at line 918 of file tlvisTrn_triangle.c. Referenced by carveholes(), insertsite(), mergehulls(), writeedges(), writeelements(), and writevoronoi(). |
|
|
Definition at line 300 of file tlvisTrn_triangle.c. Referenced by ang_d(), ang_d2(), disp_init(), init_dparams(), invert_2d_proc(), invert_3d_proc(), l_prop(), nmr_gaus_tri(), quality_statistics(), raxis_show(), sellipse_subpix_proc(), tv_zbuff_quadric(), and tv_zbuff_sphere(). |
|
|
Definition at line 1139 of file tlvisTrn_triangle.c. |
|
|
Definition at line 1134 of file tlvisTrn_triangle.c. Referenced by writeedges(), writeelements(), writenodes(), and writepoly(). |
|
|
Definition at line 264 of file tlvisTrn_triangle.c. |
|
|
Definition at line 200 of file tlvisTrn_triangle.c. |
|
|
Definition at line 231 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 891 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 896 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 905 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 910 of file tlvisTrn_triangle.c. |
|
|
Definition at line 292 of file tlvisTrn_triangle.c. |
|
|
Definition at line 296 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 1075 of file tlvisTrn_triangle.c. Referenced by insertsite(). |
|
|
Value: (edge).shorient = (int) ((unsigned long) (sptr) & (unsigned long) 1l); \ (edge).sh = (shelle *) \ ((unsigned long) (sptr) & ~ (unsigned long) 3l) Definition at line 1007 of file tlvisTrn_triangle.c. |
|
|
Definition at line 1056 of file tlvisTrn_triangle.c. Referenced by writepoly(). |
|
|
Definition at line 1082 of file tlvisTrn_triangle.c. |
|
|
Definition at line 1016 of file tlvisTrn_triangle.c. |
|
|
Definition at line 933 of file tlvisTrn_triangle.c. Referenced by divconqrecurse(), insertsite(), and mergehulls(). |
|
|
Definition at line 995 of file tlvisTrn_triangle.c. Referenced by insertsite(). |
|
|
Definition at line 930 of file tlvisTrn_triangle.c. Referenced by divconqrecurse(), insertsite(), and mergehulls(). |
|
|
Definition at line 988 of file tlvisTrn_triangle.c. Referenced by carveholes(), and insertsite(). |
|
|
Definition at line 1070 of file tlvisTrn_triangle.c. |
|
|
Definition at line 927 of file tlvisTrn_triangle.c. Referenced by divconqrecurse(), insertsite(), and mergehulls(). |
|
|
Definition at line 1141 of file tlvisTrn_triangle.c. |
|
|
Definition at line 1136 of file tlvisTrn_triangle.c. Referenced by transfernodes(), and writenodes(). |
|
|
Definition at line 1062 of file tlvisTrn_triangle.c. Referenced by insertsite(). |
|
|
Definition at line 1059 of file tlvisTrn_triangle.c. |
|
|
Value: (triedge).tri[3] = (triangle) NULL; \ (triedge).tri[4] = (triangle) NULL; \ (triedge).tri[5] = (triangle) NULL; Definition at line 936 of file tlvisTrn_triangle.c. |
|
|
Value: (edge2).sh = (edge1).sh; \ (edge2).shorient = (edge1).shorient Definition at line 1087 of file tlvisTrn_triangle.c. Referenced by insertsite(). |
|
|
Value: (((edge1).sh == (edge2).sh) && \ ((edge1).shorient == (edge2).shorient)) Definition at line 1093 of file tlvisTrn_triangle.c. |
|
|
Definition at line 262 of file tlvisTrn_triangle.c. |
|
|
Value: sptr = (edge1).sh[1 - (edge1).shorient]; \ sdecode(sptr, edge2) Definition at line 1042 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 1046 of file tlvisTrn_triangle.c. |
|
|
Definition at line 1053 of file tlvisTrn_triangle.c. Referenced by writepoly(). |
|
|
Value: sptr = (edge1).sh[(edge1).shorient]; \ sdecode(sptr, edge2) Definition at line 1031 of file tlvisTrn_triangle.c. Referenced by insertsite(). |
|
|
Value: Definition at line 1035 of file tlvisTrn_triangle.c. |
|
|
Definition at line 273 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 3950 of file tlvisTrn_triangle.c. Referenced by scale_expansion_zeroelim(). |
|
|
Value: x = (REAL) (a * a); \ Square_Tail(a, x, y) Definition at line 3987 of file tlvisTrn_triangle.c. Referenced by incircleadapt(). |
|
|
Value: Split(a, ahi, alo); \ err1 = x - (ahi * ahi); \ err3 = err1 - ((ahi + ahi) * alo); \ y = (alo * alo) - err3 Definition at line 3981 of file tlvisTrn_triangle.c. |
|
|
Definition at line 304 of file tlvisTrn_triangle.c. |
|
|
Value: (edge2).sh = (edge1).sh; \ (edge2).shorient = 1 - (edge1).shorient Definition at line 1021 of file tlvisTrn_triangle.c. |
|
|
Definition at line 1025 of file tlvisTrn_triangle.c. Referenced by insertsite(). |
|
|
Referenced by parsecommandline(). |
|
|
Definition at line 1127 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 1110 of file tlvisTrn_triangle.c. |
|
|
Value: ptr = (triedge1).tri[(triedge1).orient]; \ decode(ptr, triedge2); Definition at line 813 of file tlvisTrn_triangle.c. Referenced by insertsite(), mergehulls(), triangulatepolygon(), writeedges(), writeneighbors(), and writevoronoi(). |
|
|
Value: Definition at line 817 of file tlvisTrn_triangle.c. Referenced by carveholes(), insertsite(), and mergehulls(). |
|
|
Value: (triedge2).tri = (triedge1).tri; \ (triedge2).orient = (triedge1).orient Definition at line 957 of file tlvisTrn_triangle.c. Referenced by carveholes(), divconqrecurse(), insertsite(), mergehulls(), and triangulatepolygon(). |
|
|
Value: (((triedge1).tri == (triedge2).tri) && \ ((triedge1).orient == (triedge2).orient)) Definition at line 963 of file tlvisTrn_triangle.c. |
|
|
Definition at line 220 of file tlvisTrn_triangle.c. |
|
|
Definition at line 260 of file tlvisTrn_triangle.c. |
|
|
Value: (triedge).tri[6 + (triedge).orient] = (triangle) sencode(edge); \ (edge).sh[4 + (edge).shorient] = (shelle) encode(triedge) Definition at line 1116 of file tlvisTrn_triangle.c. Referenced by insertsite(). |
|
|
Definition at line 1122 of file tlvisTrn_triangle.c. Referenced by insertsite(). |
|
|
Value: Definition at line 1103 of file tlvisTrn_triangle.c. Referenced by insertsite(), and writeedges(). |
|
|
Value: x = (REAL) (a - b); \ Two_Diff_Tail(a, b, x, y) Definition at line 3946 of file tlvisTrn_triangle.c. |
|
|
Value: bvirt = (REAL) (a - x); \ avirt = x + bvirt; \ bround = bvirt - b; \ around = a - avirt; \ y = around + bround Definition at line 3939 of file tlvisTrn_triangle.c. Referenced by counterclockwiseadapt(), and incircleadapt(). |
|
|
Value: Definition at line 3998 of file tlvisTrn_triangle.c. |
|
|
Value: Definition at line 3994 of file tlvisTrn_triangle.c. |
|
|
Value: x = (REAL) (a * b); \ Two_Product_Tail(a, b, x, y) Definition at line 3964 of file tlvisTrn_triangle.c. Referenced by counterclockwiseadapt(), and incircleadapt(). |
|
|
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 3971 of file tlvisTrn_triangle.c. Referenced by scale_expansion_zeroelim(). |
|
|
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 3956 of file tlvisTrn_triangle.c. |
|
|
Value: x = (REAL) (a + b); \ Two_Sum_Tail(a, b, x, y) Definition at line 3935 of file tlvisTrn_triangle.c. Referenced by fast_expansion_sum_zeroelim(), and scale_expansion_zeroelim(). |
|
|
Value: bvirt = (REAL) (x - a); \ avirt = x - bvirt; \ bround = b - bvirt; \ around = a - avirt; \ y = around + bround Definition at line 3928 of file tlvisTrn_triangle.c. |
|
|
Value: Two_One_Diff(a1, a0, b0, _j, _0, x0); \ Two_One_Diff(_j, _0, b1, x3, x2, x1) Definition at line 4006 of file tlvisTrn_triangle.c. Referenced by counterclockwiseadapt(), and incircleadapt(). |
|
|
Value: Two_One_Sum(a1, a0, b0, _j, _0, x0); \ Two_One_Sum(_j, _0, b1, x3, x2, x1) Definition at line 4002 of file tlvisTrn_triangle.c. Referenced by incircleadapt(). |
|
|
Value: Definition at line 974 of file tlvisTrn_triangle.c. |
|
|
Definition at line 266 of file tlvisTrn_triangle.c. Referenced by carveholes(). |
|
|
Definition at line 285 of file tlvisTrn_triangle.c. Referenced by getpoint(), poolalloc(), pooldealloc(), poolinit(), poolrestart(), traversalinit(), and traverse(). |
|
|
|
Definition at line 503 of file tlvisTrn_triangle.c. Referenced by constrainededge(), delaunayfixup(), flip(), highorder(), infecthull(), insertshelle(), insertsite(), makeshelle(), plague(), regionplague(), scoutsegment(), shelledealloc(), shelletraverse(), writeedges(), and writepoly(). |
|
|
|
Definition at line 371 of file tlvisTrn_triangle.c.
|
|
|
Definition at line 366 of file tlvisTrn_triangle.c. Referenced by scoutsegment(), and segmentintersection().
00366 {OPPOSITEORG, OPPOSITEDEST, OPPOSITEAPEX};
|
|
|
Definition at line 358 of file tlvisTrn_triangle.c. Referenced by insertsite(), and segmentintersection().
00361 {WITHIN, LEFTCOLLINEAR, RIGHTCOLLINEAR};
|
|
|
Definition at line 351 of file tlvisTrn_triangle.c. Referenced by carveholes(), and insertsite().
00353 {SUCCESSFULPOINT, ENCROACHINGPOINT, VIOLATINGPOINT,
|
|
|
Definition at line 345 of file tlvisTrn_triangle.c.
00346 {INTRIANGLE, ONEDGE, ONVERTEX, OUTSIDE};
|
|
||||||||||||||||
|
Definition at line 7108 of file tlvisTrn_triangle.c.
07111 {
07112 /* Recursive base case: subsets of two or three points will be */
07113 /* handled specially, and should always be sorted by x-coordinate. */
07114 axis = 0;
07115 }
07116 /* Partition with a horizontal or vertical cut. */
07117 pointmedian(sortarray, arraysize, divider, axis);
07118 /* Recursively partition the subsets with a cross cut. */
07119 if (arraysize - divider >= 2) {
07120 if (divider >= 2) {
07121 alternateaxes(sortarray, divider, 1 - axis);
07122 }
07123 alternateaxes(&sortarray[divider], arraysize - divider, 1 - axis);
07124 }
07125 }
07126
07127 /*****************************************************************************/
07128 /* */
07129 /* mergehulls() Merge two adjacent Delaunay triangulations into a */
07130 /* single Delaunay triangulation. */
|
|
||||||||||||||||||||
|
Definition at line 10433 of file tlvisTrn_triangle.c. References convex, counterclockwise(), dest, dummytri, eextras, exit(), free(), holes, infect, infected, infecthull(), memorypool::items, locate(), locateresult, malloc(), noholes, org, triedge::orient, OUTSIDE, plague(), point, POINTER, poolalloc(), pooldeinit(), poolinit(), quiet, refine, regionattrib, regionplague(), regions, setelemattribute, symself, traversalinit(), triedge::tri, triangle, triangles, triangletraverse(), triedgecopy, vararea, verbose, viri, and VIRUSPERBLOCK. Referenced by triangulate().
10433 {
10434 struct triedge searchtri;
10435 struct triedge triangleloop;
10436 struct triedge *regiontris;
10437 triangle **holetri;
10438 triangle **regiontri;
10439 point searchorg, searchdest;
10440 enum locateresult intersect;
10441 int i;
10442 triangle ptr; /* Temporary variable used by sym(). */
10443
10444 if (!(quiet || (noholes && convex))) {
10445 printf("Removing unwanted triangles.\n");
10446 if (verbose && (holes > 0)) {
10447 printf(" Marking holes for elimination.\n");
10448 }
10449 }
10450
10451 if (regions > 0) {
10452 /* Allocate storage for the triangles in which region points fall. */
10453 regiontris = (struct triedge *) malloc(regions * sizeof(struct triedge));
10454 if (regiontris == (struct triedge *) NULL) {
10455 printf("Error: Out of memory.\n");
10456 exit(1);
10457 }
10458 }
10459
10460 if (((holes > 0) && !noholes) || !convex || (regions > 0)) {
10461 /* Initialize a pool of viri to be used for holes, concavities, */
10462 /* regional attributes, and/or regional area constraints. */
10463 poolinit(&viri, sizeof(triangle *), VIRUSPERBLOCK, POINTER, 0);
10464 }
10465
10466 if (!convex) {
10467 /* Mark as infected any unprotected triangles on the boundary. */
10468 /* This is one way by which concavities are created. */
10469 infecthull();
10470 }
10471
10472 if ((holes > 0) && !noholes) {
10473 /* Infect each triangle in which a hole lies. */
10474 for (i = 0; i < 2 * holes; i += 2) {
10475 /* Ignore holes that aren't within the bounds of the mesh. */
10476 if ((holelist[i] >= xmin) && (holelist[i] <= xmax)
10477 && (holelist[i + 1] >= ymin) && (holelist[i + 1] <= ymax)) {
10478 /* Start searching from some triangle on the outer boundary. */
10479 searchtri.tri = dummytri;
10480 searchtri.orient = 0;
10481 symself(searchtri);
10482 /* Ensure that the hole is to the left of this boundary edge; */
10483 /* otherwise, locate() will falsely report that the hole */
10484 /* falls within the starting triangle. */
10485 org(searchtri, searchorg);
10486 dest(searchtri, searchdest);
10487 if (counterclockwise(searchorg, searchdest, &holelist[i]) > 0.0) {
10488 /* Find a triangle that contains the hole. */
10489 intersect = locate(&holelist[i], &searchtri);
10490 if ((intersect != OUTSIDE) && (!infected(searchtri))) {
10491 /* Infect the triangle. This is done by marking the triangle */
10492 /* as infect and including the triangle in the virus pool. */
10493 infect(searchtri);
10494 holetri = (triangle **) poolalloc(&viri);
10495 *holetri = searchtri.tri;
10496 }
10497 }
10498 }
10499 }
10500 }
10501
10502 /* Now, we have to find all the regions BEFORE we carve the holes, because */
10503 /* locate() won't work when the triangulation is no longer convex. */
10504 /* (Incidentally, this is the reason why regional attributes and area */
10505 /* constraints can't be used when refining a preexisting mesh, which */
10506 /* might not be convex; they can only be used with a freshly */
10507 /* triangulated PSLG.) */
10508 if (regions > 0) {
10509 /* Find the starting triangle for each region. */
10510 for (i = 0; i < regions; i++) {
10511 regiontris[i].tri = dummytri;
10512 /* Ignore region points that aren't within the bounds of the mesh. */
10513 if ((regionlist[4 * i] >= xmin) && (regionlist[4 * i] <= xmax) &&
10514 (regionlist[4 * i + 1] >= ymin) && (regionlist[4 * i + 1] <= ymax)) {
10515 /* Start searching from some triangle on the outer boundary. */
10516 searchtri.tri = dummytri;
10517 searchtri.orient = 0;
10518 symself(searchtri);
10519 /* Ensure that the region point is to the left of this boundary */
10520 /* edge; otherwise, locate() will falsely report that the */
10521 /* region point falls within the starting triangle. */
10522 org(searchtri, searchorg);
10523 dest(searchtri, searchdest);
10524 if (counterclockwise(searchorg, searchdest, ®ionlist[4 * i]) >
10525 0.0) {
10526 /* Find a triangle that contains the region point. */
10527 intersect = locate(®ionlist[4 * i], &searchtri);
10528 if ((intersect != OUTSIDE) && (!infected(searchtri))) {
10529 /* Record the triangle for processing after the */
10530 /* holes have been carved. */
10531 triedgecopy(searchtri, regiontris[i]);
10532 }
10533 }
10534 }
10535 }
10536 }
10537
10538 if (viri.items > 0) {
10539 /* Carve the holes and concavities. */
10540 plague();
10541 }
10542 /* The virus pool should be empty now. */
10543
10544 if (regions > 0) {
10545 if (!quiet) {
10546 if (regionattrib) {
10547 if (vararea) {
10548 printf("Spreading regional attributes and area constraints.\n");
10549 } else {
10550 printf("Spreading regional attributes.\n");
10551 }
10552 } else {
10553 printf("Spreading regional area constraints.\n");
10554 }
10555 }
10556 if (regionattrib && !refine) {
10557 /* Assign every triangle a regional attribute of zero. */
10558 traversalinit(&triangles);
10559 triangleloop.orient = 0;
10560 triangleloop.tri = triangletraverse();
10561 while (triangleloop.tri != (triangle *) NULL) {
10562 setelemattribute(triangleloop, eextras, 0.0);
10563 triangleloop.tri = triangletraverse();
10564 }
10565 }
10566 for (i = 0; i < regions; i++) {
10567 if (regiontris[i].tri != dummytri) {
10568 /* Make sure the triangle under consideration still exists. */
10569 /* It may have been eaten by the virus. */
10570 if (regiontris[i].tri[3] != (triangle) NULL) {
10571 /* Put one triangle in the virus pool. */
10572 infect(regiontris[i]);
10573 regiontri = (triangle **) poolalloc(&viri);
10574 *regiontri = regiontris[i].tri;
10575 /* Apply one region's attribute and/or area constraint. */
10576 regionplague(regionlist[4 * i + 2], regionlist[4 * i + 3]);
10577 /* The virus pool should be empty now. */
10578 }
10579 }
10580 }
10581 if (regionattrib && !refine) {
10582 /* Note the fact that each triangle has an additional attribute. */
10583 eextras++;
10584 }
10585 }
10586
10587 /* Free up memory. */
10588 if (((holes > 0) && !noholes) || !convex || (regions > 0)) {
10589 pooldeinit(&viri);
10590 }
10591 if (regions > 0) {
10592 free(regiontris);
10593 }
10594 }
10595
10598 /********* Carving out holes and concavities ends here *********/
10599
|
Here is the call graph for this function:
|
||||||||||||||||
|
Definition at line 9671 of file tlvisTrn_triangle.c. References point, REAL, shelle, and triangle.
09688 {
09689 org(fixuptri, farpoint);
09690 /* `farpoint' is the extreme point of the polygon we are "digging" */
09691 /* to get from endpoint1 to endpoint2. */
09692 if ((farpoint[0] == endpoint2[0]) && (farpoint[1] == endpoint2[1])) {
09693 oprev(fixuptri, fixuptri2);
09694 /* Enforce the Delaunay condition around endpoint2. */
09695 delaunayfixup(&fixuptri, 0);
09696 delaunayfixup(&fixuptri2, 1);
09697 done = 1;
09698 } else {
09699 /* Check whether farpoint is to the left or right of the segment */
09700 /* being inserted, to decide which edge of fixuptri to dig */
09701 /* through next. */
09702 area = counterclockwise(endpoint1, endpoint2, farpoint);
09703 if (area == 0.0) {
09704 /* We've collided with a point between endpoint1 and endpoint2. */
09705 collision = 1;
09706 oprev(fixuptri, fixuptri2);
09707 /* Enforce the Delaunay condition around farpoint. */
09708 delaunayfixup(&fixuptri, 0);
09709 delaunayfixup(&fixuptri2, 1);
09710 done = 1;
09711 } else {
09712 if (area > 0.0) { /* farpoint is to the left of the segment. */
09713 oprev(fixuptri, fixuptri2);
09714 /* Enforce the Delaunay condition around farpoint, on the */
09715 /* left side of the segment only. */
09716 delaunayfixup(&fixuptri2, 1);
09717 /* Flip the edge that crosses the segment. After the edge is */
09718 /* flipped, one of its endpoints is the fan vertex, and the */
09719 /* destination of fixuptri is the fan vertex. */
09720 lprevself(fixuptri);
09721 } else { /* farpoint is to the right of the segment. */
09722 delaunayfixup(&fixuptri, 0);
09723 /* Flip the edge that crosses the segment. After the edge is */
09724 /* flipped, one of its endpoints is the fan vertex, and the */
09725 /* destination of fixuptri is the fan vertex. */
09726 oprevself(fixuptri);
09727 }
09728 /* Check for two intersecting segments. */
09729 tspivot(fixuptri, fixupedge);
09730 if (fixupedge.sh == dummysh) {
09731 flip(&fixuptri); /* May create an inverted triangle on the left. */
09732 } else {
09733 /* We've collided with a segment between endpoint1 and endpoint2. */
09734 collision = 1;
09735 /* Insert a point at the intersection. */
09736 segmentintersection(&fixuptri, &fixupedge, endpoint2);
09737 done = 1;
09738 }
09739 }
09740 }
09741 } while (!done);
09742 /* Insert a shell edge to make the segment permanent. */
09743 insertshelle(&fixuptri, newmark);
09744 /* If there was a collision with an interceding vertex, install another */
09745 /* segment connecting that vertex with endpoint2. */
09746 if (collision) {
09747 /* Insert the remainder of the segment. */
09748 if (!scoutsegment(&fixuptri, endpoint2, newmark)) {
09749 constrainededge(&fixuptri, endpoint2, newmark);
09750 }
09751 }
09752 }
09753
09754 /*****************************************************************************/
09755 /* */
09756 /* insertsegment() Insert a PSLG segment into a triangulation. */
09757 /* */
|
|
||||||||||||||||
|
Definition at line 4340 of file tlvisTrn_triangle.c. References counterclockcount, noexact, and REAL. Referenced by carveholes(), divconqrecurse(), findcircumcenter(), insertsite(), and mergehulls().
04349 {
04350 return det;
04351 }
04352
04353 if (detleft > 0.0) {
04354 if (detright <= 0.0) {
04355 return det;
04356 } else {
04357 detsum = detleft + detright;
04358 }
04359 } else if (detleft < 0.0) {
04360 if (detright >= 0.0) {
04361 return det;
04362 } else {
04363 detsum = -detleft - detright;
04364 }
04365 } else {
04366 return det;
04367 }
04368
04369 errbound = ccwerrboundA * detsum;
04370 if ((det >= errbound) || (-det >= errbound)) {
04371 return det;
04372 }
04373
04374 return counterclockwiseadapt(pa, pb, pc, detsum);
04375 }
04376
04377 /*****************************************************************************/
04378 /* */
04379 /* incircle() Return a positive value if the point pd lies inside the */
04380 /* circle passing through pa, pb, and pc; a negative value if */
|
|
||||||||||||||||||||
|
Definition at line 4256 of file tlvisTrn_triangle.c. References Absolute, ccwerrboundB, ccwerrboundC, estimate(), fast_expansion_sum_zeroelim(), INEXACT, REAL, resulterrbound, Two_Diff_Tail, Two_Product, and Two_Two_Diff.
04256 {
04257 INEXACT REAL acx, acy, bcx, bcy;
04258 REAL acxtail, acytail, bcxtail, bcytail;
04259 INEXACT REAL detleft, detright;
04260 REAL detlefttail, detrighttail;
04261 REAL det, errbound;
04262 REAL B[4], C1[8], C2[12], D[16];
04263 INEXACT REAL B3;
04264 int C1length, C2length, Dlength;
04265 REAL u[4];
04266 INEXACT REAL u3;
04267 INEXACT REAL s1, t1;
04268 REAL s0, t0;
04269
04270 INEXACT REAL bvirt;
04271 REAL avirt, bround, around;
04272 INEXACT REAL c;
04273 INEXACT REAL abig;
04274 REAL ahi, alo, bhi, blo;
04275 REAL err1, err2, err3;
04276 INEXACT REAL _i, _j;
04277 REAL _0;
04278
04279 acx = (REAL) (pa[0] - pc[0]);
04280 bcx = (REAL) (pb[0] - pc[0]);
04281 acy = (REAL) (pa[1] - pc[1]);
04282 bcy = (REAL) (pb[1] - pc[1]);
04283
04284 Two_Product(acx, bcy, detleft, detlefttail);
04285 Two_Product(acy, bcx, detright, detrighttail);
04286
04287 Two_Two_Diff(detleft, detlefttail, detright, detrighttail,
04288 B3, B[2], B[1], B[0]);
04289 B[3] = B3;
04290
04291 det = estimate(4, B);
04292 errbound = ccwerrboundB * detsum;
04293 if ((det >= errbound) || (-det >= errbound)) {
04294 return det;
04295 }
04296
04297 Two_Diff_Tail(pa[0], pc[0], acx, acxtail);
04298 Two_Diff_Tail(pb[0], pc[0], bcx, bcxtail);
04299 Two_Diff_Tail(pa[1], pc[1], acy, acytail);
04300 Two_Diff_Tail(pb[1], pc[1], bcy, bcytail);
04301
04302 if ((acxtail == 0.0) && (acytail == 0.0)
04303 && (bcxtail == 0.0) && (bcytail == 0.0)) {
04304 return det;
04305 }
04306
04307 errbound = ccwerrboundC * detsum + resulterrbound * Absolute(det);
04308 det += (acx * bcytail + bcy * acxtail)
04309 - (acy * bcxtail + bcx * acytail);
04310 if ((det >= errbound) || (-det >= errbound)) {
04311 return det;
04312 }
04313
04314 Two_Product(acxtail, bcy, s1, s0);
04315 Two_Product(acytail, bcx, t1, t0);
04316 Two_Two_Diff(s1, s0, t1, t0, u3, u[2], u[1], u[0]);
04317 u[3] = u3;
04318 C1length = fast_expansion_sum_zeroelim(4, B, 4, u, C1);
04319
04320 Two_Product(acx, bcytail, s1, s0);
04321 Two_Product(acy, bcxtail, t1, t0);
04322 Two_Two_Diff(s1, s0, t1, t0, u3, u[2], u[1], u[0]);
04323 u[3] = u3;
04324 C2length = fast_expansion_sum_zeroelim(C1length, C1, 4, u, C2);
04325
04326 Two_Product(acxtail, bcytail, s1, s0);
04327 Two_Product(acytail, bcxtail, t1, t0);
04328 Two_Two_Diff(s1, s0, t1, t0, u3, u[2], u[1], u[0]);
04329 u[3] = u3;
04330 Dlength = fast_expansion_sum_zeroelim(C2length, C2, 4, u, D);
04331
04332 return(D[Dlength - 1]);
04333 }
04334
04335 REAL counterclockwise(pa, pb, pc)
04336 point pa;
04337 point pb;
04338 point pc;
|
Here is the call graph for this function:
|
|
* Definition at line 8637 of file tlvisTrn_triangle.c. References quiet. Referenced by triangulate().
08638 {
08639 printf(
08640 "Constructing Delaunay triangulation by divide-and-conquer method.\n");
08641 }
08642 return divconqdelaunay();
08643 #else /* not REDUCED */
08644 if (!quiet) {
08645 printf("Constructing Delaunay triangulation ");
08646 if (incremental) {
08647 printf("by incremental method.\n");
08648 } else if (sweepline) {
08649 printf("by sweepline method.\n");
08650 } else {
08651 printf("by divide-and-conquer method.\n");
08652 }
08653 }
08654 if (incremental) {
08655 return incrementaldelaunay();
08656 } else if (sweepline) {
08657 return sweeplinedelaunay();
08658 } else {
08659 return divconqdelaunay();
08660 }
08661 #endif /* not REDUCED */
08662 }
08663
08664 /*****************************************************************************/
08665 /* */
08666 /* reconstruct() Reconstruct a triangulation from its .ele (and possibly */
08667 /* .poly) file. Used when the -r switch is used. */
|
|
||||||||||||
|
Definition at line 9560 of file tlvisTrn_triangle.c. References dummytri, point, shelle, and triangle.
09569 {
09570 return;
09571 }
09572 tspivot(neartri, faredge);
09573 if (faredge.sh != dummysh) {
09574 return;
09575 }
09576 /* Find all the relevant vertices. */
09577 apex(neartri, nearpoint);
09578 org(neartri, leftpoint);
09579 dest(neartri, rightpoint);
09580 apex(fartri, farpoint);
09581 /* Check whether the previous polygon vertex is a reflex vertex. */
09582 if (leftside) {
09583 if (counterclockwise(nearpoint, leftpoint, farpoint) <= 0.0) {
09584 /* leftpoint is a reflex vertex too. Nothing can */
09585 /* be done until a convex section is found. */
09586 return;
09587 }
09588 } else {
09589 if (counterclockwise(farpoint, rightpoint, nearpoint) <= 0.0) {
09590 /* rightpoint is a reflex vertex too. Nothing can */
09591 /* be done until a convex section is found. */
09592 return;
09593 }
09594 }
09595 if (counterclockwise(rightpoint, leftpoint, farpoint) > 0.0) {
09596 /* fartri is not an inverted triangle, and farpoint is not a reflex */
09597 /* vertex. As there are no reflex vertices, fixuptri isn't an */
09598 /* inverted triangle, either. Hence, test the edge between the */
09599 /* triangles to ensure it is locally Delaunay. */
09600 if (incircle(leftpoint, farpoint, rightpoint, nearpoint) <= 0.0) {
09601 return;
09602 }
09603 /* Not locally Delaunay; go on to an edge flip. */
09604 } /* else fartri is inverted; remove it from the stack by flipping. */
09605 flip(&neartri);
09606 lprevself(*fixuptri); /* Restore the origin of fixuptri after the flip. */
09607 /* Recursively process the two triangles that result from the flip. */
09608 delaunayfixup(fixuptri, leftside);
09609 delaunayfixup(&fartri, leftside);
09610 }
09611
09612 /*****************************************************************************/
09613 /* */
09614 /* constrainededge() Force a segment into a constrained Delaunay */
09615 /* triangulation by deleting the triangles it */
|
|
|
Definition at line 7688 of file tlvisTrn_triangle.c. References point.
07692 {
07693 printf("Error: Out of memory.\n");
07694 exit(1);
07695 }
07696 traversalinit(&points);
07697 for (i = 0; i < inpoints; i++) {
07698 sortarray[i] = pointtraverse();
07699 }
07700 if (verbose) {
07701 printf(" Sorting points.\n");
07702 }
07703 /* Sort the points. */
07704 pointsort(sortarray, inpoints);
07705 /* Discard duplicate points, which can really mess up the algorithm. */
07706 i = 0;
07707 for (j = 1; j < inpoints; j++) {
07708 if ((sortarray[i][0] == sortarray[j][0])
07709 && (sortarray[i][1] == sortarray[j][1])) {
07710 if (!quiet) {
07711 printf(
07712 "Warning: A duplicate point at (%.12g, %.12g) appeared and was ignored.\n",
07713 sortarray[j][0], sortarray[j][1]);
07714 }
07715 /* Commented out - would eliminate point from output .node file, but causes
07716 a failure if some segment has this point as an endpoint.
07717 setpointmark(sortarray[j], DEADPOINT);
07718 */
07719 } else {
07720 i++;
07721 sortarray[i] = sortarray[j];
07722 }
07723 }
07724 i++;
07725 if (dwyer) {
07726 /* Re-sort the array of points to accommodate alternating cuts. */
07727 divider = i >> 1;
07728 if (i - divider >= 2) {
07729 if (divider >= 2) {
07730 alternateaxes(sortarray, divider, 1);
07731 }
07732 alternateaxes(&sortarray[divider], i - divider, 1);
07733 }
07734 }
07735 if (verbose) {
07736 printf(" Forming triangulation.\n");
07737 }
07738 /* Form the Delaunay triangulation. */
07739 divconqrecurse(sortarray, i, 0, &hullleft, &hullright);
07740 free(sortarray);
07741
07742 return removeghosts(&hullleft);
07743 }
07744
07747 /********* Divide-and-conquer Delaunay triangulation ends here *********/
07748
|
|
||||||||||||||||||||||||
|
Definition at line 7477 of file tlvisTrn_triangle.c. References bond, counterclockwise(), lnext, lnextself, lprev, lprevself, maketriangle(), mergehulls(), printtriangle(), REAL, setapex, setdest, setorg, triedgecopy, and verbose.
07478 {
07479 struct triedge midtri, tri1, tri2, tri3;
07480 struct triedge innerleft, innerright;
07481 REAL area;
07482 int divider;
07483
07484 if (verbose > 2) {
07485 printf(" Triangulating %d points.\n", vertices);
07486 }
07487 if (vertices == 2) {
07488 /* The triangulation of two vertices is an edge. An edge is */
07489 /* represented by two bounding triangles. */
07490 maketriangle(farleft);
07491 setorg(*farleft, sortarray[0]);
07492 setdest(*farleft, sortarray[1]);
07493 /* The apex is intentionally left NULL. */
07494 maketriangle(farright);
07495 setorg(*farright, sortarray[1]);
07496 setdest(*farright, sortarray[0]);
07497 /* The apex is intentionally left NULL. */
07498 bond(*farleft, *farright);
07499 lprevself(*farleft);
07500 lnextself(*farright);
07501 bond(*farleft, *farright);
07502 lprevself(*farleft);
07503 lnextself(*farright);
07504 bond(*farleft, *farright);
07505 if (verbose > 2) {
07506 printf(" Creating ");
07507 printtriangle(farleft);
07508 printf(" Creating ");
07509 printtriangle(farright);
07510 }
07511 /* Ensure that the origin of `farleft' is sortarray[0]. */
07512 lprev(*farright, *farleft);
07513 return;
07514 } else if (vertices == 3) {
07515 /* The triangulation of three vertices is either a triangle (with */
07516 /* three bounding triangles) or two edges (with four bounding */
07517 /* triangles). In either case, four triangles are created. */
07518 maketriangle(&midtri);
07519 maketriangle(&tri1);
07520 maketriangle(&tri2);
07521 maketriangle(&tri3);
07522 area = counterclockwise(sortarray[0], sortarray[1], sortarray[2]);
07523 if (area == 0.0) {
07524 /* Three collinear points; the triangulation is two edges. */
07525 setorg(midtri, sortarray[0]);
07526 setdest(midtri, sortarray[1]);
07527 setorg(tri1, sortarray[1]);
07528 setdest(tri1, sortarray[0]);
07529 setorg(tri2, sortarray[2]);
07530 setdest(tri2, sortarray[1]);
07531 setorg(tri3, sortarray[1]);
07532 setdest(tri3, sortarray[2]);
07533 /* All apices are intentionally left NULL. */
07534 bond(midtri, tri1);
07535 bond(tri2, tri3);
07536 lnextself(midtri);
07537 lprevself(tri1);
07538 lnextself(tri2);
07539 lprevself(tri3);
07540 bond(midtri, tri3);
07541 bond(tri1, tri2);
07542 lnextself(midtri);
07543 lprevself(tri1);
07544 lnextself(tri2);
07545 lprevself(tri3);
07546 bond(midtri, tri1);
07547 bond(tri2, tri3);
07548 /* Ensure that the origin of `farleft' is sortarray[0]. */
07549 triedgecopy(tri1, *farleft);
07550 /* Ensure that the destination of `farright' is sortarray[2]. */
07551 triedgecopy(tri2, *farright);
07552 } else {
07553 /* The three points are not collinear; the triangulation is one */
07554 /* triangle, namely `midtri'. */
07555 setorg(midtri, sortarray[0]);
07556 setdest(tri1, sortarray[0]);
07557 setorg(tri3, sortarray[0]);
07558 /* Apices of tri1, tri2, and tri3 are left NULL. */
07559 if (area > 0.0) {
07560 /* The vertices are in counterclockwise order. */
07561 setdest(midtri, sortarray[1]);
07562 setorg(tri1, sortarray[1]);
07563 setdest(tri2, sortarray[1]);
07564 setapex(midtri, sortarray[2]);
07565 setorg(tri2, sortarray[2]);
07566 setdest(tri3, sortarray[2]);
07567 } else {
07568 /* The vertices are in clockwise order. */
07569 setdest(midtri, sortarray[2]);
07570 setorg(tri1, sortarray[2]);
07571 setdest(tri2, sortarray[2]);
07572 setapex(midtri, sortarray[1]);
07573 setorg(tri2, sortarray[1]);
07574 setdest(tri3, sortarray[1]);
07575 }
07576 /* The topology does not depend on how the vertices are ordered. */
07577 bond(midtri, tri1);
07578 lnextself(midtri);
07579 bond(midtri, tri2);
07580 lnextself(midtri);
07581 bond(midtri, tri3);
07582 lprevself(tri1);
07583 lnextself(tri2);
07584 bond(tri1, tri2);
07585 lprevself(tri1);
07586 lprevself(tri3);
07587 bond(tri1, tri3);
07588 lnextself(tri2);
07589 lprevself(tri3);
07590 bond(tri2, tri3);
07591 /* Ensure that the origin of `farleft' is sortarray[0]. */
07592 triedgecopy(tri1, *farleft);
07593 /* Ensure that the destination of `farright' is sortarray[2]. */
07594 if (area > 0.0) {
07595 triedgecopy(tri2, *farright);
07596 } else {
07597 lnext(*farleft, *farright);
07598 }
07599 }
07600 if (verbose > 2) {
07601 printf(" Creating ");
07602 printtriangle(&midtri);
07603 printf(" Creating ");
07604 printtriangle(&tri1);
07605 printf(" Creating ");
07606 printtriangle(&tri2);
07607 printf(" Creating ");
07608 printtriangle(&tri3);
07609 }
07610 return;
07611 } else {
07612 /* Split the vertices in half. */
07613 divider = vertices >> 1;
07614 /* Recursively triangulate each half. */
07615 divconqrecurse(sortarray, divider, 1 - axis, farleft, &innerleft);
07616 divconqrecurse(&sortarray[divider], vertices - divider, 1 - axis,
07617 &innerright, farright);
07618 if (verbose > 1) {
07619 printf(" Joining triangulations with %d and %d vertices.\n", divider,
07620 vertices - divider);
07621 }
07622 /* Merge the two triangulations into one. */
07623 mergehulls(farleft, &innerleft, &innerright, farright, axis);
07624 }
07625 }
07626
07627 long removeghosts(startghost)
07628 struct triedge *startghost;
07629 {
07630 struct triedge searchedge;
|
Here is the call graph for this function:
|
||||||||||||
|
Definition at line 3440 of file tlvisTrn_triangle.c. References dummytribase, shwords, triangle, triangles, and triwords.
03449 {
03450 printf("Error: Out of memory.\n");
03451 exit(1);
03452 }
03453 /* Align `dummytri' on a `triangles.alignbytes'-byte boundary. */
03454 alignptr = (unsigned long) dummytribase;
03455 dummytri = (triangle *)
03456 (alignptr + (unsigned long) triangles.alignbytes
03457 - (alignptr % (unsigned long) triangles.alignbytes));
03458 /* Initialize the three adjoining triangles to be "outer space". These */
03459 /* will eventually be changed by various bonding operations, but their */
03460 /* values don't really matter, as long as they can legally be */
03461 /* dereferenced. */
03462 dummytri[0] = (triangle) dummytri;
03463 dummytri[1] = (triangle) dummytri;
03464 dummytri[2] = (triangle) dummytri;
03465 /* Three NULL vertex points. */
03466 dummytri[3] = (triangle) NULL;
03467 dummytri[4] = (triangle) NULL;
03468 dummytri[5] = (triangle) NULL;
03469
03470 if (useshelles) {
03471 /* Set up `dummysh', the omnipresent "shell edge" pointed to by any */
03472 /* triangle side or shell edge end that isn't attached to a real shell */
03473 /* edge. */
03474 dummyshbase = (shelle *) malloc(shwords * sizeof(shelle)
03475 + shelles.alignbytes);
03476 if (dummyshbase == (shelle *) NULL) {
03477 printf("Error: Out of memory.\n");
03478 exit(1);
03479 }
03480 /* Align `dummysh' on a `shelles.alignbytes'-byte boundary. */
03481 alignptr = (unsigned long) dummyshbase;
03482 dummysh = (shelle *)
03483 (alignptr + (unsigned long) shelles.alignbytes
03484 - (alignptr % (unsigned long) shelles.alignbytes));
03485 /* Initialize the two adjoining shell edges to be the omnipresent shell */
03486 /* edge. These will eventually be changed by various bonding */
03487 /* operations, but their values don't really matter, as long as they */
03488 /* can legally be dereferenced. */
03489 dummysh[0] = (shelle) dummysh;
03490 dummysh[1] = (shelle) dummysh;
03491 /* Two NULL vertex points. */
03492 dummysh[2] = (shelle) NULL;
03493 dummysh[3] = (shelle) NULL;
03494 /* Initialize the two adjoining triangles to be "outer space". */
03495 dummysh[4] = (shelle) dummytri;
03496 dummysh[5] = (shelle) dummytri;
03497 /* Set the boundary marker to zero. */
03498 * (int *) (dummysh + 6) = 0;
03499
03500 /* Initialize the three adjoining shell edges of `dummytri' to be */
03501 /* the omnipresent shell edge. */
03502 dummytri[6] = (triangle) dummysh;
03503 dummytri[7] = (triangle) dummysh;
03504 dummytri[8] = (triangle) dummysh;
03505 }
03506 }
03507
03508 /*****************************************************************************/
03509 /* */
03510 /* initializepointpool() Calculate the size of the point data structure */
03511 /* and initialize its memory pool. */
|
|
||||||||||||
|
Definition at line 4222 of file tlvisTrn_triangle.c. Referenced by counterclockwiseadapt(), and incircleadapt().
04225 {
04226 Q += e[eindex];
04227 }
04228 return Q;
04229 }
04230
04231 /*****************************************************************************/
04232 /* */
04233 /* counterclockwise() Return a positive value if the points pa, pb, and */
04234 /* pc occur in counterclockwise order; a negative */
|
|
|
Definition at line 4029 of file tlvisTrn_triangle.c. References epsilon, and splitter.
04039 {
04040 lastcheck = check;
04041 epsilon *= half;
04042 if (every_other) {
04043 splitter *= 2.0;
04044 }
04045 every_other = !every_other;
04046 check = 1.0 + epsilon;
04047 } while ((check != 1.0) && (check != lastcheck));
04048 splitter += 1.0;
04049 if (verbose > 1) {
04050 printf("Floating point roundoff is of magnitude %.17g\n", epsilon);
04051 printf("Floating point splitter is %.17g\n", splitter);
04052 }
04053 /* Error bounds for orientation and incircle tests. */
04054 resulterrbound = (3.0 + 8.0 * epsilon) * epsilon;
04055 ccwerrboundA = (3.0 + 16.0 * epsilon) * epsilon;
04056 ccwerrboundB = (2.0 + 12.0 * epsilon) * epsilon;
04057 ccwerrboundC = (9.0 + 64.0 * epsilon) * epsilon * epsilon;
04058 iccerrboundA = (10.0 + 96.0 * epsilon) * epsilon;
04059 iccerrboundB = (4.0 + 48.0 * epsilon) * epsilon;
04060 iccerrboundC = (44.0 + 576.0 * epsilon) * epsilon * epsilon;
04061 }
04062
04063 /*****************************************************************************/
04064 /* */
04065 /* fast_expansion_sum_zeroelim() Sum two expansions, eliminating zero */
04066 /* components from the output expansion. */
|
|
|
||||||||||||||||||||||||
|
Definition at line 4082 of file tlvisTrn_triangle.c. References Fast_Two_Sum, INEXACT, REAL, and Two_Sum. Referenced by counterclockwiseadapt(), and incircleadapt().
04083 {
04084 REAL Q;
04085 INEXACT REAL Qnew;
04086 INEXACT REAL hh;
04087 INEXACT REAL bvirt;
04088 REAL avirt, bround, around;
04089 int eindex, findex, hindex;
04090 REAL enow, fnow;
04091
04092 enow = e[0];
04093 fnow = f[0];
04094 eindex = findex = 0;
04095 if ((fnow > enow) == (fnow > -enow)) {
04096 Q = enow;
04097 enow = e[++eindex];
04098 } else {
04099 Q = fnow;
04100 fnow = f[++findex];
04101 }
04102 hindex = 0;
04103 if ((eindex < elen) && (findex < flen)) {
04104 if ((fnow > enow) == (fnow > -enow)) {
04105 Fast_Two_Sum(enow, Q, Qnew, hh);
04106 enow = e[++eindex];
04107 } else {
04108 Fast_Two_Sum(fnow, Q, Qnew, hh);
04109 fnow = f[++findex];
04110 }
04111 Q = Qnew;
04112 if (hh != 0.0) {
04113 h[hindex++] = hh;
04114 }
04115 while ((eindex < elen) && (findex < flen)) {
04116 if ((fnow > enow) == (fnow > -enow)) {
04117 Two_Sum(Q, enow, Qnew, hh);
04118 enow = e[++eindex];
04119 } else {
04120 Two_Sum(Q, fnow, Qnew, hh);
04121 fnow = f[++findex];
04122 }
04123 Q = Qnew;
04124 if (hh != 0.0) {
04125 h[hindex++] = hh;
04126 }
04127 }
04128 }
04129 while (eindex < elen) {
04130 Two_Sum(Q, enow, Qnew, hh);
04131 enow = e[++eindex];
04132 Q = Qnew;
04133 if (hh != 0.0) {
04134 h[hindex++] = hh;
04135 }
04136 }
04137 while (findex < flen) {
04138 Two_Sum(Q, fnow, Qnew, hh);
04139 fnow = f[++findex];
04140 Q = Qnew;
04141 if (hh != 0.0) {
04142 h[hindex++] = hh;
04143 }
04144 }
04145 if ((Q != 0.0) || (hindex == 0)) {
04146 h[hindex++] = Q;
04147 }
04148 return hindex;
04149 }
04150
04151 /*****************************************************************************/
04152 /* */
04153 /* scale_expansion_zeroelim() Multiply an expansion by a scalar, */
04154 /* eliminating zero components from the */
|
|
||||||||||||||||||||||||||||
|
* Definition at line 10849 of file tlvisTrn_triangle.c. References circumcentercount, counterclockcount, counterclockwise(), noexact, OPPOSITEAPEX, OPPOSITEDEST, OPPOSITEORG, point, and REAL. Referenced by writevoronoi().
10852 {
10853 REAL xdo, ydo, xao, yao, xad, yad;
10854 REAL dodist, aodist, addist;
10855 REAL denominator;
10856 REAL dx, dy;
10857
10858 circumcentercount++;
10859
10860 /* Compute the circumcenter of the triangle. */
10861 xdo = tdest[0] - torg[0];
10862 ydo = tdest[1] - torg[1];
10863 xao = tapex[0] - torg[0];
10864 yao = tapex[1] - torg[1];
10865 dodist = xdo * xdo + ydo * ydo;
10866 aodist = xao * xao + yao * yao;
10867 if (noexact) {
10868 denominator = 0.5 / (xdo * yao - xao * ydo);
10869 } else {
10870 /* Use the counterclockwise() routine to ensure a positive (and */
10871 /* reasonably accurate) result, avoiding any possibility of */
10872 /* division by zero. */
10873 denominator = 0.5 / counterclockwise(tdest, tapex, torg);
10874 /* Don't count the above as an orientation test. */
10875 counterclockcount--;
10876 }
10877 circumcenter[0] = torg[0] - (ydo * aodist - yao * dodist) * denominator;
10878 circumcenter[1] = torg[1] + (xdo * aodist - xao * dodist) * denominator;
10879
10880 /* To interpolate point attributes for the new point inserted at */
10881 /* the circumcenter, define a coordinate system with a xi-axis, */
10882 /* directed from the triangle's origin to its destination, and */
10883 /* an eta-axis, directed from its origin to its apex. */
10884 /* Calculate the xi and eta coordinates of the circumcenter. */
10885 dx = circumcenter[0] - torg[0];
10886 dy = circumcenter[1] - torg[1];
10887 *xi = (dx * yao - xao * dy) * (2.0 * denominator);
10888 *eta = (xdo * dy - dx * ydo) * (2.0 * denominator);
10889
10890 xad = tapex[0] - tdest[0];
10891 yad = tapex[1] - tdest[1];
10892 addist = xad * xad + yad * yad;
10893 if ((addist < dodist) && (addist < aodist)) {
10894 return OPPOSITEORG;
10895 } else if (dodist < aodist) {
10896 return OPPOSITEAPEX;
10897 } else {
10898 return OPPOSITEDEST;
10899 }
10900 }
10901
10902 /*****************************************************************************/
10903 /* */
10904 /* splittriangle() Inserts a point at the circumcenter of a triangle. */
10905 /* Deletes the newly inserted point if it encroaches upon */
|
Here is the call graph for this function:
|
||||||||||||
|
* Definition at line 9179 of file tlvisTrn_triangle.c. References dummytri, point, REAL, and triangle.
09194 {
09195 /* `searchtri' faces directly away from `endpoint'. We could go */
09196 /* left or right. Ask whether it's a triangle or a boundary */
09197 /* on the left. */
09198 onext(*searchtri, checktri);
09199 if (checktri.tri == dummytri) {
09200 leftflag = 0;
09201 } else {
09202 rightflag = 0;
09203 }
09204 }
09205 while (leftflag) {
09206 /* Turn left until satisfied. */
09207 onextself(*searchtri);
09208 if (searchtri->tri == dummytri) {
09209 printf("Internal error in finddirection(): Unable to find a\n");
09210 printf(" triangle leading from (%.12g, %.12g) to", startpoint[0],
09211 startpoint[1]);
09212 printf(" (%.12g, %.12g).\n", endpoint[0], endpoint[1]);
09213 internalerror();
09214 }
09215 apex(*searchtri, leftpoint);
09216 rightccw = leftccw;
09217 leftccw = counterclockwise(endpoint, startpoint, leftpoint);
09218 leftflag = leftccw > 0.0;
09219 }
09220 while (rightflag) {
09221 /* Turn right until satisfied. */
09222 oprevself(*searchtri);
09223 if (searchtri->tri == dummytri) {
09224 printf("Internal error in finddirection(): Unable to find a\n");
09225 printf(" triangle leading from (%.12g, %.12g) to", startpoint[0],
09226 startpoint[1]);
09227 printf(" (%.12g, %.12g).\n", endpoint[0], endpoint[1]);
09228 internalerror();
09229 }
09230 dest(*searchtri, rightpoint);
09231 leftccw = rightccw;
09232 rightccw = counterclockwise(startpoint, endpoint, rightpoint);
09233 rightflag = rightccw > 0.0;
09234 }
09235 if (leftccw == 0.0) {
09236 return LEFTCOLLINEAR;
09237 } else if (rightccw == 0.0) {
09238 return RIGHTCOLLINEAR;
09239 } else {
09240 return WITHIN;
09241 }
09242 }
09243
09244 /*****************************************************************************/
09245 /* */
09246 /* segmentintersection() Find the intersection of an existing segment */
09247 /* and a segment that is being inserted. Insert */
|
|
|
Definition at line 6013 of file tlvisTrn_triangle.c. References dummytri, point, shelle, and triangle. Referenced by triangulatepolygon().
06029 {
06030 printf("Internal error in flip(): Attempt to flip on boundary.\n");
06031 lnextself(*flipedge);
06032 return;
06033 }
06034 if (checksegments) {
06035 tspivot(*flipedge, toplshelle);
06036 if (toplshelle.sh != dummysh) {
06037 printf("Internal error in flip(): Attempt to flip a segment.\n");
06038 lnextself(*flipedge);
06039 return;
06040 }
06041 }
06042 #endif /* SELF_CHECK */
06043 apex(top, farpoint);
06044
06045 /* Identify the casing of the quadrilateral. */
06046 lprev(top, topleft);
06047 sym(topleft, toplcasing);
06048 lnext(top, topright);
06049 sym(topright, toprcasing);
06050 lnext(*flipedge, botleft);
06051 sym(botleft, botlcasing);
06052 lprev(*flipedge, botright);
06053 sym(botright, botrcasing);
06054 /* Rotate the quadrilateral one-quarter turn counterclockwise. */
06055 bond(topleft, botlcasing);
06056 bond(botleft, botrcasing);
06057 bond(botright, toprcasing);
06058 bond(topright, toplcasing);
06059
06060 if (checksegments) {
06061 /* Check for shell edges and rebond them to the quadrilateral. */
06062 tspivot(topleft, toplshelle);
06063 tspivot(botleft, botlshelle);
06064 tspivot(botright, botrshelle);
06065 tspivot(topright, toprshelle);
06066 if (toplshelle.sh == dummysh) {
06067 tsdissolve(topright);
06068 } else {
06069 tsbond(topright, toplshelle);
06070 }
06071 if (botlshelle.sh == dummysh) {
06072 tsdissolve(topleft);
06073 } else {
06074 tsbond(topleft, botlshelle);
06075 }
06076 if (botrshelle.sh == dummysh) {
06077 tsdissolve(botleft);
06078 } else {
06079 tsbond(botleft, botrshelle);
06080 }
06081 if (toprshelle.sh == dummysh) {
06082 tsdissolve(botright);
06083 } else {
06084 tsbond(botright, toprshelle);
06085 }
06086 }
06087
06088 /* New point assignments for the rotated quadrilateral. */
06089 setorg(*flipedge, farpoint);
06090 setdest(*flipedge, botpoint);
06091 setapex(*flipedge, rightpoint);
06092 setorg(top, botpoint);
06093 setdest(top, farpoint);
06094 setapex(top, leftpoint);
06095 if (verbose > 2) {
06096 printf(" Edge flip results in left ");
06097 lnextself(topleft);
06098 printtriangle(&topleft);
06099 printf(" and right ");
06100 printtriangle(flipedge);
06101 }
06102 }
06103
06104 /*****************************************************************************/
06105 /* */
06106 /* insertsite() Insert a vertex into a Delaunay triangulation, */
06107 /* performing flips as necessary to maintain the Delaunay */
|
|
||||||||||||||||
|
Definition at line 9908 of file tlvisTrn_triangle.c. References convex, exit(), firstnumber, getpoint(), inpoints, INPUTLINESIZE, insertsegment(), makepointmap(), markhull(), point, poly, quiet, strtol(), and verbose. Referenced by triangulate().
09916 {
09917 #ifdef TRILIBRARY
09918 char polyfilename[6];
09919 int index;
09920 #else /* not TRILIBRARY */
09921 char inputline[INPUTLINESIZE];
09922 char *stringptr;
09923 #endif /* not TRILIBRARY */
09924 point endpoint1, endpoint2;
09925 int segments;
09926 int segmentmarkers;
09927 int end1, end2;
09928 int boundmarker;
09929 int i;
09930
09931 if (poly) {
09932 if (!quiet) {
09933 printf("Inserting segments into Delaunay triangulation.\n");
09934 }
09935 #ifdef TRILIBRARY
09936 strcpy(polyfilename, "input");
09937 segments = numberofsegments;
09938 segmentmarkers = segmentmarkerlist != (int *) NULL;
09939 index = 0;
09940 #else /* not TRILIBRARY */
09941 /* Read the segments from a .poly file. */
09942 /* Read number of segments and number of boundary markers. */
09943 stringptr = freadline(inputline, polyfile, polyfilename);
09944 segments = (int) strtol (stringptr, &stringptr, 0);
09945 stringptr = findfield(stringptr);
09946 if (*stringptr == '\0') {
09947 segmentmarkers = 0;
09948 } else {
09949 segmentmarkers = (int) strtol (stringptr, &stringptr, 0);
09950 }
09951 #endif /* not TRILIBRARY */
09952 /* If segments are to be inserted, compute a mapping */
09953 /* from points to triangles. */
09954 if (segments > 0) {
09955 if (verbose) {
09956 printf(" Inserting PSLG segments.\n");
09957 }
09958 makepointmap();
09959 }
09960
09961 boundmarker = 0;
09962 /* Read and insert the segments. */
09963 for (i = 1; i <= segments; i++) {
09964 #ifdef TRILIBRARY
09965 end1 = segmentlist[index++];
09966 end2 = segmentlist[index++];
09967 if (segmentmarkers) {
09968 boundmarker = segmentmarkerlist[i - 1];
09969 }
09970 #else /* not TRILIBRARY */
09971 stringptr = freadline(inputline, polyfile, inpolyfilename);
09972 stringptr = findfield(stringptr);
09973 if (*stringptr == '\0') {
09974 printf("Error: Segment %d has no endpoints in %s.\n", i,
09975 polyfilename);
09976 exit(1);
09977 } else {
09978 end1 = (int) strtol (stringptr, &stringptr, 0);
09979 }
09980 stringptr = findfield(stringptr);
09981 if (*stringptr == '\0') {
09982 printf("Error: Segment %d is missing its second endpoint in %s.\n", i,
09983 polyfilename);
09984 exit(1);
09985 } else {
09986 end2 = (int) strtol (stringptr, &stringptr, 0);
09987 }
09988 if (segmentmarkers) {
09989 stringptr = findfield(stringptr);
09990 if (*stringptr == '\0') {
09991 boundmarker = 0;
09992 } else {
09993 boundmarker = (int) strtol (stringptr, &stringptr, 0);
09994 }
09995 }
09996 #endif /* not TRILIBRARY */
09997 if ((end1 < firstnumber) || (end1 >= firstnumber + inpoints)) {
09998 if (!quiet) {
09999 printf("Warning: Invalid first endpoint of segment %d in %s.\n", i,
10000 polyfilename);
10001 }
10002 } else if ((end2 < firstnumber) || (end2 >= firstnumber + inpoints)) {
10003 if (!quiet) {
10004 printf("Warning: Invalid second endpoint of segment %d in %s.\n", i,
10005 polyfilename);
10006 }
10007 } else {
10008 endpoint1 = getpoint(end1);
10009 endpoint2 = getpoint(end2);
10010 if ((endpoint1[0] == endpoint2[0]) && (endpoint1[1] == endpoint2[1])) {
10011 if (!quiet) {
10012 printf("Warning: Endpoints of segment %d are coincident in %s.\n",
10013 i, polyfilename);
10014 }
10015 } else {
10016 insertsegment(endpoint1, endpoint2, boundmarker);
10017 }
10018 }
10019 }
10020 } else {
10021 segments = 0;
10022 }
10023 if (convex || !poly) {
10024 /* Enclose the convex hull with shell edges. */
10025 if (verbose) {
10026 printf(" Enclosing convex hull with segments.\n");
10027 }
10028 markhull();
10029 }
10030 return segments;
10031 }
10032
10035 /********* Segment (shell edge) insertion ends here *********/
10036
|
Here is the call graph for this function:
|
|
Referenced by carveholes(), DeleteCoordList(), open_database_file(), and triangulate(). |
|
|
Definition at line 3764 of file tlvisTrn_triangle.c. References firstnumber, memorypool::itemsperblock, points, and VOID. Referenced by formskeleton().
03770 {
03771 getblock = (VOID **) *getblock;
03772 current += points.itemsperblock;
03773 }
03774 /* Now find the right point. */
03775 alignptr = (unsigned long) (getblock + 1);
03776 foundpoint = (point) (alignptr + (unsigned long) points.alignbytes
03777 - (alignptr % (unsigned long) points.alignbytes));
03778 while (current < number) {
03779 foundpoint += points.itemwords;
03780 current++;
03781 }
03782 return foundpoint;
03783 }
03784
03785 /*****************************************************************************/
03786 /* */
03787 /* triangledeinit() Free all remaining allocated memory. */
03788 /* */
|
|
|
* Definition at line 11114 of file tlvisTrn_triangle.c. References point, quiet, shelle, and triangle. Referenced by triangulate().
11119 {
11120 printf("Adding vertices for second-order triangles.\n");
11121 }
11122 /* The following line ensures that dead items in the pool of nodes */
11123 /* cannot be allocated for the extra nodes associated with high */
11124 /* order elements. This ensures that the primary nodes (at the */
11125 /* corners of elements) will occur earlier in the output files, and */
11126 /* have lower indices, than the extra nodes. */
11127 points.deaditemstack = (VOID *) NULL;
11128
11129 traversalinit(&triangles);
11130 triangleloop.tri = triangletraverse();
11131 /* To loop over the set of edges, loop over all triangles, and look at */
11132 /* the three edges of each triangle. If there isn't another triangle */
11133 /* adjacent to the edge, operate on the edge. If there is another */
11134 /* adjacent triangle, operate on the edge only if the current triangle */
11135 /* has a smaller pointer than its neighbor. This way, each edge is */
11136 /* considered only once. */
11137 while (triangleloop.tri != (triangle *) NULL) {
11138 for (triangleloop.orient = 0; triangleloop.orient < 3;
11139 triangleloop.orient++) {
11140 sym(triangleloop, trisym);
11141 if ((triangleloop.tri < trisym.tri) || (trisym.tri == dummytri)) {
11142 org(triangleloop, torg);
11143 dest(triangleloop, tdest);
11144 /* Create a new node in the middle of the edge. Interpolate */
11145 /* its attributes. */
11146 newpoint = (point) poolalloc(&points);
11147 for (i = 0; i < 2 + nextras; i++) {
11148 newpoint[i] = 0.5 * (torg[i] + tdest[i]);
11149 }
11150 /* Set the new node's marker to zero or one, depending on */
11151 /* whether it lies on a boundary. */
11152 setpointmark(newpoint, trisym.tri == dummytri);
11153 if (useshelles) {
11154 tspivot(triangleloop, checkmark);
11155 /* If this edge is a segment, transfer the marker to the new node. */
11156 if (checkmark.sh != dummysh) {
11157 setpointmark(newpoint, mark(checkmark));
11158 }
11159 }
11160 if (verbose > 1) {
11161 printf(" Creating (%.12g, %.12g).\n", newpoint[0], newpoint[1]);
11162 }
11163 /* Record the new node in the (one or two) adjacent elements. */
11164 triangleloop.tri[highorderindex + triangleloop.orient] =
11165 (triangle) newpoint;
11166 if (trisym.tri != dummytri) {
11167 trisym.tri[highorderindex + trisym.orient] = (triangle) newpoint;
11168 }
11169 }
11170 }
11171 triangleloop.tri = triangletraverse();
11172 }
11173 }
11174
11175 /********* File I/O routines begin here *********/
|
|
||||||||||||||||||||
|
Definition at line 4975 of file tlvisTrn_triangle.c. References Absolute, iccerrboundA, incircleadapt(), incirclecount, noexact, and REAL. Referenced by insertsite(), mergehulls(), and triangulatepolygon().
04975 {
04976 REAL adx, bdx, cdx, ady, bdy, cdy;
04977 REAL bdxcdy, cdxbdy, cdxady, adxcdy, adxbdy, bdxady;
04978 REAL alift, blift, clift;
04979 REAL det;
04980 REAL permanent, errbound;
04981
04982 incirclecount++;
04983
04984 adx = pa[0] - pd[0];
04985 bdx = pb[0] - pd[0];
04986 cdx = pc[0] - pd[0];
04987 ady = pa[1] - pd[1];
04988 bdy = pb[1] - pd[1];
04989 cdy = pc[1] - pd[1];
04990
04991 bdxcdy = bdx * cdy;
04992 cdxbdy = cdx * bdy;
04993 alift = adx * adx + ady * ady;
04994
04995 cdxady = cdx * ady;
04996 adxcdy = adx * cdy;
04997 blift = bdx * bdx + bdy * bdy;
04998
04999 adxbdy = adx * bdy;
05000 bdxady = bdx * ady;
05001 clift = cdx * cdx + cdy * cdy;
05002
05003 det = alift * (bdxcdy - cdxbdy)
05004 + blift * (cdxady - adxcdy)
05005 + clift * (adxbdy - bdxady);
05006
05007 if (noexact) {
05008 return det;
05009 }
05010
05011 permanent = (Absolute(bdxcdy) + Absolute(cdxbdy)) * alift
05012 + (Absolute(cdxady) + Absolute(adxcdy)) * blift
05013 + (Absolute(adxbdy) + Absolute(bdxady)) * clift;
05014 errbound = iccerrboundA * permanent;
05015 if ((det > errbound) || (-det > errbound)) {
05016 return det;
05017 }
05018
05019 return incircleadapt(pa, pb, pc, pd, permanent);
05020 }
05021
05024 /********* Determinant evaluation routines end here *********/
05025
|
Here is the call graph for this function:
|
||||||||||||||||||||||||
|
Definition at line 4401 of file tlvisTrn_triangle.c. References Absolute, estimate(), fast_expansion_sum_zeroelim(), iccerrboundB, iccerrboundC, INEXACT, REAL, resulterrbound, scale_expansion_zeroelim(), Square, Two_Diff_Tail, Two_Product, Two_Two_Diff, and Two_Two_Sum. Referenced by incircle().
04402 {
04403 INEXACT REAL adx, bdx, cdx, ady, bdy, cdy;
04404 REAL det, errbound;
04405
04406 INEXACT REAL bdxcdy1, cdxbdy1, cdxady1, adxcdy1, adxbdy1, bdxady1;
04407 REAL bdxcdy0, cdxbdy0, cdxady0, adxcdy0, adxbdy0, bdxady0;
04408 REAL bc[4], ca[4], ab[4];
04409 INEXACT REAL bc3, ca3, ab3;
04410 REAL axbc[8], axxbc[16], aybc[8], ayybc[16], adet[32];
04411 int axbclen, axxbclen, aybclen, ayybclen, alen;
04412 REAL bxca[8], bxxca[16], byca[8], byyca[16], bdet[32];
04413 int bxcalen, bxxcalen, bycalen, byycalen, blen;
04414 REAL cxab[8], cxxab[16], cyab[8], cyyab[16], cdet[32];
04415 int cxablen, cxxablen, cyablen, cyyablen, clen;
04416 REAL abdet[64];
04417 int ablen;
04418 REAL fin1[1152], fin2[1152];
04419 REAL *finnow, *finother, *finswap;
04420 int finlength;
04421
04422 REAL adxtail, bdxtail, cdxtail, adytail, bdytail, cdytail;
04423 INEXACT REAL adxadx1, adyady1, bdxbdx1, bdybdy1, cdxcdx1, cdycdy1;
04424 REAL adxadx0, adyady0, bdxbdx0, bdybdy0, cdxcdx0, cdycdy0;
04425 REAL aa[4], bb[4], cc[4];
04426 INEXACT REAL aa3, bb3, cc3;
04427 INEXACT REAL ti1, tj1;
04428 REAL ti0, tj0;
04429 REAL u[4], v[4];
04430 INEXACT REAL u3, v3;
04431 REAL temp8[8], temp16a[16], temp16b[16], temp16c[16];
04432 REAL temp32a[32], temp32b[32], temp48[48], temp64[64];
04433 int temp8len, temp16alen, temp16blen, temp16clen;
04434 int temp32alen, temp32blen, temp48len, temp64len;
04435 REAL axtbb[8], axtcc[8], aytbb[8], aytcc[8];
04436 int axtbblen, axtcclen, aytbblen, aytcclen;
04437 REAL bxtaa[8], bxtcc[8], bytaa[8], bytcc[8];
04438 int bxtaalen, bxtcclen, bytaalen, bytcclen;
04439 REAL cxtaa[8], cxtbb[8], cytaa[8], cytbb[8];
04440 int cxtaalen, cxtbblen, cytaalen, cytbblen;
04441 REAL axtbc[8], aytbc[8], bxtca[8], bytca[8], cxtab[8], cytab[8];
04442 int axtbclen, aytbclen, bxtcalen, bytcalen, cxtablen, cytablen;
04443 REAL axtbct[16], aytbct[16], bxtcat[16], bytcat[16], cxtabt[16], cytabt[16];
04444 int axtbctlen, aytbctlen, bxtcatlen, bytcatlen, cxtabtlen, cytabtlen;
04445 REAL axtbctt[8], aytbctt[8], bxtcatt[8];
04446 REAL bytcatt[8], cxtabtt[8], cytabtt[8];
04447 int axtbcttlen, aytbcttlen, bxtcattlen, bytcattlen, cxtabttlen, cytabttlen;
04448 REAL abt[8], bct[8], cat[8];
04449 int abtlen, bctlen, catlen;
04450 REAL abtt[4], bctt[4], catt[4];
04451 int abttlen, bcttlen, cattlen;
04452 INEXACT REAL abtt3, bctt3, catt3;
04453 REAL negate;
04454
04455 INEXACT REAL bvirt;
04456 REAL avirt, bround, around;
04457 INEXACT REAL c;
04458 INEXACT REAL abig;
04459 REAL ahi, alo, bhi, blo;
04460 REAL err1, err2, err3;
04461 INEXACT REAL _i, _j;
04462 REAL _0;
04463
04464 adx = (REAL) (pa[0] - pd[0]);
04465 bdx = (REAL) (pb[0] - pd[0]);
04466 cdx = (REAL) (pc[0] - pd[0]);
04467 ady = (REAL) (pa[1] - pd[1]);
04468 bdy = (REAL) (pb[1] - pd[1]);
04469 cdy = (REAL) (pc[1] - pd[1]);
04470
04471 Two_Product(bdx, cdy, bdxcdy1, bdxcdy0);
04472 Two_Product(cdx, bdy, cdxbdy1, cdxbdy0);
04473 Two_Two_Diff(bdxcdy1, bdxcdy0, cdxbdy1, cdxbdy0, bc3, bc[2], bc[1], bc[0]);
04474 bc[3] = bc3;
04475 axbclen = scale_expansion_zeroelim(4, bc, adx, axbc);
04476 axxbclen = scale_expansion_zeroelim(axbclen, axbc, adx, axxbc);
04477 aybclen = scale_expansion_zeroelim(4, bc, ady, aybc);
04478 ayybclen = scale_expansion_zeroelim(aybclen, aybc, ady, ayybc);
04479 alen = fast_expansion_sum_zeroelim(axxbclen, axxbc, ayybclen, ayybc, adet);
04480
04481 Two_Product(cdx, ady, cdxady1, cdxady0);
04482 Two_Product(adx, cdy, adxcdy1, adxcdy0);
04483 Two_Two_Diff(cdxady1, cdxady0, adxcdy1, adxcdy0, ca3, ca[2], ca[1], ca[0]);
04484 ca[3] = ca3;
04485 bxcalen = scale_expansion_zeroelim(4, ca, bdx, bxca);
04486 bxxcalen = scale_expansion_zeroelim(bxcalen, bxca, bdx, bxxca);
04487 bycalen = scale_expansion_zeroelim(4, ca, bdy, byca);
04488 byycalen = scale_expansion_zeroelim(bycalen, byca, bdy, byyca);
04489 blen = fast_expansion_sum_zeroelim(bxxcalen, bxxca, byycalen, byyca, bdet);
04490
04491 Two_Product(adx, bdy, adxbdy1, adxbdy0);
04492 Two_Product(bdx, ady, bdxady1, bdxady0);
04493 Two_Two_Diff(adxbdy1, adxbdy0, bdxady1, bdxady0, ab3, ab[2], ab[1], ab[0]);
04494 ab[3] = ab3;
04495 cxablen = scale_expansion_zeroelim(4, ab, cdx, cxab);
04496 cxxablen = scale_expansion_zeroelim(cxablen, cxab, cdx, cxxab);
04497 cyablen = scale_expansion_zeroelim(4, ab, cdy, cyab);
04498 cyyablen = scale_expansion_zeroelim(cyablen, cyab, cdy, cyyab);
04499 clen = fast_expansion_sum_zeroelim(cxxablen, cxxab, cyyablen, cyyab, cdet);
04500
04501 ablen = fast_expansion_sum_zeroelim(alen, adet, blen, bdet, abdet);
04502 finlength = fast_expansion_sum_zeroelim(ablen, abdet, clen, cdet, fin1);
04503
04504 det = estimate(finlength, fin1);
04505 errbound = iccerrboundB * permanent;
04506 if ((det >= errbound) || (-det >= errbound)) {
04507 return det;
04508 }
04509
04510 Two_Diff_Tail(pa[0], pd[0], adx, adxtail);
04511 Two_Diff_Tail(pa[1], pd[1], ady, adytail);
04512 Two_Diff_Tail(pb[0], pd[0], bdx, bdxtail);
04513 Two_Diff_Tail(pb[1], pd[1], bdy, bdytail);
04514 Two_Diff_Tail(pc[0], pd[0], cdx, cdxtail);
04515 Two_Diff_Tail(pc[1], pd[1], cdy, cdytail);
04516 if ((adxtail == 0.0) && (bdxtail == 0.0) && (cdxtail == 0.0)
04517 && (adytail == 0.0) && (bdytail == 0.0) && (cdytail == 0.0)) {
04518 return det;
04519 }
04520
04521 errbound = iccerrboundC * permanent + resulterrbound * Absolute(det);
04522 det += ((adx * adx + ady * ady) * ((bdx * cdytail + cdy * bdxtail)
04523 - (bdy * cdxtail + cdx * bdytail))
04524 + 2.0 * (adx * adxtail + ady * adytail) * (bdx * cdy - bdy * cdx))
04525 + ((bdx * bdx + bdy * bdy) * ((cdx * adytail + ady * cdxtail)
04526 - (cdy * adxtail + adx * cdytail))
04527 + 2.0 * (bdx * bdxtail + bdy * bdytail) * (cdx * ady - cdy * adx))
04528 + ((cdx * cdx + cdy * cdy) * ((adx * bdytail + bdy * adxtail)
04529 - (ady * bdxtail + bdx * adytail))
04530 + 2.0 * (cdx * cdxtail + cdy * cdytail) * (adx * bdy - ady * bdx));
04531 if ((det >= errbound) || (-det >= errbound)) {
04532 return det;
04533 }
04534
04535 finnow = fin1;
04536 finother = fin2;
04537
04538 if ((bdxtail != 0.0) || (bdytail != 0.0)
04539 || (cdxtail != 0.0) || (cdytail != 0.0)) {
04540 Square(adx, adxadx1, adxadx0);
04541 Square(ady, adyady1, adyady0);
04542 Two_Two_Sum(adxadx1, adxadx0, adyady1, adyady0, aa3, aa[2], aa[1], aa[0]);
04543 aa[3] = aa3;
04544 }
04545 if ((cdxtail != 0.0) || (cdytail != 0.0)
04546 || (adxtail != 0.0) || (adytail != 0.0)) {
04547 Square(bdx, bdxbdx1, bdxbdx0);
04548 Square(bdy, bdybdy1, bdybdy0);
04549 Two_Two_Sum(bdxbdx1, bdxbdx0, bdybdy1, bdybdy0, bb3, bb[2], bb[1], bb[0]);
04550 bb[3] = bb3;
04551 }
04552 if ((adxtail != 0.0) || (adytail != 0.0)
04553 || (bdxtail != 0.0) || (bdytail != 0.0)) {
04554 Square(cdx, cdxcdx1, cdxcdx0);
04555 Square(cdy, cdycdy1, cdycdy0);
04556 Two_Two_Sum(cdxcdx1, cdxcdx0, cdycdy1, cdycdy0, cc3, cc[2], cc[1], cc[0]);
04557 cc[3] = cc3;
04558 }
04559
04560 if (adxtail != 0.0) {
04561 axtbclen = scale_expansion_zeroelim(4, bc, adxtail, axtbc);
04562 temp16alen = scale_expansion_zeroelim(axtbclen, axtbc, 2.0 * adx,
04563 temp16a);
04564
04565 axtcclen = scale_expansion_zeroelim(4, cc, adxtail, axtcc);
04566 temp16blen = scale_expansion_zeroelim(axtcclen, axtcc, bdy, temp16b);
04567
04568 axtbblen = scale_expansion_zeroelim(4, bb, adxtail, axtbb);
04569 temp16clen = scale_expansion_zeroelim(axtbblen, axtbb, -cdy, temp16c);
04570
04571 temp32alen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04572 temp16blen, temp16b, temp32a);
04573 temp48len = fast_expansion_sum_zeroelim(temp16clen, temp16c,
04574 temp32alen, temp32a, temp48);
04575 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
04576 temp48, finother);
04577 finswap = finnow; finnow = finother; finother = finswap;
04578 }
04579 if (adytail != 0.0) {
04580 aytbclen = scale_expansion_zeroelim(4, bc, adytail, aytbc);
04581 temp16alen = scale_expansion_zeroelim(aytbclen, aytbc, 2.0 * ady,
04582 temp16a);
04583
04584 aytbblen = scale_expansion_zeroelim(4, bb, adytail, aytbb);
04585 temp16blen = scale_expansion_zeroelim(aytbblen, aytbb, cdx, temp16b);
04586
04587 aytcclen = scale_expansion_zeroelim(4, cc, adytail, aytcc);
04588 temp16clen = scale_expansion_zeroelim(aytcclen, aytcc, -bdx, temp16c);
04589
04590 temp32alen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04591 temp16blen, temp16b, temp32a);
04592 temp48len = fast_expansion_sum_zeroelim(temp16clen, temp16c,
04593 temp32alen, temp32a, temp48);
04594 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
04595 temp48, finother);
04596 finswap = finnow; finnow = finother; finother = finswap;
04597 }
04598 if (bdxtail != 0.0) {
04599 bxtcalen = scale_expansion_zeroelim(4, ca, bdxtail, bxtca);
04600 temp16alen = scale_expansion_zeroelim(bxtcalen, bxtca, 2.0 * bdx,
04601 temp16a);
04602
04603 bxtaalen = scale_expansion_zeroelim(4, aa, bdxtail, bxtaa);
04604 temp16blen = scale_expansion_zeroelim(bxtaalen, bxtaa, cdy, temp16b);
04605
04606 bxtcclen = scale_expansion_zeroelim(4, cc, bdxtail, bxtcc);
04607 temp16clen = scale_expansion_zeroelim(bxtcclen, bxtcc, -ady, temp16c);
04608
04609 temp32alen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04610 temp16blen, temp16b, temp32a);
04611 temp48len = fast_expansion_sum_zeroelim(temp16clen, temp16c,
04612 temp32alen, temp32a, temp48);
04613 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
04614 temp48, finother);
04615 finswap = finnow; finnow = finother; finother = finswap;
04616 }
04617 if (bdytail != 0.0) {
04618 bytcalen = scale_expansion_zeroelim(4, ca, bdytail, bytca);
04619 temp16alen = scale_expansion_zeroelim(bytcalen, bytca, 2.0 * bdy,
04620 temp16a);
04621
04622 bytcclen = scale_expansion_zeroelim(4, cc, bdytail, bytcc);
04623 temp16blen = scale_expansion_zeroelim(bytcclen, bytcc, adx, temp16b);
04624
04625 bytaalen = scale_expansion_zeroelim(4, aa, bdytail, bytaa);
04626 temp16clen = scale_expansion_zeroelim(bytaalen, bytaa, -cdx, temp16c);
04627
04628 temp32alen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04629 temp16blen, temp16b, temp32a);
04630 temp48len = fast_expansion_sum_zeroelim(temp16clen, temp16c,
04631 temp32alen, temp32a, temp48);
04632 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
04633 temp48, finother);
04634 finswap = finnow; finnow = finother; finother = finswap;
04635 }
04636 if (cdxtail != 0.0) {
04637 cxtablen = scale_expansion_zeroelim(4, ab, cdxtail, cxtab);
04638 temp16alen = scale_expansion_zeroelim(cxtablen, cxtab, 2.0 * cdx,
04639 temp16a);
04640
04641 cxtbblen = scale_expansion_zeroelim(4, bb, cdxtail, cxtbb);
04642 temp16blen = scale_expansion_zeroelim(cxtbblen, cxtbb, ady, temp16b);
04643
04644 cxtaalen = scale_expansion_zeroelim(4, aa, cdxtail, cxtaa);
04645 temp16clen = scale_expansion_zeroelim(cxtaalen, cxtaa, -bdy, temp16c);
04646
04647 temp32alen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04648 temp16blen, temp16b, temp32a);
04649 temp48len = fast_expansion_sum_zeroelim(temp16clen, temp16c,
04650 temp32alen, temp32a, temp48);
04651 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
04652 temp48, finother);
04653 finswap = finnow; finnow = finother; finother = finswap;
04654 }
04655 if (cdytail != 0.0) {
04656 cytablen = scale_expansion_zeroelim(4, ab, cdytail, cytab);
04657 temp16alen = scale_expansion_zeroelim(cytablen, cytab, 2.0 * cdy,
04658 temp16a);
04659
04660 cytaalen = scale_expansion_zeroelim(4, aa, cdytail, cytaa);
04661 temp16blen = scale_expansion_zeroelim(cytaalen, cytaa, bdx, temp16b);
04662
04663 cytbblen = scale_expansion_zeroelim(4, bb, cdytail, cytbb);
04664 temp16clen = scale_expansion_zeroelim(cytbblen, cytbb, -adx, temp16c);
04665
04666 temp32alen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04667 temp16blen, temp16b, temp32a);
04668 temp48len = fast_expansion_sum_zeroelim(temp16clen, temp16c,
04669 temp32alen, temp32a, temp48);
04670 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
04671 temp48, finother);
04672 finswap = finnow; finnow = finother; finother = finswap;
04673 }
04674
04675 if ((adxtail != 0.0) || (adytail != 0.0)) {
04676 if ((bdxtail != 0.0) || (bdytail != 0.0)
04677 || (cdxtail != 0.0) || (cdytail != 0.0)) {
04678 Two_Product(bdxtail, cdy, ti1, ti0);
04679 Two_Product(bdx, cdytail, tj1, tj0);
04680 Two_Two_Sum(ti1, ti0, tj1, tj0, u3, u[2], u[1], u[0]);
04681 u[3] = u3;
04682 negate = -bdy;
04683 Two_Product(cdxtail, negate, ti1, ti0);
04684 negate = -bdytail;
04685 Two_Product(cdx, negate, tj1, tj0);
04686 Two_Two_Sum(ti1, ti0, tj1, tj0, v3, v[2], v[1], v[0]);
04687 v[3] = v3;
04688 bctlen = fast_expansion_sum_zeroelim(4, u, 4, v, bct);
04689
04690 Two_Product(bdxtail, cdytail, ti1, ti0);
04691 Two_Product(cdxtail, bdytail, tj1, tj0);
04692 Two_Two_Diff(ti1, ti0, tj1, tj0, bctt3, bctt[2], bctt[1], bctt[0]);
04693 bctt[3] = bctt3;
04694 bcttlen = 4;
04695 } else {
04696 bct[0] = 0.0;
04697 bctlen = 1;
04698 bctt[0] = 0.0;
04699 bcttlen = 1;
04700 }
04701
04702 if (adxtail != 0.0) {
04703 temp16alen = scale_expansion_zeroelim(axtbclen, axtbc, adxtail, temp16a);
04704 axtbctlen = scale_expansion_zeroelim(bctlen, bct, adxtail, axtbct);
04705 temp32alen = scale_expansion_zeroelim(axtbctlen, axtbct, 2.0 * adx,
04706 temp32a);
04707 temp48len = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04708 temp32alen, temp32a, temp48);
04709 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
04710 temp48, finother);
04711 finswap = finnow; finnow = finother; finother = finswap;
04712 if (bdytail != 0.0) {
04713 temp8len = scale_expansion_zeroelim(4, cc, adxtail, temp8);
04714 temp16alen = scale_expansion_zeroelim(temp8len, temp8, bdytail,
04715 temp16a);
04716 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp16alen,
04717 temp16a, finother);
04718 finswap = finnow; finnow = finother; finother = finswap;
04719 }
04720 if (cdytail != 0.0) {
04721 temp8len = scale_expansion_zeroelim(4, bb, -adxtail, temp8);
04722 temp16alen = scale_expansion_zeroelim(temp8len, temp8, cdytail,
04723 temp16a);
04724 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp16alen,
04725 temp16a, finother);
04726 finswap = finnow; finnow = finother; finother = finswap;
04727 }
04728
04729 temp32alen = scale_expansion_zeroelim(axtbctlen, axtbct, adxtail,
04730 temp32a);
04731 axtbcttlen = scale_expansion_zeroelim(bcttlen, bctt, adxtail, axtbctt);
04732 temp16alen = scale_expansion_zeroelim(axtbcttlen, axtbctt, 2.0 * adx,
04733 temp16a);
04734 temp16blen = scale_expansion_zeroelim(axtbcttlen, axtbctt, adxtail,
04735 temp16b);
04736 temp32blen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04737 temp16blen, temp16b, temp32b);
04738 temp64len = fast_expansion_sum_zeroelim(temp32alen, temp32a,
04739 temp32blen, temp32b, temp64);
04740 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp64len,
04741 temp64, finother);
04742 finswap = finnow; finnow = finother; finother = finswap;
04743 }
04744 if (adytail != 0.0) {
04745 temp16alen = scale_expansion_zeroelim(aytbclen, aytbc, adytail, temp16a);
04746 aytbctlen = scale_expansion_zeroelim(bctlen, bct, adytail, aytbct);
04747 temp32alen = scale_expansion_zeroelim(aytbctlen, aytbct, 2.0 * ady,
04748 temp32a);
04749 temp48len = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04750 temp32alen, temp32a, temp48);
04751 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
04752 temp48, finother);
04753 finswap = finnow; finnow = finother; finother = finswap;
04754
04755
04756 temp32alen = scale_expansion_zeroelim(aytbctlen, aytbct, adytail,
04757 temp32a);
04758 aytbcttlen = scale_expansion_zeroelim(bcttlen, bctt, adytail, aytbctt);
04759 temp16alen = scale_expansion_zeroelim(aytbcttlen, aytbctt, 2.0 * ady,
04760 temp16a);
04761 temp16blen = scale_expansion_zeroelim(aytbcttlen, aytbctt, adytail,
04762 temp16b);
04763 temp32blen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04764 temp16blen, temp16b, temp32b);
04765 temp64len = fast_expansion_sum_zeroelim(temp32alen, temp32a,
04766 temp32blen, temp32b, temp64);
04767 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp64len,
04768 temp64, finother);
04769 finswap = finnow; finnow = finother; finother = finswap;
04770 }
04771 }
04772 if ((bdxtail != 0.0) || (bdytail != 0.0)) {
04773 if ((cdxtail != 0.0) || (cdytail != 0.0)
04774 || (adxtail != 0.0) || (adytail != 0.0)) {
04775 Two_Product(cdxtail, ady, ti1, ti0);
04776 Two_Product(cdx, adytail, tj1, tj0);
04777 Two_Two_Sum(ti1, ti0, tj1, tj0, u3, u[2], u[1], u[0]);
04778 u[3] = u3;
04779 negate = -cdy;
04780 Two_Product(adxtail, negate, ti1, ti0);
04781 negate = -cdytail;
04782 Two_Product(adx, negate, tj1, tj0);
04783 Two_Two_Sum(ti1, ti0, tj1, tj0, v3, v[2], v[1], v[0]);
04784 v[3] = v3;
04785 catlen = fast_expansion_sum_zeroelim(4, u, 4, v, cat);
04786
04787 Two_Product(cdxtail, adytail, ti1, ti0);
04788 Two_Product(adxtail, cdytail, tj1, tj0);
04789 Two_Two_Diff(ti1, ti0, tj1, tj0, catt3, catt[2], catt[1], catt[0]);
04790 catt[3] = catt3;
04791 cattlen = 4;
04792 } else {
04793 cat[0] = 0.0;
04794 catlen = 1;
04795 catt[0] = 0.0;
04796 cattlen = 1;
04797 }
04798
04799 if (bdxtail != 0.0) {
04800 temp16alen = scale_expansion_zeroelim(bxtcalen, bxtca, bdxtail, temp16a);
04801 bxtcatlen = scale_expansion_zeroelim(catlen, cat, bdxtail, bxtcat);
04802 temp32alen = scale_expansion_zeroelim(bxtcatlen, bxtcat, 2.0 * bdx,
04803 temp32a);
04804 temp48len = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04805 temp32alen, temp32a, temp48);
04806 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
04807 temp48, finother);
04808 finswap = finnow; finnow = finother; finother = finswap;
04809 if (cdytail != 0.0) {
04810 temp8len = scale_expansion_zeroelim(4, aa, bdxtail, temp8);
04811 temp16alen = scale_expansion_zeroelim(temp8len, temp8, cdytail,
04812 temp16a);
04813 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp16alen,
04814 temp16a, finother);
04815 finswap = finnow; finnow = finother; finother = finswap;
04816 }
04817 if (adytail != 0.0) {
04818 temp8len = scale_expansion_zeroelim(4, cc, -bdxtail, temp8);
04819 temp16alen = scale_expansion_zeroelim(temp8len, temp8, adytail,
04820 temp16a);
04821 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp16alen,
04822 temp16a, finother);
04823 finswap = finnow; finnow = finother; finother = finswap;
04824 }
04825
04826 temp32alen = scale_expansion_zeroelim(bxtcatlen, bxtcat, bdxtail,
04827 temp32a);
04828 bxtcattlen = scale_expansion_zeroelim(cattlen, catt, bdxtail, bxtcatt);
04829 temp16alen = scale_expansion_zeroelim(bxtcattlen, bxtcatt, 2.0 * bdx,
04830 temp16a);
04831 temp16blen = scale_expansion_zeroelim(bxtcattlen, bxtcatt, bdxtail,
04832 temp16b);
04833 temp32blen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04834 temp16blen, temp16b, temp32b);
04835 temp64len = fast_expansion_sum_zeroelim(temp32alen, temp32a,
04836 temp32blen, temp32b, temp64);
04837 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp64len,
04838 temp64, finother);
04839 finswap = finnow; finnow = finother; finother = finswap;
04840 }
04841 if (bdytail != 0.0) {
04842 temp16alen = scale_expansion_zeroelim(bytcalen, bytca, bdytail, temp16a);
04843 bytcatlen = scale_expansion_zeroelim(catlen, cat, bdytail, bytcat);
04844 temp32alen = scale_expansion_zeroelim(bytcatlen, bytcat, 2.0 * bdy,
04845 temp32a);
04846 temp48len = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04847 temp32alen, temp32a, temp48);
04848 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
04849 temp48, finother);
04850 finswap = finnow; finnow = finother; finother = finswap;
04851
04852
04853 temp32alen = scale_expansion_zeroelim(bytcatlen, bytcat, bdytail,
04854 temp32a);
04855 bytcattlen = scale_expansion_zeroelim(cattlen, catt, bdytail, bytcatt);
04856 temp16alen = scale_expansion_zeroelim(bytcattlen, bytcatt, 2.0 * bdy,
04857 temp16a);
04858 temp16blen = scale_expansion_zeroelim(bytcattlen, bytcatt, bdytail,
04859 temp16b);
04860 temp32blen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04861 temp16blen, temp16b, temp32b);
04862 temp64len = fast_expansion_sum_zeroelim(temp32alen, temp32a,
04863 temp32blen, temp32b, temp64);
04864 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp64len,
04865 temp64, finother);
04866 finswap = finnow; finnow = finother; finother = finswap;
04867 }
04868 }
04869 if ((cdxtail != 0.0) || (cdytail != 0.0)) {
04870 if ((adxtail != 0.0) || (adytail != 0.0)
04871 || (bdxtail != 0.0) || (bdytail != 0.0)) {
04872 Two_Product(adxtail, bdy, ti1, ti0);
04873 Two_Product(adx, bdytail, tj1, tj0);
04874 Two_Two_Sum(ti1, ti0, tj1, tj0, u3, u[2], u[1], u[0]);
04875 u[3] = u3;
04876 negate = -ady;
04877 Two_Product(bdxtail, negate, ti1, ti0);
04878 negate = -adytail;
04879 Two_Product(bdx, negate, tj1, tj0);
04880 Two_Two_Sum(ti1, ti0, tj1, tj0, v3, v[2], v[1], v[0]);
04881 v[3] = v3;
04882 abtlen = fast_expansion_sum_zeroelim(4, u, 4, v, abt);
04883
04884 Two_Product(adxtail, bdytail, ti1, ti0);
04885 Two_Product(bdxtail, adytail, tj1, tj0);
04886 Two_Two_Diff(ti1, ti0, tj1, tj0, abtt3, abtt[2], abtt[1], abtt[0]);
04887 abtt[3] = abtt3;
04888 abttlen = 4;
04889 } else {
04890 abt[0] = 0.0;
04891 abtlen = 1;
04892 abtt[0] = 0.0;
04893 abttlen = 1;
04894 }
04895
04896 if (cdxtail != 0.0) {
04897 temp16alen = scale_expansion_zeroelim(cxtablen, cxtab, cdxtail, temp16a);
04898 cxtabtlen = scale_expansion_zeroelim(abtlen, abt, cdxtail, cxtabt);
04899 temp32alen = scale_expansion_zeroelim(cxtabtlen, cxtabt, 2.0 * cdx,
04900 temp32a);
04901 temp48len = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04902 temp32alen, temp32a, temp48);
04903 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
04904 temp48, finother);
04905 finswap = finnow; finnow = finother; finother = finswap;
04906 if (adytail != 0.0) {
04907 temp8len = scale_expansion_zeroelim(4, bb, cdxtail, temp8);
04908 temp16alen = scale_expansion_zeroelim(temp8len, temp8, adytail,
04909 temp16a);
04910 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp16alen,
04911 temp16a, finother);
04912 finswap = finnow; finnow = finother; finother = finswap;
04913 }
04914 if (bdytail != 0.0) {
04915 temp8len = scale_expansion_zeroelim(4, aa, -cdxtail, temp8);
04916 temp16alen = scale_expansion_zeroelim(temp8len, temp8, bdytail,
04917 temp16a);
04918 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp16alen,
04919 temp16a, finother);
04920 finswap = finnow; finnow = finother; finother = finswap;
04921 }
04922
04923 temp32alen = scale_expansion_zeroelim(cxtabtlen, cxtabt, cdxtail,
04924 temp32a);
04925 cxtabttlen = scale_expansion_zeroelim(abttlen, abtt, cdxtail, cxtabtt);
04926 temp16alen = scale_expansion_zeroelim(cxtabttlen, cxtabtt, 2.0 * cdx,
04927 temp16a);
04928 temp16blen = scale_expansion_zeroelim(cxtabttlen, cxtabtt, cdxtail,
04929 temp16b);
04930 temp32blen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04931 temp16blen, temp16b, temp32b);
04932 temp64len = fast_expansion_sum_zeroelim(temp32alen, temp32a,
04933 temp32blen, temp32b, temp64);
04934 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp64len,
04935 temp64, finother);
04936 finswap = finnow; finnow = finother; finother = finswap;
04937 }
04938 if (cdytail != 0.0) {
04939 temp16alen = scale_expansion_zeroelim(cytablen, cytab, cdytail, temp16a);
04940 cytabtlen = scale_expansion_zeroelim(abtlen, abt, cdytail, cytabt);
04941 temp32alen = scale_expansion_zeroelim(cytabtlen, cytabt, 2.0 * cdy,
04942 temp32a);
04943 temp48len = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04944 temp32alen, temp32a, temp48);
04945 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp48len,
04946 temp48, finother);
04947 finswap = finnow; finnow = finother; finother = finswap;
04948
04949
04950 temp32alen = scale_expansion_zeroelim(cytabtlen, cytabt, cdytail,
04951 temp32a);
04952 cytabttlen = scale_expansion_zeroelim(abttlen, abtt, cdytail, cytabtt);
04953 temp16alen = scale_expansion_zeroelim(cytabttlen, cytabtt, 2.0 * cdy,
04954 temp16a);
04955 temp16blen = scale_expansion_zeroelim(cytabttlen, cytabtt, cdytail,
04956 temp16b);
04957 temp32blen = fast_expansion_sum_zeroelim(temp16alen, temp16a,
04958 temp16blen, temp16b, temp32b);
04959 temp64len = fast_expansion_sum_zeroelim(temp32alen, temp32a,
04960 temp32blen, temp32b, temp64);
04961 finlength = fast_expansion_sum_zeroelim(finlength, finnow, temp64len,
04962 temp64, finother);
04963 finswap = finnow; finnow = finother; finother = finswap;
04964 }
04965 }
04966
04967 return finnow[finlength - 1];
04968 }
04969
04970 REAL incircle(pa, pb, pc, pd)
04971 point pa;
04972 point pb;
04973 point pc;
|
Here is the call graph for this function:
|
|
* Definition at line 10054 of file tlvisTrn_triangle.c. References point, shelle, triangle, and verbose. Referenced by carveholes().
10060 {
10061 printf(" Marking concavities (external triangles) for elimination.\n");
10062 }
10063 /* Find a triangle handle on the hull. */
10064 hulltri.tri = dummytri;
10065 hulltri.orient = 0;
10066 symself(hulltri);
10067 /* Remember where we started so we know when to stop. */
10068 triedgecopy(hulltri, starttri);
10069 /* Go once counterclockwise around the convex hull. */
10070 do {
10071 /* Ignore triangles that are already infected. */
10072 if (!infected(hulltri)) {
10073 /* Is the triangle protected by a shell edge? */
10074 tspivot(hulltri, hulledge);
10075 if (hulledge.sh == dummysh) {
10076 /* The triangle is not protected; infect it. */
10077 infect(hulltri);
10078 deadtri = (triangle **) poolalloc(&viri);
10079 *deadtri = hulltri.tri;
10080 } else {
10081 /* The triangle is protected; set boundary markers if appropriate. */
10082 if (mark(hulledge) == 0) {
10083 setmark(hulledge, 1);
10084 org(hulltri, horg);
10085 dest(hulltri, hdest);
10086 if (pointmark(horg) == 0) {
10087 setpointmark(horg, 1);
10088 }
10089 if (pointmark(hdest) == 0) {
10090 setpointmark(hdest, 1);
10091 }
10092 }
10093 }
10094 }
10095 /* To find the next hull edge, go clockwise around the next vertex. */
10096 lnextself(hulltri);
10097 oprev(hulltri, nexttri);
10098 while (nexttri.tri != dummytri) {
10099 triedgecopy(nexttri, hulltri);
10100 oprev(hulltri, nexttri);
10101 }
10102 } while (!triedgeequal(hulltri, starttri));
10103 }
10104
10105 /*****************************************************************************/
10106 /* */
10107 /* plague() Spread the virus from all infected triangles to any neighbors */
10108 /* not protected by shell edges. Delete all infected triangles. */
|
|
|
Definition at line 3523 of file tlvisTrn_triangle.c. References mesh_dim, nextras, point2triindex, pointmarkindex, poly, REAL, and triangle. Referenced by transfernodes().
03527 {
03528 /* The index within each point at which a triangle pointer is found. */
03529 /* Ensure the pointer is aligned to a sizeof(triangle)-byte address. */
03530 point2triindex = (pointsize + sizeof(triangle) - 1) / sizeof(triangle);
03531 pointsize = (point2triindex + 1) * sizeof(triangle);
03532 }
03533 /* Initialize the pool of points. */
03534 poolinit(&points, pointsize, POINTPERBLOCK,
03535 (sizeof(REAL) >= sizeof(triangle)) ? FLOATINGPOINT : POINTER, 0);
03536 }
03537
03538 /*****************************************************************************/
03539 /* */
03540 /* initializetrisegpools() Calculate the sizes of the triangle and shell */
03541 /* edge data structures and initialize their */
|
|
|
Definition at line 3554 of file tlvisTrn_triangle.c. References areaboundindex, eextras, elemattribindex, highorderindex, order, REAL, regionattrib, triangle, useshelles, and vararea.
03570 {
03571 trisize = (areaboundindex + 1) * sizeof(REAL);
03572 } else if (eextras + regionattrib > 0) {
03573 trisize = areaboundindex * sizeof(REAL);
03574 }
03575 /* If a Voronoi diagram or triangle neighbor graph is requested, make */
03576 /* sure there's room to store an integer index in each triangle. This */
03577 /* integer index can occupy the same space as the shell edges or */
03578 /* attributes or area constraint or extra nodes. */
03579 if ((voronoi || neighbors) &&
03580 (trisize < 6 * sizeof(triangle) + sizeof(int))) {
03581 trisize = 6 * sizeof(triangle) + sizeof(int);
03582 }
03583 /* Having determined the memory size of a triangle, initialize the pool. */
03584 poolinit(&triangles, trisize, TRIPERBLOCK, POINTER, 4);
03585
03586 if (useshelles) {
03587 /* Initialize the pool of shell edges. */
03588 poolinit(&shelles, 6 * sizeof(triangle) + sizeof(int), SHELLEPERBLOCK,
03589 POINTER, 4);
03590
03591 /* Initialize the "outer space" triangle and omnipresent shell edge. */
03592 dummyinit(triangles.itemwords, shelles.itemwords);
03593 } else {
03594 /* Initialize the "outer space" triangle. */
03595 dummyinit(triangles.itemwords, 0);
03596 }
03597 }
03598
03599 /*****************************************************************************/
03600 /* */
03601 /* triangledealloc() Deallocate space for a triangle, marking it dead. */
03602 /* */
|
|
||||||||||||||||
|
Definition at line 9765 of file tlvisTrn_triangle.c. References point, triangle, and verbose. Referenced by formskeleton().
09770 {
09771 printf(" Connecting (%.12g, %.12g) to (%.12g, %.12g).\n",
09772 endpoint1[0], endpoint1[1], endpoint2[0], endpoint2[1]);
09773 }
09774
09775 /* Find a triangle whose origin is the segment's first endpoint. */
09776 checkpoint = (point) NULL;
09777 encodedtri = point2tri(endpoint1);
09778 if (encodedtri != (triangle) NULL) {
09779 decode(encodedtri, searchtri1);
09780 org(searchtri1, checkpoint);
09781 }
09782 if (checkpoint != endpoint1) {
09783 /* Find a boundary triangle to search from. */
09784 searchtri1.tri = dummytri;
09785 searchtri1.orient = 0;
09786 symself(searchtri1);
09787 /* Search for the segment's first endpoint by point location. */
09788 if (locate(endpoint1, &searchtri1) != ONVERTEX) {
09789 printf(
09790 "Internal error in insertsegment(): Unable to locate PSLG point\n");
09791 printf(" (%.12g, %.12g) in triangulation.\n",
09792 endpoint1[0], endpoint1[1]);
09793 internalerror();
09794 }
09795 }
09796 /* Remember this triangle to improve subsequent point location. */
09797 triedgecopy(searchtri1, recenttri);
09798 /* Scout the beginnings of a path from the first endpoint */
09799 /* toward the second. */
09800 if (scoutsegment(&searchtri1, endpoint2, newmark)) {
09801 /* The segment was easily inserted. */
09802 return;
09803 }
09804 /* The first endpoint may have changed if a collision with an intervening */
09805 /* vertex on the segment occurred. */
09806 org(searchtri1, endpoint1);
09807
09808 /* Find a triangle whose origin is the segment's second endpoint. */
09809 checkpoint = (point) NULL;
09810 encodedtri = point2tri(endpoint2);
09811 if (encodedtri != (triangle) NULL) {
09812 decode(encodedtri, searchtri2);
09813 org(searchtri2, checkpoint);
09814 }
09815 if (checkpoint != endpoint2) {
09816 /* Find a boundary triangle to search from. */
09817 searchtri2.tri = dummytri;
09818 searchtri2.orient = 0;
09819 symself(searchtri2);
09820 /* Search for the segment's second endpoint by point location. */
09821 if (locate(endpoint2, &searchtri2) != ONVERTEX) {
09822 printf(
09823 "Internal error in insertsegment(): Unable to locate PSLG point\n");
09824 printf(" (%.12g, %.12g) in triangulation.\n",
09825 endpoint2[0], endpoint2[1]);
09826 internalerror();
09827 }
09828 }
09829 /* Remember this triangle to improve subsequent point location. */
09830 triedgecopy(searchtri2, recenttri);
09831 /* Scout the beginnings of a path from the second endpoint */
09832 /* toward the first. */
09833 if (scoutsegment(&searchtri2, endpoint1, newmark)) {
09834 /* The segment was easily inserted. */
09835 return;
09836 }
09837 /* The second endpoint may have changed if a collision with an intervening */
09838 /* vertex on the segment occurred. */
09839 org(searchtri2, endpoint2);
09840
09841 #ifndef REDUCED
09842 #ifndef CDT_ONLY
09843 if (splitseg) {
09844 /* Insert vertices to force the segment into the triangulation. */
09845 conformingedge(endpoint1, endpoint2, newmark);
09846 } else {
09847 #endif /* not CDT_ONLY */
09848 #endif /* not REDUCED */
09849 /* Insert the segment directly into the triangulation. */
09850 constrainededge(&searchtri1, endpoint2, newmark);
09851 #ifndef REDUCED
09852 #ifndef CDT_ONLY
09853 }
09854 #endif /* not CDT_ONLY */
09855 #endif /* not REDUCED */
09856 }
09857
09858 /*****************************************************************************/
09859 /* */
09860 /* markhull() Cover the convex hull of a triangulation with shell edges. */
09861 /* */
|
|
||||||||||||
|
* Definition at line 5914 of file tlvisTrn_triangle.c. References point, shelle, and triangle. Referenced by insertsite().
05922 {
05923 setpointmark(triorg, shellemark);
05924 }
05925 if (pointmark(tridest) == 0) {
05926 setpointmark(tridest, shellemark);
05927 }
05928 /* Check if there's already a shell edge here. */
05929 tspivot(*tri, newshelle);
05930 if (newshelle.sh == dummysh) {
05931 /* Make new shell edge and initialize its vertices. */
05932 makeshelle(&newshelle);
05933 setsorg(newshelle, tridest);
05934 setsdest(newshelle, triorg);
05935 /* Bond new shell edge to the two triangles it is sandwiched between. */
05936 /* Note that the facing triangle `oppotri' might be equal to */
05937 /* `dummytri' (outer space), but the new shell edge is bonded to it */
05938 /* all the same. */
05939 tsbond(*tri, newshelle);
05940 sym(*tri, oppotri);
05941 ssymself(newshelle);
05942 tsbond(oppotri, newshelle);
05943 setmark(newshelle, shellemark);
05944 if (verbose > 2) {
05945 printf(" Inserting new ");
05946 printshelle(&newshelle);
05947 }
05948 } else {
05949 if (mark(newshelle) == 0) {
05950 setmark(newshelle, shellemark);
05951 }
05952 }
05953 }
05954
05955 /*****************************************************************************/
05956 /* */
05957 /* Terminology */
05958 /* */
|
|
||||||||||||||||||||||||
|
Definition at line 6156 of file tlvisTrn_triangle.c. References apex, areabound, badsegments, bond, checksegments, counterclockwise(), dest, dummysh, dummytri, DUPLICATEPOINT, eextras, elemattribute, ENCROACHINGPOINT, hullsize, incircle(), infpoint1, infpoint2, infpoint3, insertshelle(), insertsiteresult, lnext, lnextself, locate(), locateresult, lprev, lprevself, maketriangle(), mark, nobisect, ONEDGE, ONVERTEX, org, triedge::orient, OUTSIDE, point, poolalloc(), preciselocate(), printtriangle(), REAL, recenttri, sbond, setapex, setareabound, setdest, setelemattribute, setorg, setsdest, edge::sh, shelle, shellecopy, spivot, ssymself, SUCCESSFULPOINT, sym, symself, triedge::tri, triangle, triedgecopy, tsbond, tsdissolve, tspivot, vararea, verbose, and VIOLATINGPOINT.
06158 {
06159 struct triedge horiz;
06160 struct triedge top;
06161 struct triedge botleft, botright;
06162 struct triedge topleft, topright;
06163 struct triedge newbotleft, newbotright;
06164 struct triedge newtopright;
06165 struct triedge botlcasing, botrcasing;
06166 struct triedge toplcasing, toprcasing;
06167 struct triedge testtri;
06168 struct edge botlshelle, botrshelle;
06169 struct edge toplshelle, toprshelle;
06170 struct edge brokenshelle;
06171 struct edge checkshelle;
06172 struct edge rightedge;
06173 struct edge newedge;
06174 struct edge *encroached;
06175 point first;
06176 point leftpoint, rightpoint, botpoint, toppoint, farpoint;
06177 REAL attrib;
06178 REAL area;
06179 enum insertsiteresult success;
06180 enum locateresult intersect;
06181 int doflip;
06182 int mirrorflag;
06183 int i;
06184 triangle ptr; /* Temporary variable used by sym(). */
06185 shelle sptr; /* Temporary variable used by spivot() and tspivot(). */
06186
06187 if (verbose > 1) {
06188 printf(" Inserting (%.12g, %.12g).\n", insertpoint[0], insertpoint[1]);
06189 }
06190 if (splitedge == (struct edge *) NULL) {
06191 /* Find the location of the point to be inserted. Check if a good */
06192 /* starting triangle has already been provided by the caller. */
06193 if (searchtri->tri == (triangle *) NULL) {
06194 /* Find a boundary triangle. */
06195 horiz.tri = dummytri;
06196 horiz.orient = 0;
06197 symself(horiz);
06198 /* Search for a triangle containing `insertpoint'. */
06199 intersect = locate(insertpoint, &horiz);
06200 } else {
06201 /* Start searching from the triangle provided by the caller. */
06202 triedgecopy(*searchtri, horiz);
06203 intersect = preciselocate(insertpoint, &horiz);
06204 }
06205 } else {
06206 /* The calling routine provides the edge in which the point is inserted. */
06207 triedgecopy(*searchtri, horiz);
06208 intersect = ONEDGE;
06209 }
06210 if (intersect == ONVERTEX) {
06211 /* There's already a vertex there. Return in `searchtri' a triangle */
06212 /* whose origin is the existing vertex. */
06213 triedgecopy(horiz, *searchtri);
06214 triedgecopy(horiz, recenttri);
06215 return DUPLICATEPOINT;
06216 }
06217 if ((intersect == ONEDGE) || (intersect == OUTSIDE)) {
06218 /* The vertex falls on an edge or boundary. */
06219 if (checksegments && (splitedge == (struct edge *) NULL)) {
06220 /* Check whether the vertex falls on a shell edge. */
06221 tspivot(horiz, brokenshelle);
06222 if (brokenshelle.sh != dummysh) {
06223 /* The vertex falls on a shell edge. */
06224 if (segmentflaws) {
06225 if (nobisect == 0) {
06226 /* Add the shell edge to the list of encroached segments. */
06227 encroached = (struct edge *) poolalloc(&badsegments);
06228 shellecopy(brokenshelle, *encroached);
06229 } else if ((nobisect == 1) && (intersect == ONEDGE)) {
06230 /* This segment may be split only if it is an internal boundary. */
06231 sym(horiz, testtri);
06232 if (testtri.tri != dummytri) {
06233 /* Add the shell edge to the list of encroached segments. */
06234 encroached = (struct edge *) poolalloc(&badsegments);
06235 shellecopy(brokenshelle, *encroached);
06236 }
06237 }
06238 }
06239 /* Return a handle whose primary edge contains the point, */
06240 /* which has not been inserted. */
06241 triedgecopy(horiz, *searchtri);
06242 triedgecopy(horiz, recenttri);
06243 return VIOLATINGPOINT;
06244 }
06245 }
06246 /* Insert the point on an edge, dividing one triangle into two (if */
06247 /* the edge lies on a boundary) or two triangles into four. */
06248 lprev(horiz, botright);
06249 sym(botright, botrcasing);
06250 sym(horiz, topright);
06251 /* Is there a second triangle? (Or does this edge lie on a boundary?) */
06252 mirrorflag = topright.tri != dummytri;
06253 if (mirrorflag) {
06254 lnextself(topright);
06255 sym(topright, toprcasing);
06256 maketriangle(&newtopright);
06257 } else {
06258 /* Splitting the boundary edge increases the number of boundary edges. */
06259 hullsize++;
06260 }
06261 maketriangle(&newbotright);
06262
06263 /* Set the vertices of changed and new triangles. */
06264 org(horiz, rightpoint);
06265 dest(horiz, leftpoint);
06266 apex(horiz, botpoint);
06267 setorg(newbotright, botpoint);
06268 setdest(newbotright, rightpoint);
06269 setapex(newbotright, insertpoint);
06270 setorg(horiz, insertpoint);
06271 for (i = 0; i < eextras; i++) {
06272 /* Set the element attributes of a new triangle. */
06273 setelemattribute(newbotright, i, elemattribute(botright, i));
06274 }
06275 if (vararea) {
06276 /* Set the area constraint of a new triangle. */
06277 setareabound(newbotright, areabound(botright));
06278 }
06279 if (mirrorflag) {
06280 dest(topright, toppoint);
06281 setorg(newtopright, rightpoint);
06282 setdest(newtopright, toppoint);
06283 setapex(newtopright, insertpoint);
06284 setorg(topright, insertpoint);
06285 for (i = 0; i < eextras; i++) {
06286 /* Set the element attributes of another new triangle. */
06287 setelemattribute(newtopright, i, elemattribute(topright, i));
06288 }
06289 if (vararea) {
06290 /* Set the area constraint of another new triangle. */
06291 setareabound(newtopright, areabound(topright));
06292 }
06293 }
06294
06295 /* There may be shell edges that need to be bonded */
06296 /* to the new triangle(s). */
06297 if (checksegments) {
06298 tspivot(botright, botrshelle);
06299 if (botrshelle.sh != dummysh) {
06300 tsdissolve(botright);
06301 tsbond(newbotright, botrshelle);
06302 }
06303 if (mirrorflag) {
06304 tspivot(topright, toprshelle);
06305 if (toprshelle.sh != dummysh) {
06306 tsdissolve(topright);
06307 tsbond(newtopright, toprshelle);
06308 }
06309 }
06310 }
06311
06312 /* Bond the new triangle(s) to the surrounding triangles. */
06313 bond(newbotright, botrcasing);
06314 lprevself(newbotright);
06315 bond(newbotright, botright);
06316 lprevself(newbotright);
06317 if (mirrorflag) {
06318 bond(newtopright, toprcasing);
06319 lnextself(newtopright);
06320 bond(newtopright, topright);
06321 lnextself(newtopright);
06322 bond(newtopright, newbotright);
06323 }
06324
06325 if (splitedge != (struct edge *) NULL) {
06326 /* Split the shell edge into two. */
06327 setsdest(*splitedge, insertpoint);
06328 ssymself(*splitedge);
06329 spivot(*splitedge, rightedge);
06330 insertshelle(&newbotright, mark(*splitedge));
06331 tspivot(newbotright, newedge);
06332 sbond(*splitedge, newedge);
06333 ssymself(newedge);
06334 sbond(newedge, rightedge);
06335 ssymself(*splitedge);
06336 }
06337
06338 #ifdef SELF_CHECK
06339 if (counterclockwise(rightpoint, leftpoint, botpoint) < 0.0) {
06340 printf("Internal error in insertsite():\n");
06341 printf(" Clockwise triangle prior to edge point insertion (bottom).\n");
06342 }
06343 if (mirrorflag) {
06344 if (counterclockwise(leftpoint, rightpoint, toppoint) < 0.0) {
06345 printf("Internal error in insertsite():\n");
06346 printf(" Clockwise triangle prior to edge point insertion (top).\n");
06347 }
06348 if (counterclockwise(rightpoint, toppoint, insertpoint) < 0.0) {
06349 printf("Internal error in insertsite():\n");
06350 printf(" Clockwise triangle after edge point insertion (top right).\n"
06351 );
06352 }
06353 if (counterclockwise(toppoint, leftpoint, insertpoint) < 0.0) {
06354 printf("Internal error in insertsite():\n");
06355 printf(" Clockwise triangle after edge point insertion (top left).\n"
06356 );
06357 }
06358 }
06359 if (counterclockwise(leftpoint, botpoint, insertpoint) < 0.0) {
06360 printf("Internal error in insertsite():\n");
06361 printf(" Clockwise triangle after edge point insertion (bottom left).\n"
06362 );
06363 }
06364 if (counterclockwise(botpoint, rightpoint, insertpoint) < 0.0) {
06365 printf("Internal error in insertsite():\n");
06366 printf(
06367 " Clockwise triangle after edge point insertion (bottom right).\n");
06368 }
06369 #endif /* SELF_CHECK */
06370 if (verbose > 2) {
06371 printf(" Updating bottom left ");
06372 printtriangle(&botright);
06373 if (mirrorflag) {
06374 printf(" Updating top left ");
06375 printtriangle(&topright);
06376 printf(" Creating top right ");
06377 printtriangle(&newtopright);
06378 }
06379 printf(" Creating bottom right ");
06380 printtriangle(&newbotright);
06381 }
06382
06383 /* Position `horiz' on the first edge to check for */
06384 /* the Delaunay property. */
06385 lnextself(horiz);
06386 } else {
06387 /* Insert the point in a triangle, splitting it into three. */
06388 lnext(horiz, botleft);
06389 lprev(horiz, botright);
06390 sym(botleft, botlcasing);
06391 sym(botright, botrcasing);
06392 maketriangle(&newbotleft);
06393 maketriangle(&newbotright);
06394
06395 /* Set the vertices of changed and new triangles. */
06396 org(horiz, rightpoint);
06397 dest(horiz, leftpoint);
06398 apex(horiz, botpoint);
06399 setorg(newbotleft, leftpoint);
06400 setdest(newbotleft, botpoint);
06401 setapex(newbotleft, insertpoint);
06402 setorg(newbotright, botpoint);
06403 setdest(newbotright, rightpoint);
06404 setapex(newbotright, insertpoint);
06405 setapex(horiz, insertpoint);
06406 for (i = 0; i < eextras; i++) {
06407 /* Set the element attributes of the new triangles. */
06408 attrib = elemattribute(horiz, i);
06409 setelemattribute(newbotleft, i, attrib);
06410 setelemattribute(newbotright, i, attrib);
06411 }
06412 if (vararea) {
06413 /* Set the area constraint of the new triangles. */
06414 area = areabound(horiz);
06415 setareabound(newbotleft, area);
06416 setareabound(newbotright, area);
06417 }
06418
06419 /* There may be shell edges that need to be bonded */
06420 /* to the new triangles. */
06421 if (checksegments) {
06422 tspivot(botleft, botlshelle);
06423 if (botlshelle.sh != dummysh) {
06424 tsdissolve(botleft);
06425 tsbond(newbotleft, botlshelle);
06426 }
06427 tspivot(botright, botrshelle);
06428 if (botrshelle.sh != dummysh) {
06429 tsdissolve(botright);
06430 tsbond(newbotright, botrshelle);
06431 }
06432 }
06433
06434 /* Bond the new triangles to the surrounding triangles. */
06435 bond(newbotleft, botlcasing);
06436 bond(newbotright, botrcasing);
06437 lnextself(newbotleft);
06438 lprevself(newbotright);
06439 bond(newbotleft, newbotright);
06440 lnextself(newbotleft);
06441 bond(botleft, newbotleft);
06442 lprevself(newbotright);
06443 bond(botright, newbotright);
06444
06445 #ifdef SELF_CHECK
06446 if (counterclockwise(rightpoint, leftpoint, botpoint) < 0.0) {
06447 printf("Internal error in insertsite():\n");
06448 printf(" Clockwise triangle prior to point insertion.\n");
06449 }
06450 if (counterclockwise(rightpoint, leftpoint, insertpoint) < 0.0) {
06451 printf("Internal error in insertsite():\n");
06452 printf(" Clockwise triangle after point insertion (top).\n");
06453 }
06454 if (counterclockwise(leftpoint, botpoint, insertpoint) < 0.0) {
06455 printf("Internal error in insertsite():\n");
06456 printf(" Clockwise triangle after point insertion (left).\n");
06457 }
06458 if (counterclockwise(botpoint, rightpoint, insertpoint) < 0.0) {
06459 printf("Internal error in insertsite():\n");
06460 printf(" Clockwise triangle after point insertion (right).\n");
06461 }
06462 #endif /* SELF_CHECK */
06463 if (verbose > 2) {
06464 printf(" Updating top ");
06465 printtriangle(&horiz);
06466 printf(" Creating left ");
06467 printtriangle(&newbotleft);
06468 printf(" Creating right ");
06469 printtriangle(&newbotright);
06470 }
06471 }
06472
06473 /* The insertion is successful by default, unless an encroached */
06474 /* edge is found. */
06475 success = SUCCESSFULPOINT;
06476 /* Circle around the newly inserted vertex, checking each edge opposite */
06477 /* it for the Delaunay property. Non-Delaunay edges are flipped. */
06478 /* `horiz' is always the edge being checked. `first' marks where to */
06479 /* stop circling. */
06480 org(horiz, first);
06481 rightpoint = first;
06482 dest(horiz, leftpoint);
06483 /* Circle until finished. */
06484 while (1) {
06485 /* By default, the edge will be flipped. */
06486 doflip = 1;
06487 if (checksegments) {
06488 /* Check for a segment, which cannot be flipped. */
06489 tspivot(horiz, checkshelle);
06490 if (checkshelle.sh != dummysh) {
06491 /* The edge is a segment and cannot be flipped. */
06492 doflip = 0;
06493 #ifndef CDT_ONLY
06494 if (segmentflaws) {
06495 /* Does the new point encroach upon this segment? */
06496 if (checkedge4encroach(&checkshelle)) {
06497 success = ENCROACHINGPOINT;
06498 }
06499 }
06500 #endif /* not CDT_ONLY */
06501 }
06502 }
06503 if (doflip) {
06504 /* Check if the edge is a boundary edge. */
06505 sym(horiz, top);
06506 if (top.tri == dummytri) {
06507 /* The edge is a boundary edge and cannot be flipped. */
06508 doflip = 0;
06509 } else {
06510 /* Find the point on the other side of the edge. */
06511 apex(top, farpoint);
06512 /* In the incremental Delaunay triangulation algorithm, any of */
06513 /* `leftpoint', `rightpoint', and `farpoint' could be vertices */
06514 /* of the triangular bounding box. These vertices must be */
06515 /* treated as if they are infinitely distant, even though their */
06516 /* "coordinates" are not. */
06517 if ((leftpoint == infpoint1) || (leftpoint == infpoint2)
06518 || (leftpoint == infpoint3)) {
06519 /* `leftpoint' is infinitely distant. Check the convexity of */
06520 /* the boundary of the triangulation. 'farpoint' might be */
06521 /* infinite as well, but trust me, this same condition */
06522 /* should be applied. */
06523 doflip = counterclockwise(insertpoint, rightpoint, farpoint) > 0.0;
06524 } else if ((rightpoint == infpoint1) || (rightpoint == infpoint2)
06525 || (rightpoint == infpoint3)) {
06526 /* `rightpoint' is infinitely distant. Check the convexity of */
06527 /* the boundary of the triangulation. 'farpoint' might be */
06528 /* infinite as well, but trust me, this same condition */
06529 /* should be applied. */
06530 doflip = counterclockwise(farpoint, leftpoint, insertpoint) > 0.0;
06531 } else if ((farpoint == infpoint1) || (farpoint == infpoint2)
06532 || (farpoint == infpoint3)) {
06533 /* `farpoint' is infinitely distant and cannot be inside */
06534 /* the circumcircle of the triangle `horiz'. */
06535 doflip = 0;
06536 } else {
06537 /* Test whether the edge is locally Delaunay. */
06538 doflip = incircle(leftpoint, insertpoint, rightpoint, farpoint)
06539 > 0.0;
06540 }
06541 if (doflip) {
06542 /* We made it! Flip the edge `horiz' by rotating its containing */
06543 /* quadrilateral (the two triangles adjacent to `horiz'). */
06544 /* Identify the casing of the quadrilateral. */
06545 lprev(top, topleft);
06546 sym(topleft, toplcasing);
06547 lnext(top, topright);
06548 sym(topright, toprcasing);
06549 lnext(horiz, botleft);
06550 sym(botleft, botlcasing);
06551 lprev(horiz, botright);
06552 sym(botright, botrcasing);
06553 /* Rotate the quadrilateral one-quarter turn counterclockwise. */
06554 bond(topleft, botlcasing);
06555 bond(botleft, botrcasing);
06556 bond(botright, toprcasing);
06557 bond(topright, toplcasing);
06558 if (checksegments) {
06559 /* Check for shell edges and rebond them to the quadrilateral. */
06560 tspivot(topleft, toplshelle);
06561 tspivot(botleft, botlshelle);
06562 tspivot(botright, botrshelle);
06563 tspivot(topright, toprshelle);
06564 if (toplshelle.sh == dummysh) {
06565 tsdissolve(topright);
06566 } else {
06567 tsbond(topright, toplshelle);
06568 }
06569 if (botlshelle.sh == dummysh) {
06570 tsdissolve(topleft);
06571 } else {
06572 tsbond(topleft, botlshelle);
06573 }
06574 if (botrshelle.sh == dummysh) {
06575 tsdissolve(botleft);
06576 } else {
06577 tsbond(botleft, botrshelle);
06578 }
06579 if (toprshelle.sh == dummysh) {
06580 tsdissolve(botright);
06581 } else {
06582 tsbond(botright, toprshelle);
06583 }
06584 }
06585 /* New point assignments for the rotated quadrilateral. */
06586 setorg(horiz, farpoint);
06587 setdest(horiz, insertpoint);
06588 setapex(horiz, rightpoint);
06589 setorg(top, insertpoint);
06590 setdest(top, farpoint);
06591 setapex(top, leftpoint);
06592 for (i = 0; i < eextras; i++) {
06593 /* Take the average of the two triangles' attributes. */
06594 attrib = 0.5 * (elemattribute(top, i) + elemattribute(horiz, i));
06595 setelemattribute(top, i, attrib);
06596 setelemattribute(horiz, i, attrib);
06597 }
06598 if (vararea) {
06599 if ((areabound(top) <= 0.0) || (areabound(horiz) <= 0.0)) {
06600 area = -1.0;
06601 } else {
06602 /* Take the average of the two triangles' area constraints. */
06603 /* This prevents small area constraints from migrating a */
06604 /* long, long way from their original location due to flips. */
06605 area = 0.5 * (areabound(top) + areabound(horiz));
06606 }
06607 setareabound(top, area);
06608 setareabound(horiz, area);
06609 }
06610 #ifdef SELF_CHECK
06611 if (insertpoint != (point) NULL) {
06612 if (counterclockwise(leftpoint, insertpoint, rightpoint) < 0.0) {
06613 printf("Internal error in insertsite():\n");
06614 printf(" Clockwise triangle prior to edge flip (bottom).\n");
06615
|