[666] | 1 | |
---|
| 2 | /*** VORONOI.C ***/ |
---|
| 3 | |
---|
| 4 | #include "vdefs.h" |
---|
| 5 | |
---|
| 6 | extern Site * bottomsite ; |
---|
| 7 | extern Halfedge * ELleftend, * ELrightend ; |
---|
| 8 | |
---|
| 9 | /*** implicit parameters: nsites, sqrt_nsites, xmin, xmax, ymin, ymax, |
---|
| 10 | : deltax, deltay (can all be estimates). |
---|
| 11 | : Performance suffers if they are wrong; better to make nsites, |
---|
| 12 | : deltax, and deltay too big than too small. (?) |
---|
| 13 | ***/ |
---|
| 14 | |
---|
| 15 | void |
---|
| 16 | voronoi(Site *(*nextsite)(void)) |
---|
| 17 | { |
---|
| 18 | Site * newsite, * bot, * top, * temp, * p, * v ; |
---|
| 19 | Point newintstar ; |
---|
| 20 | int pm ; |
---|
| 21 | Halfedge * lbnd, * rbnd, * llbnd, * rrbnd, * bisector ; |
---|
| 22 | Edge * e ; |
---|
| 23 | |
---|
| 24 | PQinitialize() ; |
---|
| 25 | bottomsite = (*nextsite)() ; |
---|
| 26 | out_site(bottomsite) ; |
---|
| 27 | ELinitialize() ; |
---|
| 28 | newsite = (*nextsite)() ; |
---|
| 29 | while (1) |
---|
| 30 | { |
---|
| 31 | if(!PQempty()) |
---|
| 32 | { |
---|
| 33 | newintstar = PQ_min() ; |
---|
| 34 | } |
---|
| 35 | if (newsite != (Site *)NULL && (PQempty() |
---|
| 36 | || newsite -> coord.y < newintstar.y |
---|
| 37 | || (newsite->coord.y == newintstar.y |
---|
| 38 | && newsite->coord.x < newintstar.x))) {/* new site is |
---|
| 39 | smallest */ |
---|
| 40 | { |
---|
| 41 | out_site(newsite) ; |
---|
| 42 | } |
---|
| 43 | lbnd = ELleftbnd(&(newsite->coord)) ; |
---|
| 44 | rbnd = ELright(lbnd) ; |
---|
| 45 | bot = rightreg(lbnd) ; |
---|
| 46 | e = bisect(bot, newsite) ; |
---|
| 47 | bisector = HEcreate(e, le) ; |
---|
| 48 | ELinsert(lbnd, bisector) ; |
---|
| 49 | p = intersect(lbnd, bisector) ; |
---|
| 50 | if (p != (Site *)NULL) |
---|
| 51 | { |
---|
| 52 | PQdelete(lbnd) ; |
---|
| 53 | PQinsert(lbnd, p, dist(p,newsite)) ; |
---|
| 54 | } |
---|
| 55 | lbnd = bisector ; |
---|
| 56 | bisector = HEcreate(e, re) ; |
---|
| 57 | ELinsert(lbnd, bisector) ; |
---|
| 58 | p = intersect(bisector, rbnd) ; |
---|
| 59 | if (p != (Site *)NULL) |
---|
| 60 | { |
---|
| 61 | PQinsert(bisector, p, dist(p,newsite)) ; |
---|
| 62 | } |
---|
| 63 | newsite = (*nextsite)() ; |
---|
| 64 | } |
---|
| 65 | else if (!PQempty()) /* intersection is smallest */ |
---|
| 66 | { |
---|
| 67 | lbnd = PQextractmin() ; |
---|
| 68 | llbnd = ELleft(lbnd) ; |
---|
| 69 | rbnd = ELright(lbnd) ; |
---|
| 70 | rrbnd = ELright(rbnd) ; |
---|
| 71 | bot = leftreg(lbnd) ; |
---|
| 72 | top = rightreg(rbnd) ; |
---|
| 73 | out_triple(bot, top, rightreg(lbnd)) ; |
---|
| 74 | v = lbnd->vertex ; |
---|
| 75 | makevertex(v) ; |
---|
| 76 | endpoint(lbnd->ELedge, lbnd->ELpm, v); |
---|
| 77 | endpoint(rbnd->ELedge, rbnd->ELpm, v) ; |
---|
| 78 | ELdelete(lbnd) ; |
---|
| 79 | PQdelete(rbnd) ; |
---|
| 80 | ELdelete(rbnd) ; |
---|
| 81 | pm = le ; |
---|
| 82 | if (bot->coord.y > top->coord.y) |
---|
| 83 | { |
---|
| 84 | temp = bot ; |
---|
| 85 | bot = top ; |
---|
| 86 | top = temp ; |
---|
| 87 | pm = re ; |
---|
| 88 | } |
---|
| 89 | e = bisect(bot, top) ; |
---|
| 90 | bisector = HEcreate(e, pm) ; |
---|
| 91 | ELinsert(llbnd, bisector) ; |
---|
| 92 | endpoint(e, re-pm, v) ; |
---|
| 93 | deref(v) ; |
---|
| 94 | p = intersect(llbnd, bisector) ; |
---|
| 95 | if (p != (Site *) NULL) |
---|
| 96 | { |
---|
| 97 | PQdelete(llbnd) ; |
---|
| 98 | PQinsert(llbnd, p, dist(p,bot)) ; |
---|
| 99 | } |
---|
| 100 | p = intersect(bisector, rrbnd) ; |
---|
| 101 | if (p != (Site *) NULL) |
---|
| 102 | { |
---|
| 103 | PQinsert(bisector, p, dist(p,bot)) ; |
---|
| 104 | } |
---|
| 105 | } |
---|
| 106 | else |
---|
| 107 | { |
---|
| 108 | break ; |
---|
| 109 | } |
---|
| 110 | } |
---|
| 111 | |
---|
| 112 | for( lbnd = ELright(ELleftend) ; |
---|
| 113 | lbnd != ELrightend ; |
---|
| 114 | lbnd = ELright(lbnd)) |
---|
| 115 | { |
---|
| 116 | e = lbnd->ELedge ; |
---|
| 117 | out_ep(e) ; |
---|
| 118 | } |
---|
| 119 | } |
---|
| 120 | |
---|