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