Graphviz 14.0.2~dev.20251008.0253
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#include <util/arena.h>
18
19#define DELETED -2
20
23 free(st->hash);
24}
25
27 assert(st != NULL);
28
29 *st = (el_state_t){0};
30
31 st->hashsize = 2 * sqrt_nsites;
32 st->hash = gv_calloc(st->hashsize, sizeof(Halfedge *));
33 st->leftend = HEcreate(st, NULL, 0);
34 st->rightend = HEcreate(st, NULL, 0);
35 st->leftend->ELleft = NULL;
36 st->leftend->ELright = st->rightend;
37 st->rightend->ELleft = st->leftend;
38 st->rightend->ELright = NULL;
39 st->hash[0] = st->leftend;
40 st->hash[st->hashsize - 1] = st->rightend;
41}
42
43Site *hintersect(Halfedge *el1, Halfedge *el2, arena_t *allocator) {
44 assert(allocator != NULL);
45 Edge *e1, *e2, *e;
46 Halfedge *el;
47 double d, xint, yint;
48 bool right_of_site;
49
50 e1 = el1->ELedge;
51 e2 = el2->ELedge;
52 if (e1 == NULL || e2 == NULL)
53 return NULL;
54 if (e1->reg[1] == e2->reg[1])
55 return NULL;
56
57 d = e1->a * e2->b - e1->b * e2->a;
58 if (-1.0e-10 < d && d < 1.0e-10)
59 return NULL;
60
61 xint = (e1->c * e2->b - e2->c * e1->b) / d;
62 yint = (e2->c * e1->a - e1->c * e2->a) / d;
63
64 if (e1->reg[1]->coord.y < e2->reg[1]->coord.y ||
65 (e1->reg[1]->coord.y == e2->reg[1]->coord.y &&
66 e1->reg[1]->coord.x < e2->reg[1]->coord.x)) {
67 el = el1;
68 e = e1;
69 } else {
70 el = el2;
71 e = e2;
72 }
73 right_of_site = xint >= e->reg[1]->coord.x;
74 if ((right_of_site && el->ELpm == le) || (!right_of_site && el->ELpm == re))
75 return NULL;
76
77 Site *const v = ARENA_NEW(allocator, Site);
78 v->coord.x = xint;
79 v->coord.y = yint;
80 return v;
81}
82
83/* returns 1 if p is to right of halfedge e */
84static int right_of(Halfedge *el, Point *p) {
85 Edge *e;
86 Site *topsite;
87 int above, fast;
88 double dxp, dyp, dxs, t1, t2, t3, yl;
89
90 e = el->ELedge;
91 topsite = e->reg[1];
92 bool right_of_site = p->x > topsite->coord.x;
93 if (right_of_site && el->ELpm == le)
94 return 1;
95 if (!right_of_site && el->ELpm == re)
96 return 0;
97
98 if (e->a == 1.0) {
99 dyp = p->y - topsite->coord.y;
100 dxp = p->x - topsite->coord.x;
101 fast = 0;
102 if ((!right_of_site && e->b < 0.0) || (right_of_site && e->b >= 0.0)) {
103 above = dyp >= e->b * dxp;
104 fast = above;
105 } else {
106 above = p->x + p->y * e->b > e->c;
107 if (e->b < 0.0)
108 above = !above;
109 if (!above)
110 fast = 1;
111 }
112 if (!fast) {
113 dxs = topsite->coord.x - (e->reg[0])->coord.x;
114 above = e->b * (dxp * dxp - dyp * dyp) <
115 dxs * dyp * (1.0 + 2.0 * dxp / dxs + e->b * e->b);
116 if (e->b < 0.0)
117 above = !above;
118 }
119 } else { /*e->b==1.0 */
120 yl = e->c - e->a * p->x;
121 t1 = p->y - yl;
122 t2 = p->x - topsite->coord.x;
123 t3 = yl - topsite->coord.y;
124 above = t1 * t1 > t2 * t2 + t3 * t3;
125 }
126 return el->ELpm == le ? above : !above;
127}
128
129Halfedge *HEcreate(el_state_t *st, Edge *e, char pm) {
130 Halfedge *answer = ARENA_NEW(&st->allocated, Halfedge);
131 answer->ELedge = e;
132 answer->ELpm = pm;
133 answer->PQnext = NULL;
134 answer->vertex = NULL;
135 return answer;
136}
137
138
139void ELinsert(Halfedge * lb, Halfedge * new)
140{
141 new->ELleft = lb;
142 new->ELright = lb->ELright;
143 lb->ELright->ELleft = new;
144 lb->ELright = new;
145}
146
147/* Get entry from hash table, pruning any deleted nodes */
148static Halfedge *ELgethash(el_state_t *st, int b) {
149 assert(st != NULL);
150 Halfedge *he;
151
152 if (b < 0 || b >= st->hashsize)
153 return NULL;
154 he = st->hash[b];
155 if (he == NULL || he->ELedge != (Edge *) DELETED)
156 return he;
157
158/* Hash table points to deleted half edge. Patch as necessary. */
159 st->hash[b] = NULL;
160 return NULL;
161}
162
169static int clamp(int lower, double v, int upper) {
170 assert(upper >= lower);
171 if (v < lower) {
172 return lower;
173 }
174 if (v > upper) {
175 return upper;
176 }
177 return (int)v;
178}
179
181 assert(st != NULL);
182 int i;
183 Halfedge *he;
184
185/* Use hash table to get close to desired halfedge */
186 const int bucket =
187 clamp(0, (p->x - xmin) / deltax * st->hashsize, st->hashsize - 1);
188 he = ELgethash(st, bucket);
189 if (he == NULL) {
190 for (i = 1; ; ++i) {
191 if ((he = ELgethash(st, bucket - i)) != NULL)
192 break;
193 if ((he = ELgethash(st, bucket + i)) != NULL)
194 break;
195 }
196 }
197/* Now search linear list of halfedges for the corect one */
198 if (he == st->leftend || (he != st->rightend && right_of(he, p))) {
199 do {
200 he = he->ELright;
201 } while (he != st->rightend && right_of(he, p));
202 he = he->ELleft;
203 } else
204 do {
205 he = he->ELleft;
206 } while (he != st->leftend && !right_of(he, p));
207
208/* Update hash table */
209 if (bucket > 0 && bucket < st->hashsize - 1) {
210 st->hash[bucket] = he;
211 }
212 return he;
213}
214
215
216/* This delete routine can't reclaim node, since pointers from hash
217 table may be present. */
219{
220 he->ELleft->ELright = he->ELright;
221 he->ELright->ELleft = he->ELleft;
222 he->ELedge = (Edge *) DELETED;
223}
224
225
227{
228 return he->ELright;
229}
230
232{
233 return he->ELleft;
234}
235
236
238{
239 if (he->ELedge == NULL)
240 return bottomsite;
241 return he->ELpm == le ? he->ELedge->reg[le] : he->ELedge->reg[re];
242}
243
245{
246 if (he->ELedge == NULL)
247 return bottomsite;
248 return he->ELpm == le ? he->ELedge->reg[re] : he->ELedge->reg[le];
249}
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
void gv_arena_reset(arena_t *arena)
Definition arena.c:162
Region-based memory allocator.
#define ARENA_NEW(arena, type)
Definition arena.h:55
#define le
Definition edges.h:29
#define re
Definition edges.h:30
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:181
static Halfedge * ELgethash(el_state_t *st, int b)
Definition hedges.c:148
Site * hintersect(Halfedge *el1, Halfedge *el2, arena_t *allocator)
Definition hedges.c:43
Halfedge * ELright(Halfedge *he)
Definition hedges.c:226
void ELcleanup(el_state_t *st)
Definition hedges.c:21
void ELinitialize(el_state_t *st)
Definition hedges.c:26
void ELinsert(Halfedge *lb, Halfedge *new)
Definition hedges.c:139
static int right_of(Halfedge *el, Point *p)
Definition hedges.c:84
Site * rightreg(Halfedge *he)
Definition hedges.c:244
Halfedge * ELleft(Halfedge *he)
Definition hedges.c:231
static int clamp(int lower, double v, int upper)
Definition hedges.c:169
Halfedge * ELleftbnd(el_state_t *st, Point *p)
Definition hedges.c:180
#define DELETED
Definition hedges.c:19
void ELdelete(Halfedge *he)
Definition hedges.c:218
Halfedge * HEcreate(el_state_t *st, Edge *e, char pm)
Definition hedges.c:129
Site * leftreg(Halfedge *he)
Definition hedges.c:237
pointf coord(node_t *n)
Definition utils.c:153
Site * bottomsite
Definition site.c:14
Definition edges.h:23
double b
Definition edges.h:24
double c
Definition edges.h:24
Site * reg[2]
Definition edges.h:26
double a
Definition edges.h:24
Edge * ELedge
Definition hedges.h:25
struct Halfedge * PQnext
Definition hedges.h:29
char ELpm
Definition hedges.h:26
Site * vertex
Definition hedges.h:27
struct Halfedge * ELleft
Definition hedges.h:24
struct Halfedge * ELright
Definition hedges.h:24
double x
Definition geometry.h:24
double y
Definition geometry.h:24
Definition site.h:23
Point coord
Definition site.h:24
int hashsize
Definition hedges.h:34
Halfedge * leftend
Definition hedges.h:36
Halfedge ** hash
Definition hedges.h:35
arena_t allocated
outstanding dynamic allocations
Definition hedges.h:33
Halfedge * rightend
Definition hedges.h:37
double x
Definition geom.h:29