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