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
18static 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
30typedef struct active_edge active_edge;
31typedef struct polygon polygon;
32
33 typedef struct {
34 pointf pos;
35 polygon *poly;
36 active_edge *active;
37 } vertex ;
38
39 struct polygon {
40 vertex *start, *finish;
41 boxf bb;
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 {
53 vertex *name;
54 struct active_edge *next, *last;
55 };
56 typedef struct active_edge_list {
57 active_edge *first, *final;
58 int number;
59 } active_edge_list ;
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 */
68static 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 */
87static 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 */
95static 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 */
109static 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
175static void
176putSeg (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 */
185static int
186realIntersect (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 */
217static 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
262static 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 */
278static int
279find_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
366finish :
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 */
384static int
385findInside(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 */
412int 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}
468