1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3
4 /*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14 #include "mem.h"
15 #include "hedges.h"
16 #include "render.h"
17
18
19 #define DELETED -2
20
21 Halfedge *ELleftend, *ELrightend;
22
23 static Freelist hfl;
24 static int ELhashsize;
25 static Halfedge **ELhash;
26 static int ntry, totalsearch;
27
ELcleanup()28 void ELcleanup()
29 {
30 freeinit(&hfl, sizeof **ELhash);
31 free(ELhash);
32 ELhash = NULL;
33 }
34
ELinitialize()35 void ELinitialize()
36 {
37 int i;
38
39 freeinit(&hfl, sizeof **ELhash);
40 ELhashsize = 2 * sqrt_nsites;
41 if (ELhash == NULL)
42 ELhash = N_GNEW(ELhashsize, Halfedge *);
43 for (i = 0; i < ELhashsize; i += 1)
44 ELhash[i] = (Halfedge *) NULL;
45 ELleftend = HEcreate((Edge *) NULL, 0);
46 ELrightend = HEcreate((Edge *) NULL, 0);
47 ELleftend->ELleft = (Halfedge *) NULL;
48 ELleftend->ELright = ELrightend;
49 ELrightend->ELleft = ELleftend;
50 ELrightend->ELright = (Halfedge *) NULL;
51 ELhash[0] = ELleftend;
52 ELhash[ELhashsize - 1] = ELrightend;
53 }
54
55
hintersect(Halfedge * el1,Halfedge * el2)56 Site *hintersect(Halfedge * el1, Halfedge * el2)
57 {
58 Edge *e1, *e2, *e;
59 Halfedge *el;
60 double d, xint, yint;
61 int right_of_site;
62 Site *v;
63
64 e1 = el1->ELedge;
65 e2 = el2->ELedge;
66 if (e1 == (Edge *) NULL || e2 == (Edge *) NULL)
67 return ((Site *) NULL);
68 if (e1->reg[1] == e2->reg[1])
69 return ((Site *) NULL);
70
71 d = e1->a * e2->b - e1->b * e2->a;
72 if (-1.0e-10 < d && d < 1.0e-10)
73 return ((Site *) NULL);
74
75 xint = (e1->c * e2->b - e2->c * e1->b) / d;
76 yint = (e2->c * e1->a - e1->c * e2->a) / d;
77
78 if ((e1->reg[1]->coord.y < e2->reg[1]->coord.y) ||
79 (e1->reg[1]->coord.y == e2->reg[1]->coord.y &&
80 e1->reg[1]->coord.x < e2->reg[1]->coord.x)) {
81 el = el1;
82 e = e1;
83 } else {
84 el = el2;
85 e = e2;
86 };
87 right_of_site = xint >= e->reg[1]->coord.x;
88 if ((right_of_site && el->ELpm == le) ||
89 (!right_of_site && el->ELpm == re))
90 return ((Site *) NULL);
91
92 v = getsite();
93 v->refcnt = 0;
94 v->coord.x = xint;
95 v->coord.y = yint;
96 return (v);
97 }
98
99 /* returns 1 if p is to right of halfedge e */
right_of(Halfedge * el,Point * p)100 int right_of(Halfedge * el, Point * p)
101 {
102 Edge *e;
103 Site *topsite;
104 int right_of_site, above, fast;
105 double dxp, dyp, dxs, t1, t2, t3, yl;
106
107 e = el->ELedge;
108 topsite = e->reg[1];
109 right_of_site = p->x > topsite->coord.x;
110 if (right_of_site && el->ELpm == le)
111 return (1);
112 if (!right_of_site && el->ELpm == re)
113 return (0);
114
115 if (e->a == 1.0) {
116 dyp = p->y - topsite->coord.y;
117 dxp = p->x - topsite->coord.x;
118 fast = 0;
119 if ((!right_of_site & (e->b < 0.0)) |
120 (right_of_site & (e->b >= 0.0))) {
121 above = dyp >= e->b * dxp;
122 fast = above;
123 } else {
124 above = p->x + p->y * e->b > e->c;
125 if (e->b < 0.0)
126 above = !above;
127 if (!above)
128 fast = 1;
129 };
130 if (!fast) {
131 dxs = topsite->coord.x - (e->reg[0])->coord.x;
132 above = e->b * (dxp * dxp - dyp * dyp) <
133 dxs * dyp * (1.0 + 2.0 * dxp / dxs + e->b * e->b);
134 if (e->b < 0.0)
135 above = !above;
136 };
137 } else { /*e->b==1.0 */
138 yl = e->c - e->a * p->x;
139 t1 = p->y - yl;
140 t2 = p->x - topsite->coord.x;
141 t3 = yl - topsite->coord.y;
142 above = t1 * t1 > t2 * t2 + t3 * t3;
143 };
144 return (el->ELpm == le ? above : !above);
145 }
146
HEcreate(Edge * e,char pm)147 Halfedge *HEcreate(Edge * e, char pm)
148 {
149 Halfedge *answer;
150 answer = (Halfedge *) getfree(&hfl);
151 answer->ELedge = e;
152 answer->ELpm = pm;
153 answer->PQnext = (Halfedge *) NULL;
154 answer->vertex = (Site *) NULL;
155 answer->ELrefcnt = 0;
156 return (answer);
157 }
158
159
ELinsert(Halfedge * lb,Halfedge * new)160 void ELinsert(Halfedge * lb, Halfedge * new)
161 {
162 new->ELleft = lb;
163 new->ELright = lb->ELright;
164 (lb->ELright)->ELleft = new;
165 lb->ELright = new;
166 }
167
168 /* Get entry from hash table, pruning any deleted nodes */
ELgethash(int b)169 static Halfedge *ELgethash(int b)
170 {
171 Halfedge *he;
172
173 if (b < 0 || b >= ELhashsize)
174 return ((Halfedge *) NULL);
175 he = ELhash[b];
176 if (he == (Halfedge *) NULL || he->ELedge != (Edge *) DELETED)
177 return (he);
178
179 /* Hash table points to deleted half edge. Patch as necessary. */
180 ELhash[b] = (Halfedge *) NULL;
181 if ((he->ELrefcnt -= 1) == 0)
182 makefree(he, &hfl);
183 return ((Halfedge *) NULL);
184 }
185
ELleftbnd(Point * p)186 Halfedge *ELleftbnd(Point * p)
187 {
188 int i, bucket;
189 Halfedge *he;
190
191 /* Use hash table to get close to desired halfedge */
192 bucket = (p->x - xmin) / deltax * ELhashsize;
193 if (bucket < 0)
194 bucket = 0;
195 if (bucket >= ELhashsize)
196 bucket = ELhashsize - 1;
197 he = ELgethash(bucket);
198 if (he == (Halfedge *) NULL) {
199 for (i = 1; 1; i += 1) {
200 if ((he = ELgethash(bucket - i)) != (Halfedge *) NULL)
201 break;
202 if ((he = ELgethash(bucket + i)) != (Halfedge *) NULL)
203 break;
204 };
205 totalsearch += i;
206 };
207 ntry += 1;
208 /* Now search linear list of halfedges for the corect one */
209 if (he == ELleftend || (he != ELrightend && right_of(he, p))) {
210 do {
211 he = he->ELright;
212 } while (he != ELrightend && right_of(he, p));
213 he = he->ELleft;
214 } else
215 do {
216 he = he->ELleft;
217 } while (he != ELleftend && !right_of(he, p));
218
219 /* Update hash table and reference counts */
220 if (bucket > 0 && bucket < ELhashsize - 1) {
221 if (ELhash[bucket] != (Halfedge *) NULL)
222 ELhash[bucket]->ELrefcnt -= 1;
223 ELhash[bucket] = he;
224 ELhash[bucket]->ELrefcnt += 1;
225 };
226 return (he);
227 }
228
229
230 /* This delete routine can't reclaim node, since pointers from hash
231 table may be present. */
ELdelete(Halfedge * he)232 void ELdelete(Halfedge * he)
233 {
234 (he->ELleft)->ELright = he->ELright;
235 (he->ELright)->ELleft = he->ELleft;
236 he->ELedge = (Edge *) DELETED;
237 }
238
239
ELright(Halfedge * he)240 Halfedge *ELright(Halfedge * he)
241 {
242 return (he->ELright);
243 }
244
ELleft(Halfedge * he)245 Halfedge *ELleft(Halfedge * he)
246 {
247 return (he->ELleft);
248 }
249
250
leftreg(Halfedge * he)251 Site *leftreg(Halfedge * he)
252 {
253 if (he->ELedge == (Edge *) NULL)
254 return (bottomsite);
255 return (he->ELpm == le ? he->ELedge->reg[le] : he->ELedge->reg[re]);
256 }
257
rightreg(Halfedge * he)258 Site *rightreg(Halfedge * he)
259 {
260 if (he->ELedge == (Edge *) NULL)
261 return (bottomsite);
262 return (he->ELpm == le ? he->ELedge->reg[re] : he->ELedge->reg[le]);
263 }
264