Graphviz 14.0.2~dev.20251008.0253
Loading...
Searching...
No Matches
poly.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 <neatogen/neato.h>
12#include <assert.h>
13#include <string.h>
14#include <math.h>
15#include <neatogen/poly.h>
16#include <common/geom.h>
17#include <stdbool.h>
18#include <util/alloc.h>
19#include <util/streq.h>
20
21static const int BOX = 1;
22static const int CIRCLE = 2;
23
24static bool ISBOX(const Poly *p) { return p->kind & BOX; }
25static bool ISCIRCLE(const Poly *p) { return p->kind & CIRCLE; }
26
27static size_t maxcnt = 0;
28static Point *tp1 = NULL;
29static Point *tp2 = NULL;
30static Point *tp3 = NULL;
31
32void polyFree(void)
33{
34 maxcnt = 0;
35 free(tp1);
36 free(tp2);
37 free(tp3);
38 tp1 = NULL;
39 tp2 = NULL;
40 tp3 = NULL;
41}
42
43void breakPoly(Poly * pp)
44{
45 free(pp->verts);
46}
47
48static void bbox(Point *verts, size_t cnt, Point *o, Point *c) {
49 double x_min, y_min, x_max, y_max;
50
51 x_min = x_max = verts->x;
52 y_min = y_max = verts->y;
53 for (size_t i = 1; i < cnt; i++) {
54 verts++;
55 x_min = fmin(x_min, verts->x);
56 y_min = fmin(y_min, verts->y);
57 x_max = fmax(x_max, verts->x);
58 y_max = fmax(y_max, verts->y);
59 }
60 o->x = x_min;
61 o->y = y_min;
62 c->x = x_max;
63 c->y = y_max;
64}
65
66static void inflatePts(Point *verts, size_t cnt, double xmargin,
67 double ymargin) {
68 Point *cur;
69
70 cur = &verts[0];
71 for (size_t i = 0; i < cnt; i++) {
72 cur->x *= xmargin;
73 cur->y *= ymargin;
74 cur++;
75 }
76}
77
78static int isBox(Point *verts, size_t cnt) {
79 if (cnt != 4)
80 return 0;
81
82 if (verts[0].y == verts[1].y)
83 return ((verts[2].y == verts[3].y) &&
84 (verts[0].x == verts[3].x) && (verts[1].x == verts[2].x));
85 else
86 return ((verts[0].x == verts[1].x) &&
87 (verts[2].x == verts[3].x) &&
88 (verts[0].y == verts[3].y) && (verts[1].y == verts[2].y));
89}
90
91static Point makeScaledTransPoint(double x, double y, double dx, double dy) {
92 Point rv;
93 rv.x = PS2INCH(x) + dx;
94 rv.y = PS2INCH(y) + dy;
95 return rv;
96}
97
98static Point makeScaledPoint(double x, double y)
99{
100 Point rv;
101 rv.x = PS2INCH(x);
102 rv.y = PS2INCH(y);
103 return rv;
104}
105
106static Point *genRound(Agnode_t *n, size_t *sidep, double xm, double ym) {
107 size_t sides = 0;
108 char *p = agget(n, "samplepoints");
109
110 int isides = 0;
111 if (p)
112 isides = atoi(p);
113 sides = isides < 3 ? DFLT_SAMPLE : (size_t)isides;
114 Point *verts = gv_calloc(sides, sizeof(Point));
115 for (size_t i = 0; i < sides; i++) {
116 verts[i].x =
117 (ND_width(n) / 2.0 + xm) * cos((double)i / (double)sides * M_PI * 2.0);
118 verts[i].y =
119 (ND_height(n) / 2.0 + ym) * sin((double)i / (double)sides * M_PI * 2.0);
120 }
121 *sidep = sides;
122 return verts;
123}
124
125#define PUTPT(P,X,Y) ((P).x=(X),(P).y=(Y))
126
127int makeAddPoly(Poly *pp, Agnode_t *n, double xmargin, double ymargin) {
128 size_t sides;
129 Point *verts;
131
132 if (ND_clust(n)) {
133 Point b;
134 sides = 4;
135 b.x = ND_width(n) / 2.0 + xmargin;
136 b.y = ND_height(n) / 2.0 + ymargin;
137 pp->kind = BOX;
138 verts = gv_calloc(sides, sizeof(Point));
139 PUTPT(verts[0], b.x, b.y);
140 PUTPT(verts[1], -b.x, b.y);
141 PUTPT(verts[2], -b.x, -b.y);
142 PUTPT(verts[3], b.x, -b.y);
143 } else
144 switch (shapeOf(n)) {
145 case SH_POLY:
146 poly = ND_shape_info(n);
147 sides = poly->sides;
148
149 if (streq(ND_shape(n)->name, "box"))
150 pp->kind = BOX;
151 else if (streq(ND_shape(n)->name, "polygon")
152 && isBox(poly->vertices, sides))
153 pp->kind = BOX;
154 else if ((poly->sides < 3) && poly->regular)
155 pp->kind = CIRCLE;
156 else
157 pp->kind = 0;
158
159 if (sides >= 3) { /* real polygon */
160 verts = gv_calloc(sides, sizeof(Point));
161 if (pp->kind == BOX) {
162 /* To do an additive margin, we rely on knowing that
163 * the vertices are CCW starting from the UR
164 */
165 verts[0].x = PS2INCH(poly->vertices[0].x) + xmargin;
166 verts[0].y = PS2INCH(poly->vertices[0].y) + ymargin;
167 verts[1].x = PS2INCH(poly->vertices[1].x) - xmargin;
168 verts[1].y = PS2INCH(poly->vertices[1].y) + ymargin;
169 verts[2].x = PS2INCH(poly->vertices[2].x) - xmargin;
170 verts[2].y = PS2INCH(poly->vertices[2].y) - ymargin;
171 verts[3].x = PS2INCH(poly->vertices[3].x) + xmargin;
172 verts[3].y = PS2INCH(poly->vertices[3].y) - ymargin;
173
174 }
175 else {
176 for (size_t i = 0; i < sides; i++) {
177 const double h = hypot(poly->vertices[i].x, poly->vertices[i].y);
178 verts[i].x = poly->vertices[i].x * (1.0 + xmargin/h);
179 verts[i].y = poly->vertices[i].y * (1.0 + ymargin/h);
180 verts[i].x = PS2INCH(verts[i].x);
181 verts[i].y = PS2INCH(verts[i].y);
182 }
183 }
184 } else
185 verts = genRound(n, &sides, xmargin, ymargin);
186 break;
187 case SH_RECORD: {
188 sides = 4;
189 verts = gv_calloc(sides, sizeof(Point));
190 boxf b = ((field_t*)ND_shape_info(n))->b;
191 verts[0] = makeScaledTransPoint(b.LL.x, b.LL.y, -xmargin, -ymargin);
192 verts[1] = makeScaledTransPoint(b.UR.x, b.LL.y, xmargin, -ymargin);
193 verts[2] = makeScaledTransPoint(b.UR.x, b.UR.y, xmargin, ymargin);
194 verts[3] = makeScaledTransPoint(b.LL.x, b.UR.y, -xmargin, ymargin);
195 pp->kind = BOX;
196 break;
197 }
198 case SH_POINT:
199 pp->kind = CIRCLE;
200 verts = genRound(n, &sides, xmargin, ymargin);
201 break;
202 default:
203 agerrorf("makeAddPoly: unknown shape type %s\n",
204 ND_shape(n)->name);
205 return 1;
206 }
207
208 pp->verts = verts;
209 pp->nverts = (int)sides;
210 bbox(verts, sides, &pp->origin, &pp->corner);
211
212 if (sides > maxcnt)
213 maxcnt = sides;
214 return 0;
215}
216
217int makePoly(Poly *pp, Agnode_t *n, double xmargin, double ymargin) {
218 size_t sides;
219 Point *verts;
221
222 if (ND_clust(n)) {
223 Point b;
224 sides = 4;
225 b.x = ND_width(n) / 2.0;
226 b.y = ND_height(n) / 2.0;
227 pp->kind = BOX;
228 verts = gv_calloc(sides, sizeof(Point));
229 PUTPT(verts[0], b.x, b.y);
230 PUTPT(verts[1], -b.x, b.y);
231 PUTPT(verts[2], -b.x, -b.y);
232 PUTPT(verts[3], b.x, -b.y);
233 } else
234 switch (shapeOf(n)) {
235 case SH_POLY:
236 poly = ND_shape_info(n);
237 sides = poly->sides;
238 if (sides >= 3) { /* real polygon */
239 verts = gv_calloc(sides, sizeof(Point));
240 for (size_t i = 0; i < sides; i++) {
241 verts[i].x = PS2INCH(poly->vertices[i].x);
242 verts[i].y = PS2INCH(poly->vertices[i].y);
243 }
244 } else
245 verts = genRound(n, &sides, 0, 0);
246
247 if (streq(ND_shape(n)->name, "box"))
248 pp->kind = BOX;
249 else if (streq(ND_shape(n)->name, "polygon")
250 && isBox(verts, sides))
251 pp->kind = BOX;
252 else if ((poly->sides < 3) && poly->regular)
253 pp->kind = CIRCLE;
254 else
255 pp->kind = 0;
256
257 break;
258 case SH_RECORD: {
259 sides = 4;
260 verts = gv_calloc(sides, sizeof(Point));
261 boxf b = ((field_t *) ND_shape_info(n))->b;
262 verts[0] = makeScaledPoint(b.LL.x, b.LL.y);
263 verts[1] = makeScaledPoint(b.UR.x, b.LL.y);
264 verts[2] = makeScaledPoint(b.UR.x, b.UR.y);
265 verts[3] = makeScaledPoint(b.LL.x, b.UR.y);
266 pp->kind = BOX;
267 break;
268 }
269 case SH_POINT:
270 pp->kind = CIRCLE;
271 verts = genRound(n, &sides, 0, 0);
272 break;
273 default:
274 agerrorf("makePoly: unknown shape type %s\n",
275 ND_shape(n)->name);
276 return 1;
277 }
278
279 if ((xmargin != 1.0) || (ymargin != 1.0))
280 inflatePts(verts, sides, xmargin, ymargin);
281
282 pp->verts = verts;
283 pp->nverts = (int)sides;
284 bbox(verts, sides, &pp->origin, &pp->corner);
285
286 if (sides > maxcnt)
287 maxcnt = sides;
288 return 0;
289}
290
291static int
292pintersect(Point originp, Point cornerp, Point originq, Point cornerq)
293{
294 return ((originp.x <= cornerq.x) && (originq.x <= cornerp.x) &&
295 (originp.y <= cornerq.y) && (originq.y <= cornerp.y));
296}
297
298#define Pin 1
299#define Qin 2
300#define Unknown 0
301
302#define advance(A,B,N) (B++, A = (A+1)%N)
303
304static int edgesIntersect(Point * P, Point * Q, int n, int m)
305{
306 int a = 0;
307 int b = 0;
308 int aa = 0;
309 int ba = 0;
310 int a1, b1;
311 Point A, B;
312 double cross;
313 int bHA, aHB;
314 Point p;
315 int inflag = Unknown;
316 /* int i = 0; */
317 /* int Reset = 0; */
318
319 do {
320 a1 = (a + n - 1) % n;
321 b1 = (b + m - 1) % m;
322
323 subpt(&A, P[a], P[a1]);
324 subpt(&B, Q[b], Q[b1]);
325
326 cross = area_2((Point){0}, A, B);
327 bHA = leftOf(P[a1], P[a], Q[b]);
328 aHB = leftOf(Q[b1], Q[b], P[a]);
329
330 /* If A & B intersect, update inflag. */
331 if (intersection(P[a1], P[a], Q[b1], Q[b], &p))
332 return 1;
333
334 /* Advance rules. */
335 if ((cross == 0) && !bHA && !aHB) {
336 if (inflag == Pin)
337 advance(b, ba, m);
338 else
339 advance(a, aa, n);
340 } else if (cross >= 0)
341 if (bHA)
342 advance(a, aa, n);
343 else {
344 advance(b, ba, m);
345 } else { /* if ( cross < 0 ) */
346
347 if (aHB)
348 advance(b, ba, m);
349 else
350 advance(a, aa, n);
351 }
352
353 } while (((aa < n) || (ba < m)) && (aa < 2 * n) && (ba < 2 * m));
354
355 return 0;
356
357}
358
359/* inPoly:
360 * Return 1 if q is inside polygon vertex[]
361 * Assume points are in CCW order
362 */
363static int inPoly(Point vertex[], int n, Point q)
364{
365 int i, i1; /* point index; i1 = i-1 mod n */
366 double x; /* x intersection of e with ray */
367 double crossings = 0; /* number of edge/ray crossings */
368
369 if (tp3 == NULL)
370 tp3 = gv_calloc(maxcnt, sizeof(Point));
371
372 /* Shift so that q is the origin. */
373 for (i = 0; i < n; i++) {
374 tp3[i].x = vertex[i].x - q.x;
375 tp3[i].y = vertex[i].y - q.y;
376 }
377
378 /* For each edge e=(i-1,i), see if crosses ray. */
379 for (i = 0; i < n; i++) {
380 i1 = (i + n - 1) % n;
381
382 /* if edge is horizontal, test to see if the point is on it */
383 if (tp3[i].y == 0 && tp3[i1].y == 0) {
384 if (tp3[i].x * tp3[i1].x < 0) {
385 return 1;
386 } else {
387 continue;
388 }
389 }
390
391 /* if e straddles the x-axis... */
392 if ((tp3[i].y >= 0 && tp3[i1].y <= 0) ||
393 (tp3[i1].y >= 0 && tp3[i].y <= 0)) {
394 /* e straddles ray, so compute intersection with ray. */
395 x = (tp3[i].x * tp3[i1].y - tp3[i1].x * tp3[i].y)
396 / (double) (tp3[i1].y - tp3[i].y);
397
398 /* if intersect at origin, we've found intersection */
399 if (x == 0)
400 return 1;;
401
402 /* crosses ray if strictly positive intersection. */
403 if (x > 0) {
404 if (tp3[i].y == 0 || tp3[i1].y == 0) {
405 crossings += .5; /* goes through vertex */
406 } else {
407 crossings += 1.0;
408 }
409 }
410 }
411 }
412
413 /* q inside if an odd number of crossings. */
414 if ((int)crossings % 2 == 1)
415 return 1;
416 else
417 return 0;
418}
419
420static bool inBox(Point p, Point origin_point, Point corner) {
421 return p.x <= corner.x && p.x >= origin_point.x && p.y <= corner.y &&
422 p.y >= origin_point.y;
423}
424
425static void transCopy(Point * inp, int cnt, Point off, Point * outp)
426{
427 int i;
428
429 for (i = 0; i < cnt; i++) {
430 outp->x = inp->x + off.x;
431 outp->y = inp->y + off.y;
432 inp++;
433 outp++;
434 }
435}
436
437int polyOverlap(Point p, Poly * pp, Point q, Poly * qp)
438{
439 Point op, cp;
440 Point oq, cq;
441
442 /* translate bounding boxes */
443 addpt(&op, p, pp->origin);
444 addpt(&cp, p, pp->corner);
445 addpt(&oq, q, qp->origin);
446 addpt(&cq, q, qp->corner);
447
448 /* If bounding boxes don't overlap, done */
449 if (!pintersect(op, cp, oq, cq))
450 return 0;
451
452 if (ISBOX(pp) && ISBOX(qp))
453 return 1;
454 if (ISCIRCLE(pp) && ISCIRCLE(qp)) {
455 double d =
456 (pp->corner.x - pp->origin.x + qp->corner.x - qp->origin.x);
457 double dx = p.x - q.x;
458 double dy = p.y - q.y;
459 if ((dx * dx + dy * dy) > (d * d) / 4.0)
460 return 0;
461 else
462 return 1;
463 }
464
465 if (tp1 == NULL) {
466 tp1 = gv_calloc(maxcnt, sizeof(Point));
467 tp2 = gv_calloc(maxcnt, sizeof(Point));
468 }
469
470 transCopy(pp->verts, pp->nverts, p, tp1);
471 transCopy(qp->verts, qp->nverts, q, tp2);
472 return (edgesIntersect(tp1, tp2, pp->nverts, qp->nverts) ||
473 (inBox(*tp1, oq, cq) && inPoly(tp2, qp->nverts, *tp1)) ||
474 (inBox(*tp2, op, cp) && inPoly(tp1, pp->nverts, *tp2)));
475}
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
#define M_PI
Definition arith.h:41
#define DFLT_SAMPLE
Definition const.h:105
static bool leftOf(pointf p1, pointf p2, pointf p3)
Return true if p3 is to left of ray p1->p2.
static float dy
Definition draw.c:40
static float dx
Definition draw.c:39
#define A(n, t)
Definition expr.h:76
geometric types and macros (e.g. points and boxes)
#define PS2INCH(a_points)
Definition geom.h:64
void addpt(Point *c, Point a, Point b)
Definition geometry.c:42
void subpt(Point *a, Point b, Point c)
Definition geometry.c:36
double area_2(Point a, Point b, Point c)
Definition geometry.c:48
void free(void *)
node NULL
Definition grammar.y:181
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:196
char * agget(void *obj, char *name)
Definition attr.c:448
void agerrorf(const char *fmt,...)
Definition agerror.c:165
#define ND_clust(n)
Definition types.h:489
#define ND_height(n)
Definition types.h:498
#define ND_width(n)
Definition types.h:536
#define ND_shape_info(n)
Definition types.h:529
#define ND_shape(n)
Definition types.h:528
#define B
Definition hierarchy.c:118
static double cross(double *u, double *v)
int polyOverlap(Point p, Poly *pp, Point q, Poly *qp)
Definition poly.c:437
static int inPoly(Point vertex[], int n, Point q)
Definition poly.c:363
static Point makeScaledTransPoint(double x, double y, double dx, double dy)
Definition poly.c:91
#define Pin
Definition poly.c:298
static void inflatePts(Point *verts, size_t cnt, double xmargin, double ymargin)
Definition poly.c:66
void breakPoly(Poly *pp)
Definition poly.c:43
#define advance(A, B, N)
Definition poly.c:302
#define PUTPT(P, X, Y)
Definition poly.c:125
static bool ISCIRCLE(const Poly *p)
Definition poly.c:25
void polyFree(void)
Definition poly.c:32
static int isBox(Point *verts, size_t cnt)
Definition poly.c:78
static const int BOX
Definition poly.c:21
static size_t maxcnt
Definition poly.c:27
int makePoly(Poly *pp, Agnode_t *n, double xmargin, double ymargin)
Definition poly.c:217
#define Unknown
Definition poly.c:300
static void bbox(Point *verts, size_t cnt, Point *o, Point *c)
Definition poly.c:48
int makeAddPoly(Poly *pp, Agnode_t *n, double xmargin, double ymargin)
Definition poly.c:127
static const int CIRCLE
Definition poly.c:22
static void transCopy(Point *inp, int cnt, Point off, Point *outp)
Definition poly.c:425
static bool ISBOX(const Poly *p)
Definition poly.c:24
static Point * tp3
Definition poly.c:30
static Point * tp2
Definition poly.c:29
static Point * tp1
Definition poly.c:28
static bool inBox(Point p, Point origin_point, Point corner)
Definition poly.c:420
static int edgesIntersect(Point *P, Point *Q, int n, int m)
Definition poly.c:304
static int pintersect(Point originp, Point cornerp, Point originq, Point cornerq)
Definition poly.c:292
static Point * genRound(Agnode_t *n, size_t *sidep, double xm, double ym)
Definition poly.c:106
static Point makeScaledPoint(double x, double y)
Definition poly.c:98
shape_kind shapeOf(node_t *)
Definition shapes.c:1906
static bool streq(const char *a, const char *b)
are a and b equal?
Definition streq.h:11
double x
Definition geometry.h:24
double y
Definition geometry.h:24
Definition poly.h:21
Point corner
Definition poly.h:23
int nverts
Definition poly.h:24
Point * verts
Definition poly.h:25
int kind
Definition poly.h:26
Point origin
Definition poly.h:22
Definition geom.h:41
pointf UR
Definition geom.h:41
pointf LL
Definition geom.h:41
double x
Definition geom.h:29
double y
Definition geom.h:29
Definition legal.c:32
struct poly_s poly
@ SH_RECORD
Definition types.h:187
@ SH_POINT
Definition types.h:187
@ SH_POLY
Definition types.h:187