Graphviz  2.35.20130930.0449
legal.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 #include "neato.h"
15 #include "pathutil.h"
16 #include <setjmp.h>
17 
18 static jmp_buf jbuf;
19 
20 #define MAXINTS 10000 /* modify this line to reflect the max no. of
21  intersections you want reported -- 50000 seems to break the program */
22 
23 #define SLOPE(p,q) ( ( ( p.y ) - ( q.y ) ) / ( ( p.x ) - ( q.x ) ) )
24 
25 #define EQ_PT(v,w) (((v).x == (w).x) && ((v).y == (w).y))
26 
27 #define after(v) (((v)==((v)->poly->finish))?((v)->poly->start):((v)+1))
28 #define prior(v) (((v)==((v)->poly->start))?((v)->poly->finish):((v)-1))
29 
30 typedef struct active_edge active_edge;
31 typedef struct polygon polygon;
32 
33  typedef struct {
37  } vertex ;
38 
39  struct polygon {
42  };
43 
44  typedef struct {
45  vertex *firstv, *secondv;
46 #ifdef RECORD_INTERSECTS
47  polygon *firstp, *secondp;
48 #endif
49  double x, y;
50  } intersection ;
51 
52  struct active_edge {
54  struct active_edge *next, *last;
55  };
56  typedef struct active_edge_list {
57  active_edge *first, *final;
58  int number;
60  typedef struct {
61  int nvertices, npolygons, ninters;
62  } data ;
63 
64 
65 /* find the sign of the area of each of the triangles
66  formed by adding a vertex of m to l
67  also find the sign of their product */
68 static void sgnarea(vertex *l, vertex *m, int i[])
69 {
70  double a, b, c, d, e, f, g, h, t;
71  a = l->pos.x;
72  b = l->pos.y;
73  c = after(l)->pos.x - a;
74  d = after(l)->pos.y - b;
75  e = m->pos.x - a;
76  f = m->pos.y - b;
77  g = after(m)->pos.x - a;
78  h = after(m)->pos.y - b;
79  t = (c * f) - (d * e);
80  i[0] = ((t == 0) ? 0 : (t > 0 ? 1 : -1));
81  t = (c * h) - (d * g);
82  i[1] = ((t == 0) ? 0 : (t > 0 ? 1 : -1));
83  i[2] = i[0] * i[1];
84 }
85 
86 /* determine if g lies between f and h */
87 static int between(double f, double g, double h)
88 {
89  if ((f == g) || (g == h))
90  return (0);
91  return ((f < g) ? (g < h ? 1 : -1) : (h < g ? 1 : -1));
92 }
93 
94 /* determine if vertex i of line m is on line l */
95 static int online(vertex *l, vertex *m, int i)
96 {
97  pointf a, b, c;
98  a = l->pos;
99  b = after(l)->pos;
100  c = (i == 0) ? m->pos : after(m)->pos;
101  return ((a.x == b.x) ? ((a.x == c.x)
102  && (-1 !=
103  between(a.y, c.y, b.y))) : between(a.x,
104  c.x,
105  b.x));
106 }
107 
108 /* determine point of detected intersections */
109 static int intpoint(vertex *l, vertex *m, double *x, double *y, int cond)
110 {
111  pointf ls, le, ms, me, pt1, pt2;
112  double m1, m2, c1, c2;
113 
114  if (cond <= 0)
115  return (0);
116  ls = l->pos;
117  le = after(l)->pos;
118  ms = m->pos;
119  me = after(m)->pos;
120 
121  switch (cond) {
122 
123  case 3: /* a simple intersection */
124  if (ls.x == le.x) {
125  *x = ls.x;
126  *y = me.y + SLOPE(ms, me) * (*x - me.x);
127  } else if (ms.x == me.x) {
128  *x = ms.x;
129  *y = le.y + SLOPE(ls, le) * (*x - le.x);
130  } else {
131  m1 = SLOPE(ms, me);
132  m2 = SLOPE(ls, le);
133  c1 = ms.y - (m1 * ms.x);
134  c2 = ls.y - (m2 * ls.x);
135  *x = (c2 - c1) / (m1 - m2);
136  *y = ((m1 * c2) - (c1 * m2)) / (m1 - m2);
137  }
138  break;
139 
140  case 2: /* the two lines have a common segment */
141  if (online(l, m, 0) == -1) { /* ms between ls and le */
142  pt1 = ms;
143  pt2 =
144  (online(m, l, 1) ==
145  -1) ? ((online(m, l, 0) == -1) ? le : ls) : me;
146  } else if (online(l, m, 1) == -1) { /* me between ls and le */
147  pt1 = me;
148  pt2 =
149  (online(l, m, 0) ==
150  -1) ? ((online(m, l, 0) == -1) ? le : ls) : ms;
151  } else {
152  /* may be degenerate? */
153  if (online(m, l, 0) != -1)
154  return 0;
155  pt1 = ls;
156  pt2 = le;
157  }
158 
159  *x = (pt1.x + pt2.x) / 2;
160  *y = (pt1.y + pt2.y) / 2;
161  break;
162 
163  case 1: /* a vertex of line m is on line l */
164  if ((ls.x - le.x) * (ms.y - ls.y) == (ls.y - le.y) * (ms.x - ls.x)) {
165  *x = ms.x;
166  *y = ms.y;
167  } else {
168  *x = me.x;
169  *y = me.y;
170  }
171  } /* end switch */
172  return (1);
173 }
174 
175 static void
176 putSeg (int i, vertex* v)
177 {
178  fprintf(stderr, "seg#%d : (%.3f, %.3f) (%.3f, %.3f)\n",
179  i, v->pos.x, v->pos.y, after(v)->pos.x, after(v)->pos.y);
180 }
181 
182 /* realIntersect:
183  * Return 1 if a real inatersection has been found
184  */
185 static int
186 realIntersect (vertex *firstv, vertex *secondv, pointf p)
187 {
188  pointf vft, vsd, avft, avsd;
189 
190  vft = firstv->pos;
191  avft = after(firstv)->pos;
192  vsd = secondv->pos;
193  avsd = after(secondv)->pos;
194 
195  if (((vft.x != avft.x) && (vsd.x != avsd.x)) ||
196  ((vft.x == avft.x) &&
197  !EQ_PT(vft, p) &&
198  !EQ_PT(avft, p)) ||
199  ((vsd.x == avsd.x) &&
200  !EQ_PT(vsd, p) && !EQ_PT(avsd, p)))
201  {
202  if (Verbose > 1) {
203  fprintf(stderr, "\nintersection at %.3f %.3f\n",
204  p.x, p.y);
205  putSeg (1, firstv);
206  putSeg (2, secondv);
207  }
208  return 1;
209  }
210  else return 0;
211 }
212 
213 /* find_intersection:
214  * detect whether segments l and m intersect
215  * Return 1 if found; 0 otherwise;
216  */
217 static int find_intersection(vertex *l,
218  vertex *m,
219  intersection* ilist, data *input)
220 {
221  double x, y;
222  pointf p;
223  int i[3];
224  sgnarea(l, m, i);
225 
226  if (i[2] > 0)
227  return 0;
228 
229  if (i[2] < 0) {
230  sgnarea(m, l, i);
231  if (i[2] > 0)
232  return 0;
233  if (!intpoint
234  (l, m, &x, &y, (i[2] < 0) ? 3 : online(m, l, ABS(i[0]))))
235  return 0;
236  }
237 
238  else if (!intpoint(l, m, &x, &y, (i[0] == i[1]) ?
239  2 * MAX(online(l, m, 0),
240  online(l, m, 1)) : online(l, m, ABS(i[0]))))
241  return 0;
242 
243 #ifdef RECORD_INTERSECTS
244  if (input->ninters >= MAXINTS) {
245  agerr(AGERR, "using too many intersections\n");
246  exit(1);
247  }
248 
249  ilist[input->ninters].firstv = l;
250  ilist[input->ninters].secondv = m;
251  ilist[input->ninters].firstp = l->poly;
252  ilist[input->ninters].secondp = m->poly;
253  ilist[input->ninters].x = x;
254  ilist[input->ninters].y = y;
255  input->ninters++;
256 #endif
257  p.x = x;
258  p.y = y;
259  return realIntersect(l, m, p);
260 }
261 
262 static int gt(vertex **i, vertex **j)
263 {
264  /* i > j if i.x > j.x or i.x = j.x and i.y > j.y */
265  double t;
266  if ((t = (*i)->pos.x - (*j)->pos.x) != 0.)
267  return ((t > 0.) ? 1 : -1);
268  if ((t = (*i)->pos.y - (*j)->pos.y) == 0.)
269  return (0);
270  else
271  return ((t > 0.) ? 1 : -1);
272 }
273 
274 /* find_ints:
275  * Check for pairwise intersection of polygon sides
276  * Return 1 if intersection found, 0 otherwise.
277  */
278 static int
279 find_ints(vertex vertex_list[],
280  polygon polygon_list[],
281  data *input, intersection ilist[])
282 {
283  int i, j, k, found = 0;
284  active_edge_list all;
285  active_edge *new, *tempa;
286  vertex *pt1, *pt2, *templ, **pvertex;
287 
288  input->ninters = 0;
289  all.first = all.final = 0;
290  all.number = 0;
291 
292  pvertex = N_GNEW(input->nvertices, vertex *);
293 
294  for (i = 0; i < input->nvertices; i++)
295  pvertex[i] = vertex_list + i;
296 
297 /* sort vertices by x coordinate */
298  qsort(pvertex, input->nvertices, sizeof(vertex *),
299  (int (*)(const void *, const void *))gt);
300 
301 /* walk through the vertices in order of increasing x coordinate */
302  for (i = 0; i < input->nvertices; i++) {
303  pt1 = pvertex[i];
304  templ = pt2 = prior(pvertex[i]);
305  for (k = 0; k < 2; k++) { /* each vertex has 2 edges */
306  switch (gt(&pt1, &pt2)) {
307 
308  case -1: /* forward edge, test and insert */
309 
310  /* test */
311  for (tempa = all.first, j = 0; j < all.number;
312  j++, tempa = tempa->next) {
313  found = find_intersection(tempa->name, templ, ilist, input);
314  if (found)
315  goto finish;
316  }
317 
318  new = GNEW(active_edge);
319  if (all.number == 0) {
320  all.first = new;
321  new->last = 0;
322  } /* insert */
323  else {
324  all.final->next = new;
325  new->last = all.final;
326  }
327 
328  new->name = templ;
329  new->next = 0;
330  templ->active = new;
331  all.final = new;
332  all.number++;
333 
334  break; /* end of case -1 */
335 
336  case 1: /* backward edge, delete */
337 
338  if ((tempa = templ->active) == 0) {
339  agerr(AGERR, "trying to delete a non-line\n");
340  longjmp(jbuf, 1);
341  }
342  if (all.number == 1)
343  all.final = all.first = 0; /* delete the line */
344  else if (tempa == all.first) {
345  all.first = all.first->next;
346  all.first->last = 0;
347  } else if (tempa == all.final) {
348  all.final = all.final->last;
349  all.final->next = 0;
350  } else {
351  tempa->last->next = tempa->next;
352  tempa->next->last = tempa->last;
353  }
354  free((char *) tempa);
355  all.number--;
356  templ->active = 0;
357  break; /* end of case 1 */
358 
359  } /* end switch */
360 
361  pt2 = after(pvertex[i]);
362  templ = pvertex[i]; /*second neighbor */
363  } /* end k for loop */
364  } /* end i for loop */
365 
366 finish :
367  for (tempa = all.first, j = 0; j < all.number;
368  j++, tempa = new) {
369  new = tempa->next;
370  free (tempa);
371  }
372  free (pvertex);
373  return found;
374 }
375 
376 #define INBOX(p,bb) ((p.x <= bb.UR.x) && (p.x >= bb.LL.x) && (p.y <= bb.UR.y) && (p.y >= bb.LL.y))
377 #define NESTED(a,b) (INBOX(a.LL,b) && INBOX(a.UR,b))
378 
379 /* findInside:
380  * Check if one polygon is inside another. We know that each
381  * pair is either disjoint or one is inside the other.
382  * Return 1 if an intersection is found, 0 otherwise.
383  */
384 static int
385 findInside(Ppoly_t ** polys, int n_polys, polygon* polygon_list)
386 {
387  int i, j;
388  pointf pt;
389  Ppoly_t* p1;
390  Ppoly_t* p2;
391 
392  for (i = 0; i < n_polys; i++) {
393  p1 = polys[i];
394  pt = p1->ps[0];
395  for (j = i+1; j < n_polys; j++) {
396  p2 = polys[j];
397  if (NESTED(polygon_list[i].bb,polygon_list[j].bb)) {
398  if (in_poly(*p2, pt)) return 1;
399  }
400  else if (NESTED(polygon_list[j].bb,polygon_list[i].bb)) {
401  if (in_poly(*p1, p2->ps[0])) return 1;
402  }
403  }
404  }
405  return 0;
406 }
407 
408 /* Plegal_arrangement:
409  * Check that none of the polygons overlap.
410  * Return 1 if okay; 0 otherwise.
411  */
412 int Plegal_arrangement(Ppoly_t ** polys, int n_polys)
413 {
414  int i, j, vno, nverts, found;
415  vertex *vertex_list;
416  polygon *polygon_list;
417  data input;
418  intersection ilist[MAXINTS];
419  boxf bb;
420  double x, y;
421 
422  polygon_list = N_GNEW(n_polys, polygon);
423 
424  for (i = nverts = 0; i < n_polys; i++)
425  nverts += polys[i]->pn;
426 
427  vertex_list = N_GNEW(nverts, vertex);
428 
429  for (i = vno = 0; i < n_polys; i++) {
430  polygon_list[i].start = &vertex_list[vno];
431  bb.LL.x = bb.LL.y = MAXDOUBLE;
432  bb.UR.x = bb.UR.y = -MAXDOUBLE;
433  for (j = 0; j < polys[i]->pn; j++) {
434  x = polys[i]->ps[j].x;
435  y = polys[i]->ps[j].y;
436  bb.LL.x = MIN(bb.LL.x,x);
437  bb.LL.y = MIN(bb.LL.y,y);
438  bb.UR.x = MAX(bb.UR.x,x);
439  bb.UR.y = MAX(bb.UR.y,y);
440  vertex_list[vno].pos.x = x;
441  vertex_list[vno].pos.y = y;
442  vertex_list[vno].poly = &polygon_list[i];
443  vertex_list[vno].active = 0;
444  vno++;
445  }
446  polygon_list[i].finish = &vertex_list[vno - 1];
447  polygon_list[i].bb = bb;
448  }
449 
450  input.nvertices = nverts;
451  input.npolygons = n_polys;
452 
453  if (setjmp(jbuf)) {
454  free(polygon_list);
455  free(vertex_list);
456  return 0;
457  }
458  found = find_ints(vertex_list, polygon_list, &input, ilist);
459 
460  if (!found) {
461  found = findInside(polys, n_polys, polygon_list);
462  }
463  free(polygon_list);
464  free(vertex_list);
465 
466  return !found;
467 }