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