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