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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
#
#include "defs.h"
int nedges;
struct Freelist efl;
struct Freelist hfl;
struct Halfedge *ELleftend, *ELrightend;
int ELhashsize;
struct Halfedge **ELhash;
int ntry, totalsearch;
void ELinitialize() {
int i;
freeinit(&hfl, sizeof **ELhash);
ELhashsize = 2 * sqrt_nsites;
ELhash = (struct Halfedge **)myalloc(sizeof *ELhash * ELhashsize);
for (i = 0; i < ELhashsize; i += 1)
ELhash[i] = (struct Halfedge *)NULL;
ELleftend = HEcreate((struct Edge *)NULL, 0);
ELrightend = HEcreate((struct Edge *)NULL, 0);
ELleftend->ELleft = (struct Halfedge *)NULL;
ELleftend->ELright = ELrightend;
ELrightend->ELleft = ELleftend;
ELrightend->ELright = (struct Halfedge *)NULL;
ELhash[0] = ELleftend;
ELhash[ELhashsize - 1] = ELrightend;
}
struct Halfedge *HEcreate(e, pm) struct Edge *e;
int pm;
{
struct Halfedge *answer;
answer = (struct Halfedge *)getfree(&hfl);
answer->ELedge = e;
answer->ELpm = pm;
answer->PQnext = (struct Halfedge *)NULL;
answer->vertex = (struct Site *)NULL;
answer->ELrefcnt = 0;
return (answer);
}
void ELinsert(struct Halfedge *lb, struct Halfedge *new) {
new->ELleft = lb;
new->ELright = lb->ELright;
(lb->ELright)->ELleft = new;
lb->ELright = new;
}
/* Get entry from hash table, pruning any deleted nodes */
struct Halfedge *ELgethash(b) int b;
{
struct Halfedge *he;
if (b < 0 || b >= ELhashsize)
return ((struct Halfedge *)NULL);
he = ELhash[b];
if (he == (struct Halfedge *)NULL || he->ELedge != (struct Edge *)DELETED)
return (he);
/* Hash table points to deleted half edge. Patch as necessary. */
ELhash[b] = (struct Halfedge *)NULL;
if ((he->ELrefcnt -= 1) == 0)
makefree((struct Freenode *)he, &hfl);
return ((struct Halfedge *)NULL);
}
struct Halfedge *ELleftbnd(p) struct Point *p;
{
int i, bucket;
struct Halfedge *he;
/* Use hash table to get close to desired halfedge */
bucket = (p->x - xmin) / deltax * ELhashsize;
if (bucket < 0)
bucket = 0;
if (bucket >= ELhashsize)
bucket = ELhashsize - 1;
he = ELgethash(bucket);
if (he == (struct Halfedge *)NULL) {
for (i = 1; 1; i += 1) {
if ((he = ELgethash(bucket - i)) != (struct Halfedge *)NULL)
break;
if ((he = ELgethash(bucket + i)) != (struct Halfedge *)NULL)
break;
};
totalsearch += i;
};
ntry += 1;
/* Now search linear list of halfedges for the corect one */
if (he == ELleftend || (he != ELrightend && right_of(he, p))) {
do {
he = he->ELright;
} while (he != ELrightend && right_of(he, p));
he = he->ELleft;
} else
do {
he = he->ELleft;
} while (he != ELleftend && !right_of(he, p));
/* Update hash table and reference counts */
if (bucket > 0 && bucket < ELhashsize - 1) {
if (ELhash[bucket] != (struct Halfedge *)NULL)
ELhash[bucket]->ELrefcnt -= 1;
ELhash[bucket] = he;
ELhash[bucket]->ELrefcnt += 1;
};
return (he);
}
/* This delete routine can't reclaim node, since pointers from hash
table may be present. */
void ELdelete(struct Halfedge *he) {
(he->ELleft)->ELright = he->ELright;
(he->ELright)->ELleft = he->ELleft;
he->ELedge = (struct Edge *)DELETED;
}
struct Halfedge *ELright(he) struct Halfedge *he;
{ return (he->ELright); }
struct Halfedge *ELleft(he) struct Halfedge *he;
{ return (he->ELleft); }
struct Site *leftreg(he) struct Halfedge *he;
{
if (he->ELedge == (struct Edge *)NULL)
return (bottomsite);
return (he->ELpm == le ? he->ELedge->reg[le] : he->ELedge->reg[re]);
}
struct Site *rightreg(he) struct Halfedge *he;
{
if (he->ELedge == (struct Edge *)NULL)
return (bottomsite);
return (he->ELpm == le ? he->ELedge->reg[re] : he->ELedge->reg[le]);
}
|
