Go to most recent revision | Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 10 | reyssat | 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 |