1 #include <stdlib.h>
2 #include <grass/gis.h>
3 #include "sw_defs.h"
4
5 int ntry, totalsearch;
6
ELinitialize(void)7 int ELinitialize(void)
8 {
9 int i;
10
11 freeinit(&hfl, sizeof(struct Halfedge));
12 ELhashsize = 2 * sqrt_nsites;
13 ELhash = (struct Halfedge **)G_malloc(ELhashsize * sizeof(struct Halfedge *));
14 for (i = 0; i < ELhashsize; i++)
15 ELhash[i] = (struct Halfedge *)NULL;
16 ELleftend = HEcreate((struct Edge *)NULL, 0);
17 ELrightend = HEcreate((struct Edge *)NULL, 0);
18 ELleftend->ELleft = (struct Halfedge *)NULL;
19 ELleftend->ELright = ELrightend;
20 ELrightend->ELleft = ELleftend;
21 ELrightend->ELright = (struct Halfedge *)NULL;
22 ELhash[0] = ELleftend;
23 ELhash[ELhashsize - 1] = ELrightend;
24
25 return 0;
26 }
27
28
HEcreate(struct Edge * e,int pm)29 struct Halfedge *HEcreate(struct Edge *e, int pm)
30 {
31 struct Halfedge *answer;
32
33 answer = (struct Halfedge *)getfree(&hfl);
34 answer->ELedge = e;
35 answer->ELpm = pm;
36 answer->PQnext = (struct Halfedge *)NULL;
37 answer->vertex = (struct Site *)NULL;
38 answer->ELrefcnt = 0;
39 return (answer);
40 }
41
42
ELinsert(struct Halfedge * lb,struct Halfedge * new)43 int ELinsert(struct Halfedge *lb, struct Halfedge *new)
44 {
45 new->ELleft = lb;
46 new->ELright = lb->ELright;
47 (lb->ELright)->ELleft = new;
48 lb->ELright = new;
49
50 return 0;
51 }
52
53 /* Get entry from hash table, pruning any deleted nodes */
ELgethash(int b)54 struct Halfedge *ELgethash(int b)
55 {
56 struct Halfedge *he;
57
58 if (b < 0 || b >= ELhashsize)
59 return ((struct Halfedge *)NULL);
60 he = ELhash[b];
61 if (he == (struct Halfedge *)NULL || he->ELedge != (struct Edge *)DELETED)
62 return (he);
63
64 /* Hash table points to deleted half edge. Patch as necessary. */
65 ELhash[b] = (struct Halfedge *)NULL;
66 if (--(he->ELrefcnt) == 0)
67 makefree((struct Freenode *)he, &hfl);
68 return ((struct Halfedge *)NULL);
69 }
70
ELleftbnd(struct Point * p)71 struct Halfedge *ELleftbnd(struct Point *p)
72 {
73 int i, bucket;
74 struct Halfedge *he;
75
76 /* Use hash table to get close to desired halfedge */
77 bucket = (p->x - xmin) / deltax * ELhashsize;
78 if (bucket < 0)
79 bucket = 0;
80 if (bucket >= ELhashsize)
81 bucket = ELhashsize - 1;
82 he = ELgethash(bucket);
83 if (he == (struct Halfedge *)NULL) {
84 for (i = 1; 1; i++) {
85 if ((he = ELgethash(bucket - i)) != (struct Halfedge *)NULL)
86 break;
87 if ((he = ELgethash(bucket + i)) != (struct Halfedge *)NULL)
88 break;
89 }
90 totalsearch += i;
91 }
92 ntry++;
93 /* Now search linear list of halfedges for the corect one */
94 if (he == ELleftend || (he != ELrightend && right_of(he, p))) {
95 do {
96 he = he->ELright;
97 } while (he != ELrightend && right_of(he, p));
98 he = he->ELleft;
99 }
100 else
101 do {
102 he = he->ELleft;
103 } while (he != ELleftend && !right_of(he, p));
104
105 /* Update hash table and reference counts */
106 if (bucket > 0 && bucket < ELhashsize - 1) {
107 if (ELhash[bucket] != (struct Halfedge *)NULL)
108 ELhash[bucket]->ELrefcnt--;
109 ELhash[bucket] = he;
110 ELhash[bucket]->ELrefcnt++;
111 }
112 return (he);
113 }
114
115
116 /* This delete routine can't reclaim node, since pointers from hash
117 table may be present. */
ELdelete(struct Halfedge * he)118 int ELdelete(struct Halfedge *he)
119 {
120 (he->ELleft)->ELright = he->ELright;
121 (he->ELright)->ELleft = he->ELleft;
122 he->ELedge = (struct Edge *)DELETED;
123
124 return 0;
125 }
126
127
ELright(struct Halfedge * he)128 struct Halfedge *ELright(struct Halfedge *he)
129 {
130 return (he->ELright);
131 }
132
ELleft(struct Halfedge * he)133 struct Halfedge *ELleft(struct Halfedge *he)
134 {
135 return (he->ELleft);
136 }
137
138
leftreg(struct Halfedge * he)139 struct Site *leftreg(struct Halfedge *he)
140 {
141 if (he->ELedge == (struct Edge *)NULL)
142 return (bottomsite);
143 return (he->ELpm == le ? he->ELedge->reg[le] : he->ELedge->reg[re]);
144 }
145
rightreg(struct Halfedge * he)146 struct Site *rightreg(struct Halfedge *he)
147 {
148 if (he->ELedge == (struct Edge *)NULL)
149 return (bottomsite);
150 return (he->ELpm == le ? he->ELedge->reg[re] : he->ELedge->reg[le]);
151 }
152