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