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