Graphviz  2.41.20170921.2350
hedges.c
Go to the documentation of this file.
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 
22 
23 static Freelist hfl;
24 static int ELhashsize;
25 static Halfedge **ELhash;
26 static int ntry, totalsearch;
27 
28 void ELcleanup()
29 {
30  freeinit(&hfl, sizeof **ELhash);
31  free(ELhash);
32  ELhash = NULL;
33 }
34 
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 
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 */
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 
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 
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 */
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 
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. */
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 
241 {
242  return (he->ELright);
243 }
244 
246 {
247  return (he->ELleft);
248 }
249 
250 
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 
259 {
260  if (he->ELedge == (Edge *) NULL)
261  return (bottomsite);
262  return (he->ELpm == le ? he->ELedge->reg[re] : he->ELedge->reg[le]);
263 }
struct Halfedge * PQnext
Definition: hedges.h:33
int refcnt
Definition: site.h:29
Site * bottomsite
Definition: site.c:20
Edge * ELedge
Definition: hedges.h:28
Site * rightreg(Halfedge *he)
Definition: hedges.c:258
double deltax
Definition: geometry.c:21
void ELinsert(Halfedge *lb, Halfedge *new)
Definition: hedges.c:160
Site * getsite()
Definition: site.c:36
double y
Definition: geometry.h:27
void * getfree(Freelist *)
Definition: memory.c:62
char ELpm
Definition: hedges.h:30
double b
Definition: edges.h:26
Definition: site.h:26
double xmin
Definition: geometry.c:20
Halfedge * HEcreate(Edge *e, char pm)
Definition: hedges.c:147
struct Halfedge * ELleft
Definition: hedges.h:27
Site * hintersect(Halfedge *el1, Halfedge *el2)
Definition: hedges.c:56
Halfedge * ELrightend
Definition: hedges.c:21
Definition: edges.h:25
Halfedge * ELleftend
Definition: hedges.c:21
Halfedge * ELright(Halfedge *he)
Definition: hedges.c:240
double x
Definition: geometry.h:27
void makefree(void *, Freelist *)
Definition: memory.c:86
double c
Definition: edges.h:26
#define le
Definition: edges.h:32
int sqrt_nsites
Definition: geometry.c:25
Definition: mem.h:29
double a
Definition: edges.h:26
void ELdelete(Halfedge *he)
Definition: hedges.c:232
int ELrefcnt
Definition: hedges.h:29
Halfedge * ELleftbnd(Point *p)
Definition: hedges.c:186
void ELcleanup()
Definition: hedges.c:28
Site * reg[2]
Definition: edges.h:28
#define DELETED
Definition: hedges.c:19
#define re
Definition: edges.h:33
Site * leftreg(Halfedge *he)
Definition: hedges.c:251
Halfedge * ELleft(Halfedge *he)
Definition: hedges.c:245
int right_of(Halfedge *el, Point *p)
Definition: hedges.c:100
#define NULL
Definition: logic.h:39
Site * vertex
Definition: hedges.h:31
double x
Definition: geom.h:28
Definition: geometry.h:26
void ELinitialize()
Definition: hedges.c:35
struct Halfedge * ELright
Definition: hedges.h:27
Point coord
Definition: site.h:27
pointf coord(node_t *n)
Definition: utils.c:202
char * el(GVJ_t *job, char *template,...)
#define N_GNEW(n, t)
Definition: agxbuf.c:20
void freeinit(Freelist *, int)
Definition: memory.c:43