| /* For copyright information, see olden_v1.0/COPYRIGHT */ |
| |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include "defines.h" |
| |
| #if defined(__linux__) |
| #include <malloc.h> |
| #endif |
| |
| |
| VERTEX_PTR *vp ; |
| struct VERTEX *va ; |
| EDGE_PTR *next ; |
| VERTEX_PTR *org ; |
| int num_vertices, num_edgeparts, stack_size ; |
| int to_lincoln, to_off, to_3d_out, to_color, voronoi, delaunay, interactive, ahost; |
| char *see; |
| int NumNodes, NDim; |
| |
| int flag; |
| |
| QUAD_EDGE connect_left(a, b) |
| QUAD_EDGE a,b; |
| { |
| VERTEX_PTR t1,t2; |
| register QUAD_EDGE ans,lnexta; |
| |
| /*printf("begin connect_left\n");*/ |
| t1=dest(a); |
| lnexta=lnext(a); |
| t2=orig(b); |
| ans = makeedge(t1,t2/*dest(a), orig(b)*/); |
| splice(ans, lnexta); |
| splice(sym(ans), b); |
| /*printf("end connect_left\n");*/ |
| return(ans); |
| } |
| |
| QUAD_EDGE connect_right(a, b) |
| QUAD_EDGE a,b; |
| { |
| VERTEX_PTR t1,t2; |
| register QUAD_EDGE ans, oprevb; |
| |
| /*printf("begin connect_right\n");*/ |
| t1=dest(a); |
| t2=orig(b); |
| oprevb=oprev(b); |
| ans = makeedge(t1,t2/*dest(a), orig(b)*/); |
| splice(ans, sym(a)); |
| splice(sym(ans), oprevb); |
| /*printf("end connect_right\n");*/ |
| return(ans); |
| } |
| |
| void deleteedge(e) |
| /*disconnects e from the rest of the structure and destroys it. */ |
| QUAD_EDGE e; |
| { |
| QUAD_EDGE f; |
| /*printf("begin delete_edge 0x%x\n",e);*/ |
| f=oprev(e); |
| splice(e, f); |
| f=oprev(sym(e)); |
| splice(sym(e),f); |
| free_edge(e); |
| /*printf("end delete_edge\n");*/ |
| } |
| |
| /****************************************************************/ |
| /* Top-level Delaunay Triangulation Procedure */ |
| /****************************************************************/ |
| |
| QUAD_EDGE build_delaunay_triangulation(tree,extra) |
| /* builds delaunay triangulation. |
| va is an array of vertices, from 0 to size. Each vertex consists of |
| a vector and a data pointer. edge is a pointer to an |
| edge on the convex hull of the constructed delaunay triangulation. */ |
| |
| VERTEX_PTR tree,extra; |
| { |
| EDGE_PAIR retval; |
| |
| retval=build_delaunay(tree,extra); |
| return retval.left; |
| } |
| |
| VERTEX_PTR get_low(tree) |
| register VERTEX_PTR tree; |
| { |
| register VERTEX_PTR temp; |
| while((temp=tree->left)) tree=temp; /* 3% load penalty */ |
| return tree; |
| } |
| |
| /****************************************************************/ |
| /* Recursive Delaunay Triangulation Procedure */ |
| /* Contains modifications for axis-switching division. */ |
| /****************************************************************/ |
| |
| EDGE_PAIR build_delaunay(VERTEX_PTR tree, VERTEX_PTR extra) |
| { |
| QUAD_EDGE a,b,c,ldo,rdi,ldi,rdo; |
| EDGE_PAIR retval; |
| register VERTEX_PTR maxx, minx; |
| VERTEX_PTR s1, s2, s3; |
| |
| EDGE_PAIR delleft, delright; |
| |
| if (tree && tree->right) /* <----------------------- 3% load penalty */ |
| { |
| /* more than three elements; do recursion */ |
| minx = get_low(tree); maxx = extra; |
| delright = build_delaunay(tree->right,extra); |
| delleft = build_delaunay(tree->left, tree); |
| ldo = delleft.left; ldi=delleft.right; |
| rdi=delright.left; rdo=delright.right; |
| retval=do_merge(ldo, ldi, rdi, rdo); |
| ldo = retval.left; |
| rdo = retval.right; |
| while (orig(ldo) != minx) {ldo = rprev(ldo); } |
| while (orig(rdo) != maxx) {rdo = lprev(rdo); } |
| retval.left = ldo; |
| retval.right = rdo; |
| } |
| else if (!tree) |
| { |
| printf("ERROR: Only 1 point!\n"); |
| exit(-1); |
| } |
| else if (!tree->left) { /* two points */ |
| a = makeedge(tree, extra); |
| retval.left = a; |
| retval.right = sym(a); |
| } |
| else { /* tree->left, !tree->right */ /* three points */ |
| /* 3 cases: triangles of 2 orientations, and 3 points on a line. */ |
| s1 = tree->left; |
| s2 = tree; |
| s3 = extra; |
| a = makeedge(s1, s2); |
| b = makeedge(s2, s3); |
| splice(sym(a), b); |
| c = connect_left(b, a); |
| if (ccw(s1, s3, s2)) { |
| retval.left = sym(c); |
| retval.right = c; |
| } |
| else { |
| retval.left = a; |
| retval.right = sym(b); |
| if (!ccw(s1, s2, s3)) deleteedge(c); /* colinear */ |
| } |
| } |
| return retval; |
| } |
| |
| /****************************************************************/ |
| /* Quad-edge storage allocation */ |
| /****************************************************************/ |
| QUAD_EDGE next_edge, avail_edge; |
| |
| #define NYL NULL |
| |
| void delete_all_edges() { next_edge= 0; avail_edge = NYL;} |
| |
| #if defined(__APPLE__) || defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__MINGW32__) |
| #define MEMALIGN_IS_NOT_AVAILABLE |
| #endif |
| |
| /* memalign() on my SGI doesn't work. Thus, I have to write my own */ |
| void* myalign(int align_size, int alloc_size) |
| { |
| #ifdef MEMALIGN_IS_NOT_AVAILABLE |
| char* base = (char*)malloc(alloc_size + align_size); |
| #else |
| char* base = (char*)memalign(align_size, alloc_size); |
| #endif |
| void *Result; |
| if (base == NULL){ |
| printf("myalign() failed\n"); |
| exit(-1); |
| } |
| #ifdef MEMALIGN_IS_NOT_AVAILABLE |
| return (void*)(base + align_size - ((uptrint)base % align_size)); |
| #else |
| return base; |
| #endif |
| } |
| |
| |
| |
| QUAD_EDGE alloc_edge() { |
| QUAD_EDGE ans; |
| |
| if (avail_edge == NYL) { |
| ans = (QUAD_EDGE)myalign(4*(sizeof(struct edge_rec)), |
| 4*(sizeof(struct edge_rec))); |
| if ((uptrint)ans & ANDF) { |
| printf("Aborting in alloc_edge, ans = 0x%p\n", ans); |
| exit(-1); |
| } |
| } else |
| ans = (QUAD_EDGE) avail_edge, avail_edge = onext(avail_edge); |
| |
| ans[0].wasseen = 0; |
| ans[1].wasseen = 0; |
| ans[2].wasseen = 0; |
| ans[3].wasseen = 0; |
| return ans; |
| } |
| |
| void free_edge(QUAD_EDGE e) { |
| e = (QUAD_EDGE) ((uptrint) e ^ ((uptrint) e & ANDF)); |
| onext(e) = avail_edge; |
| avail_edge = e; |
| } |
| |
| |
| |
| /****************************************************************/ |
| /* Geometric primitives */ |
| /****************************************************************/ |
| |
| BOOLEAN incircle(a,b,c,d) |
| /* incircle, as in the Guibas-Stolfi paper. */ |
| VERTEX_PTR a,b,c,d; |
| { |
| double adx, ady, bdx, bdy, cdx, cdy, dx, dy, anorm, bnorm, cnorm, dnorm; |
| double dret ; |
| VERTEX_PTR loc_a,loc_b,loc_c,loc_d; |
| |
| /*if (flag) printf("incircle: 0x%x,0x%x,0x%x,0x%x\n",a,b,c,d);*/ |
| loc_d = d; |
| dx = X(loc_d); dy = Y(loc_d); dnorm = NORM(loc_d); |
| loc_a = a; |
| adx = X(loc_a) - dx; ady = Y(loc_a) - dy; anorm = NORM(loc_a); /* <--- 4% load penalty */ |
| loc_b = b; |
| bdx = X(loc_b) - dx; bdy = Y(loc_b) - dy; bnorm = NORM(loc_b); /* <--- 5% load penalty */ |
| loc_c = c; |
| cdx = X(loc_c) - dx; cdy = Y(loc_c) - dy; cnorm = NORM(loc_c); |
| /*if (flag) printf("adx=%f,bdx=%f,cdx=%f\n",adx,bdx,cdx);*/ |
| dret = (anorm - dnorm) * (bdx * cdy - bdy * cdx); |
| dret += (bnorm - dnorm) * (cdx * ady - cdy * adx); |
| dret += (cnorm - dnorm) * (adx * bdy - ady * bdx); |
| /*if (flag) printf("Incircle: %f\n", dret);*/ |
| return 0.0 < dret; |
| } |
| |
| /* TRUE iff A, B, C form a counterclockwise oriented triangle */ |
| BOOLEAN ccw(VERTEX_PTR a, VERTEX_PTR b, VERTEX_PTR c) { |
| double dret ; |
| double xa,ya,xb,yb,xc,yc; |
| VERTEX_PTR loc_a,loc_b,loc_c; |
| loc_a = a; |
| xa=X(loc_a); ya=Y(loc_a); |
| loc_b = b; |
| xb=X(loc_b); yb=Y(loc_b); /*<----------------------------- 10 % load penalty */ |
| loc_c = c; |
| xc=X(loc_c); yc=Y(loc_c); |
| /*if (flag) printf("CCW:xa=%f,xb=%f,xd=%f\n",xa,xb,xc);*/ |
| /*if (flag) printf("CCW:ya=%f,yb=%f,yd=%f\n",ya,yb,yc);*/ |
| dret = (xa-xc)*(yb-yc) - (xb-xc)*(ya-yc); |
| /*if (flag) printf("ccw: %f\n", dret);*/ |
| return dret > 0.0; |
| } |
| |
| /****************************************************************/ |
| /* Quad-edge manipulation primitives */ |
| /****************************************************************/ |
| QUAD_EDGE makeedge(origin, destination) |
| VERTEX_PTR origin, destination; |
| { |
| register QUAD_EDGE temp, ans; |
| temp = alloc_edge(); |
| ans = temp; |
| |
| onext(temp) = ans; |
| orig(temp) = origin; |
| temp = (QUAD_EDGE) ((uptrint) temp+SIZE); |
| onext(temp) = (QUAD_EDGE) ((uptrint) ans + 3*SIZE); |
| temp = (QUAD_EDGE) ((uptrint) temp+SIZE); |
| onext(temp) = (QUAD_EDGE) ((uptrint) ans + 2*SIZE); |
| orig(temp) = destination; |
| temp = (QUAD_EDGE) ((uptrint) temp+SIZE); |
| onext(temp) = (QUAD_EDGE) ((uptrint) ans + 1*SIZE); |
| |
| /*printf("Edge made @ 0x%x\n",ans);*/ |
| /*dump_quad(ans);*/ |
| return(ans); |
| } |
| |
| void splice(a,b) |
| QUAD_EDGE a, b; |
| { |
| QUAD_EDGE alpha, beta, temp; |
| QUAD_EDGE t1; |
| |
| /*printf("begin splice 0x%x,0x%x\n",a,b);*/ |
| /*dump_quad(a); dump_quad(b);*/ |
| alpha = rot(onext(a)); |
| beta = rot(onext(b)); /*<---------------------------------- 15% load miss penalty */ |
| /*dump_quad(alpha); dump_quad(beta);*/ |
| t1 = onext(beta); /*<---------------------------------- 3% load miss penalty */ |
| temp = onext(alpha); /*<---------------------------------- 11% load miss penalty */ |
| onext(alpha) = t1; |
| /*printf("Writing 0x%x at onext of 0x%x\n",t1,alpha);*/ |
| |
| onext(beta) = temp; |
| /*printf("Writing 0x%x at onext of 0x%x\n",temp,beta);*/ |
| temp = onext(a); |
| t1 = onext(b); |
| onext(b) = temp; |
| onext(a) = t1; |
| /*printf("Wrote 0x%x at onext of 0x%x\n",temp,b);*/ |
| /*printf("Wrote 0x%x at onext of 0x%x\n",t1,a);*/ |
| /*printf("End splice\n");*/ |
| } |
| |
| void swapedge(e) |
| QUAD_EDGE e; |
| { |
| QUAD_EDGE a,b,syme,lnexttmp; |
| VERTEX_PTR a1,b1; |
| |
| /*printf("begin swapedge\n");*/ |
| a = oprev(e); |
| syme = sym(e); |
| b = oprev(syme); |
| splice(e, a); |
| splice(syme, b); |
| lnexttmp = lnext(a); |
| splice(e, lnexttmp); |
| lnexttmp = lnext(b); |
| splice(syme, lnexttmp); |
| a1 = dest(a); |
| b1 = dest(b); |
| orig(e) = a1; |
| dest(e) = b1; |
| /*printf("end swapedge\n");*/ |
| } |
| |
| /****************************************************************/ |
| /* The Merge Procedure. */ |
| /****************************************************************/ |
| /*#define valid(l) ccw(orig(basel), dest(l), dest(basel))*/ |
| |
| int valid(l,basel) |
| QUAD_EDGE l,basel; |
| { |
| register VERTEX_PTR t1,t2,t3; |
| |
| /*printf("valid:0x%x,0x%x\n",l,basel);*/ |
| |
| t1=orig(basel); |
| t3=dest(basel); |
| |
| t2=dest(l); /* <------------------------------------------------- 11 % load penalty */ |
| return ccw(t1,t2,t3); |
| } |
| |
| void dump_quad(ptr) |
| QUAD_EDGE ptr; |
| { |
| int i; |
| QUAD_EDGE j; |
| VERTEX_PTR v; |
| |
| ptr = (QUAD_EDGE) ((uptrint) ptr & ~ANDF); |
| printf("Entered DUMP_QUAD: ptr=0x%p\n",ptr); |
| for (i=0; i<4; i++) |
| { |
| j=onext(((QUAD_EDGE) (ptr+i))); |
| v = orig(j); |
| printf("DUMP_QUAD: ptr=0x%p onext=0x%p,v=0x%p\n",ptr+i,j,v); |
| } |
| } |
| |
| |
| |
| |
| |
| |
| EDGE_PAIR do_merge(QUAD_EDGE ldo, QUAD_EDGE ldi, QUAD_EDGE rdi, QUAD_EDGE rdo) |
| { |
| int rvalid, lvalid; |
| register QUAD_EDGE basel,lcand,rcand,t; |
| VERTEX_PTR t1,t2; |
| |
| /*printf("merge\n");*/ |
| while (1) { |
| VERTEX_PTR t3=orig(rdi); |
| /*loc=rdi;*/ |
| /*t3=orig(loc);*/ |
| |
| t1=orig(ldi); |
| t2=dest(ldi); |
| /*loc = ldi;*/ |
| /*t1 = orig(loc);*/ |
| /*t2 = dest(loc);*/ |
| |
| while (ccw(t1,t2,t3/*orig(ldi), dest(ldi), orig(rdi)*/)) |
| { |
| ldi = lnext(ldi); |
| /*ldi = lnext(loc);*/ |
| /*loc = ldi;*/ |
| |
| t1=orig(ldi); |
| t2=dest(ldi); |
| /*t1 = orig(loc);*/ |
| /*t2 = dest(loc);*/ |
| } |
| /*loc = rdi;*/ |
| |
| t2=dest(rdi); |
| /*t2 = dest(loc);*/ |
| |
| if (ccw(t2,t3,t1/*dest(rdi), orig(rdi), orig(ldi)*/)) |
| { rdi = rprev(rdi); } |
| /*{ rdi = rprev(loc); }*/ |
| else { break; } |
| } |
| |
| basel = connect_left(sym(rdi), ldi); |
| |
| /*loc = basel;*/ |
| |
| lcand = rprev(basel); |
| rcand = oprev(basel); |
| t1 = orig(basel); |
| t2 = dest(basel); |
| /*lcand = rprev(loc);*/ |
| /*rcand = oprev(loc);*/ |
| /*t1 = orig(loc);*/ |
| /*t2 = dest(loc);*/ |
| |
| if (t1/*orig(basel)*/ == orig(rdo)) rdo = basel; |
| if (t2/*dest(basel)*/ == orig(ldo)) ldo = sym(basel); |
| |
| while (1) { |
| VERTEX_PTR v1,v2,v3,v4; |
| |
| /*printf("valid site 1,lcand=0x%x,basel=0x%x\n",lcand,basel);*/ |
| /*dump_quad(lcand);*/ |
| t=onext(lcand); |
| if (valid(t,basel)) { |
| v4=orig(basel); |
| |
| /*loc = lcand;*/ |
| v1=dest(lcand); |
| v3=orig(lcand); |
| /*v1=dest(loc);*/ |
| /*v3=orig(loc);*/ |
| |
| v2=dest(t); |
| while (incircle(v1,v2,v3,v4 |
| /*dest(lcand), dest(t), orig(lcand), orig(basel)*/)) |
| { |
| deleteedge(lcand); |
| lcand = t; |
| |
| /*loc = lcand;*/ |
| t = onext(lcand); |
| v1=dest(lcand); |
| v3=orig(lcand); |
| /*t = onext(loc);*/ |
| /*v1=dest(loc);*/ |
| /*v3=orig(loc);*/ |
| |
| v2=dest(t); /* <---- 3% load penalty */ |
| } |
| } |
| |
| /*printf("valid site 2\n");*/ |
| t=oprev(rcand); |
| if (valid(t,basel)) { |
| v4=dest(basel); |
| v1=dest(t); |
| v2=dest(rcand); |
| v3=orig(rcand); |
| while (incircle(v1,v2,v3,v4 |
| /*dest(t), dest(rcand), orig(rcand), dest(basel)*/)) |
| { |
| deleteedge(rcand); |
| rcand = t; |
| t = oprev(rcand); |
| v2=dest(rcand); |
| v3=orig(rcand); |
| v1=dest(t); /* <--- 4% load penalty */ |
| } |
| } |
| |
| |
| /*printf("Valid sites 3,4\n");*/ |
| lvalid = valid(lcand,basel); |
| /*printf("Valid sites 3,4\n");*/ |
| rvalid = valid(rcand,basel); |
| |
| if ((! lvalid) && (! rvalid)) |
| { |
| EDGE_PAIR retval; |
| retval.left = ldo; retval.right = rdo; return retval; |
| } |
| |
| v1=dest(lcand); |
| v2=orig(lcand); |
| v3=orig(rcand); |
| v4=dest(rcand); |
| |
| if (!lvalid || |
| (rvalid && incircle(v1,v2,v3,v4 |
| /*dest(lcand), orig(lcand), |
| orig(rcand), dest(rcand)*/))) |
| { |
| basel = connect_left(rcand, sym(basel)); |
| rcand = lnext(sym(basel)); |
| } |
| else |
| { |
| basel = sym(connect_right(lcand, basel)); |
| lcand = rprev(basel); |
| } |
| } |
| } |
| |
| |
| #define CONST_m1 10000 |
| #define CONST_b 31415821 |
| #define RANGE 100 |
| |
| int loop = 0, randum = 1, filein = 0 , fileout = 1, statistics = 0; |
| |
| void in_order(tree) |
| VERTEX_PTR tree; |
| { |
| VERTEX_PTR tleft, tright; |
| double x, y; |
| |
| if (!tree) { |
| printf("NULL\n"); |
| return; |
| } |
| |
| x = X(tree); |
| y = Y(tree); |
| printf("X=%f, Y=%f\n",x, y); |
| tleft = tree->left; |
| in_order(tleft); |
| tright = tree->right; |
| in_order(tright); |
| } |
| |
| int mult(int p, int q) |
| { |
| int p1, p0, q1, q0; |
| |
| p1=p/CONST_m1; p0=p%CONST_m1; |
| q1=q/CONST_m1; q0=q%CONST_m1; |
| return (((p0*q1+p1*q0) % CONST_m1)*CONST_m1+p0*q0); |
| } |
| |
| int skiprand(int seed, int n) |
| /* Generate the nth random # */ |
| { |
| for (; n; n--) seed=myrandom(seed); |
| return seed; |
| } |
| |
| int myrandom(int seed) |
| { |
| seed = (mult(seed,CONST_b)+1); |
| return seed; |
| } |
| |
| |
| |
| void print_extra(VERTEX_PTR extra) { |
| double x, y; |
| x = X(extra); |
| y = Y(extra); |
| printf("X=%f, Y=%f\n",x, y); |
| } |
| |
| int main(int argc, char **argv) { |
| struct EDGE_STACK *my_stack; |
| struct get_point point, extra; |
| QUAD_EDGE edge; |
| int n, retained; |
| to_lincoln = to_off = to_3d_out = to_color = 0; |
| voronoi = delaunay = 1; interactive = ahost = 0 ; |
| retained = 0; |
| |
| printf("argc = %d\n",argc); |
| n = dealwithargs(argc, argv); |
| |
| /* delete_all_edges();*/ |
| if (1) { |
| printf("getting %d points\n", n); |
| extra=get_points(1,1.0,n,1023,NumNodes-1,1); |
| point=get_points(n-1,extra.curmax,n-1,extra.seed,0,NumNodes); |
| printf("Done getting points\n"); |
| num_vertices = n + 1; |
| my_stack=allocate_stack(num_vertices); |
| if (flag) in_order(point.v); |
| if (flag) print_extra(extra.v); |
| printf("Doing voronoi on %d nodes\n", n); |
| |
| edge=build_delaunay_triangulation(point.v,extra.v); |
| |
| if (flag) output_voronoi_diagram(edge,n,my_stack); |
| } |
| /* delete_all_edges();*/ |
| return 0; |
| } |
| |
| struct EDGE_STACK *allocate_stack(int num_vertice) |
| { |
| struct EDGE_STACK *my_stack; |
| |
| num_edgeparts = 12*num_vertice; |
| my_stack = (struct EDGE_STACK *)malloc(sizeof(struct EDGE_STACK)); |
| my_stack->elts = (QUAD_EDGE *)malloc(num_edgeparts * sizeof(QUAD_EDGE)); |
| my_stack->stack_size = num_edgeparts/2; |
| return my_stack; |
| } |
| |
| void free_all(cont,my_stack) |
| int cont; |
| struct EDGE_STACK *my_stack; |
| { |
| free(my_stack->elts); |
| free(my_stack); |
| } |
| |
| struct get_point get_points(int n, double curmax,int i, int seed, |
| int processor, int numnodes) |
| { |
| VERTEX_PTR node; |
| struct get_point point; |
| int j; |
| |
| //printf("seed = %d %f %d %d %d %d\n", n, curmax, i, seed, processor, numnodes); |
| |
| if (n<1) { |
| point.v = NULL; |
| point.curmax=curmax; |
| point.seed = seed; |
| return point; |
| } |
| /*printf("Get points: %d, %f, %d\n",n,curmax,processor);*/ |
| point = get_points(n/2,curmax,i,seed,processor+numnodes/2,numnodes/2); |
| /*printf("rec call n=%d\n",n);*/ |
| i -= n/2; |
| |
| j = NumNodes - ((NumNodes-1)/2); |
| |
| node = (VERTEX_PTR) malloc(sizeof(struct VERTEX)); |
| |
| /*printf("Get points past alloc,n=%d\n",n);*/ |
| //printf("%f\n", (double)point.seed); |
| X(node) = point.curmax * exp(log(drand(point.seed))/i); |
| Y(node) = drand(point.seed); |
| NORM(node) = X(node)*X(node) + Y(node)*Y(node); |
| node->right = point.v; |
| /*printf("node = 0x%x\n",node);*/ |
| point = get_points(n/2,X(node),i-1,point.seed, |
| processor,numnodes/2); |
| node->left = point.v; |
| point.v = node; |
| return point; |
| } |
| |
| |
| /****************************************************************/ |
| /* Voronoi Diagram Routines. */ |
| /****************************************************************/ |
| |
| /****************************************************************/ |
| /* Graph Traversal Routines */ |
| /****************************************************************/ |
| |
| QUAD_EDGE pop_edge(struct EDGE_STACK *x) { |
| int a=x->ptr--; |
| return (x)->elts[a]; |
| } |
| |
| void push_edge(struct EDGE_STACK *stack, QUAD_EDGE edge) { |
| register int a; |
| /*printf("pushing edge \n");*/ |
| if (stack->ptr == stack->stack_size) { |
| printf("cannot push onto stack: stack is too large\n"); |
| } |
| else { |
| a = stack->ptr; |
| a++; |
| stack->ptr = a; |
| stack->elts[a] = edge; |
| } |
| } |
| |
| void push_ring(struct EDGE_STACK *stack, QUAD_EDGE edge) { |
| QUAD_EDGE nex; |
| nex = onext(edge); |
| while (nex != edge) { |
| if (seen(nex) == 0) { |
| seen(nex) = 1; |
| push_edge(stack, nex); |
| } |
| nex = onext(nex); |
| } |
| } |
| |
| void push_nonzero_ring(stack, edge) |
| struct EDGE_STACK *stack; |
| QUAD_EDGE edge; |
| { |
| QUAD_EDGE nex; |
| nex = onext(edge); |
| while (nex != edge) { |
| if (seen(nex) != 0) { |
| seen(nex) = 0; |
| push_edge(stack, nex); |
| } |
| nex = onext(nex); |
| } |
| } |
| |
| void zero_seen(my_stack,edge) |
| QUAD_EDGE edge; |
| struct EDGE_STACK *my_stack; |
| { |
| my_stack->ptr = 0; |
| push_nonzero_ring(my_stack, edge); |
| while (my_stack->ptr != 0) { |
| edge = pop_edge(my_stack); |
| push_nonzero_ring(my_stack, sym(edge)); |
| } |
| } |