Graphviz  2.41.20171026.1811
poly.c
Go to the documentation of this file.
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 
30 static int maxcnt = 0;
31 static Point *tp1 = NULL;
32 static Point *tp2 = NULL;
33 static Point *tp3 = NULL;
34 
35 void 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 
46 void breakPoly(Poly * pp)
47 {
48  free(pp->verts);
49 }
50 
51 static 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
76 static 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 
89 static 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
115 static 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 
129 static 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 
143 static 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 
151 static 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 
159 static 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 
183 int 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 
275 int 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 
356 static int
357 pintersect(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 
369 static 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  */
428 static 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 
485 static 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 
492 static 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 
504 int 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 }
AGERR
Definition: cgraph.h:388
Poly
Definition: poly.h:23
vertex
Definition: legal.c:33
xmax
double xmax
Definition: geometry.c:20
field_t
Definition: types.h:245
shapeOf
shape_kind shapeOf(node_t *)
Definition: shapes.c:1820
CIRCLE
#define CIRCLE
Definition: poly.c:27
Point::y
double y
Definition: geometry.h:27
makeAddPoly
int makeAddPoly(Poly *pp, Agnode_t *n, float xmargin, float ymargin)
Definition: poly.c:183
Pin
#define Pin
Definition: poly.c:363
xmin
double xmin
Definition: geometry.c:20
agerr
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
ymax
double ymax
Definition: geometry.c:20
ND_shape_info
#define ND_shape_info(n)
Definition: types.h:535
Poly::corner
Point corner
Definition: poly.h:25
Point::x
double x
Definition: geometry.h:27
ymin
double ymin
Definition: geometry.c:20
Poly::verts
Point * verts
Definition: poly.h:27
ND_clust
#define ND_clust(n)
Definition: types.h:495
PS2INCH
#define PS2INCH(a_points)
Definition: geom.h:69
agget
char * agget(void *obj, char *name)
Definition: attr.c:428
BOX
#define BOX
Definition: poly.c:25
leftOf
int leftOf(Point a, Point b, Point c)
Definition: geometry.c:62
ISBOX
#define ISBOX(p)
Definition: poly.c:26
ND_shape
#define ND_shape(n)
Definition: types.h:534
origin
Point origin
Definition: geometry.c:18
LEN
#define LEN(a, b)
Definition: geom.h:57
pointf_s::y
double y
Definition: geom.h:28
ND_height
#define ND_height(n)
Definition: types.h:504
breakPoly
void breakPoly(Poly *pp)
Definition: poly.c:46
Agnode_s
Definition: cgraph.h:133
makePoly
int makePoly(Poly *pp, Agnode_t *n, float xmargin, float ymargin)
Definition: poly.c:275
polygon_t::sides
int sides
Definition: types.h:149
PUTPT
#define PUTPT(P, X, Y)
Definition: poly.c:181
if
if(aagss+aagstacksize-1<=aagssp)
Definition: grammar.c:1332
ND_width
#define ND_width(n)
Definition: types.h:542
area_2
double area_2(Point a, Point b, Point c)
Definition: geometry.c:57
ISCIRCLE
#define ISCIRCLE(p)
Definition: poly.c:28
addpt
void addpt(Point *c, Point a, Point b)
Definition: geometry.c:51
NULL
#define NULL
Definition: logic.h:39
pointf_s::x
double x
Definition: geom.h:28
SH_POLY
Definition: types.h:186
streq
#define streq(s, t)
Definition: cghdr.h:52
DFLT_SAMPLE
#define DFLT_SAMPLE
Definition: const.h:106
polygon_t::regular
int regular
Definition: types.h:147
Unknown
#define Unknown
Definition: poly.c:365
boxf::LL
pointf LL
Definition: geom.h:35
subpt
void subpt(Point *a, Point b, Point c)
Definition: geometry.c:45
Poly::origin
Point origin
Definition: poly.h:24
Point
Definition: geometry.h:26
Poly::nverts
int nverts
Definition: poly.h:26
polyOverlap
int polyOverlap(Point p, Poly *pp, Point q, Poly *qp)
Definition: poly.c:504
intersection
int intersection(Point a, Point b, Point c, Point d, Point *p)
Definition: geometry.c:67
polygon_t::vertices
pointf * vertices
Definition: types.h:154
M_PI
#define M_PI
Definition: arith.h:77
Poly::kind
int kind
Definition: poly.h:28
advance
#define advance(A, B, N)
Definition: poly.c:367
polyFree
void polyFree()
Definition: poly.c:35
polygon_t
Definition: types.h:146
boxf::UR
pointf UR
Definition: geom.h:35
boxf
Definition: geom.h:35
N_GNEW
#define N_GNEW(n, t)
Definition: agxbuf.c:20
Generated by   doxygen 1.8.5