Graphviz 14.0.1~dev.20250923.2039
Loading...
Searching...
No Matches
legal.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 <assert.h>
12#include <float.h>
13#include <math.h>
14#include <limits.h>
15#include <neatogen/neato.h>
16#include <pathplan/pathutil.h>
17#include <stdbool.h>
18#include <stddef.h>
19#include <util/alloc.h>
20#include <util/exit.h>
21#include <util/list.h>
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 polygon polygon;
31
32 typedef struct vertex {
35 struct vertex *active;
37
38 struct polygon {
41 };
42
43static int sign(double v) {
44 if (v < 0)
45 return -1;
46 if (v > 0)
47 return 1;
48 return 0;
49}
50
51/* find the sign of the area of each of the triangles
52 formed by adding a vertex of m to l
53 also find the sign of their product */
54static void sgnarea(vertex *l, vertex *m, int i[])
55{
56 double a, b, c, d, e, f, g, h, t;
57 a = l->pos.x;
58 b = l->pos.y;
59 c = after(l)->pos.x - a;
60 d = after(l)->pos.y - b;
61 e = m->pos.x - a;
62 f = m->pos.y - b;
63 g = after(m)->pos.x - a;
64 h = after(m)->pos.y - b;
65 t = c * f - d * e;
66 i[0] = sign(t);
67 t = c * h - d * g;
68 i[1] = sign(t);
69 i[2] = i[0] * i[1];
70}
71
84static int between(double f, double g, double h) {
85 if (f < g) {
86 if (g < h) {
87 return 1;
88 }
89 if (g > h) {
90 return -1;
91 }
92 return 0;
93 }
94 if (f > g) {
95 if (g > h) {
96 return 1;
97 }
98 if (g < h) {
99 return -1;
100 }
101 return 0;
102 }
103 return 0;
104}
105
106/* determine if vertex i of line m is on line l */
107static int online(vertex *l, vertex *m, int i)
108{
109 pointf a, b, c;
110 a = l->pos;
111 b = after(l)->pos;
112 c = i == 0 ? m->pos : after(m)->pos;
113 return a.x == b.x
114 ? (a.x == c.x && -1 != between(a.y, c.y, b.y))
115 : between(a.x, c.x, b.x);
116}
117
118/* determine point of detected intersections */
119static int intpoint(vertex *l, vertex *m, double *x, double *y, int cond)
120{
121 pointf ls, le, ms, me, pt1, pt2;
122 double m1, m2, c1, c2;
123
124 if (cond <= 0)
125 return 0;
126 ls = l->pos;
127 le = after(l)->pos;
128 ms = m->pos;
129 me = after(m)->pos;
130
131 switch (cond) {
132
133 case 3: /* a simple intersection */
134 if (ls.x == le.x) {
135 *x = ls.x;
136 *y = me.y + SLOPE(ms, me) * (*x - me.x);
137 } else if (ms.x == me.x) {
138 *x = ms.x;
139 *y = le.y + SLOPE(ls, le) * (*x - le.x);
140 } else {
141 m1 = SLOPE(ms, me);
142 m2 = SLOPE(ls, le);
143 c1 = ms.y - m1 * ms.x;
144 c2 = ls.y - m2 * ls.x;
145 *x = (c2 - c1) / (m1 - m2);
146 *y = (m1 * c2 - c1 * m2) / (m1 - m2);
147 }
148 break;
149
150 case 2: /* the two lines have a common segment */
151 if (online(l, m, 0) == -1) { /* ms between ls and le */
152 pt1 = ms;
153 pt2 = online(m, l, 1) == -1
154 ? (online(m, l, 0) == -1 ? le : ls) : me;
155 } else if (online(l, m, 1) == -1) { /* me between ls and le */
156 pt1 = me;
157 pt2 = online(l, m, 0) == -1
158 ? (online(m, l, 0) == -1 ? le : ls) : ms;
159 } else {
160 /* may be degenerate? */
161 if (online(m, l, 0) != -1)
162 return 0;
163 pt1 = ls;
164 pt2 = le;
165 }
166
167 *x = (pt1.x + pt2.x) / 2;
168 *y = (pt1.y + pt2.y) / 2;
169 break;
170
171 case 1: /* a vertex of line m is on line l */
172 if ((ls.x - le.x) * (ms.y - ls.y) == (ls.y - le.y) * (ms.x - ls.x)) {
173 *x = ms.x;
174 *y = ms.y;
175 } else {
176 *x = me.x;
177 *y = me.y;
178 }
179 } /* end switch */
180 return 1;
181}
182
183static void
184putSeg (int i, vertex* v)
185{
186 fprintf(stderr, "seg#%d : (%.3f, %.3f) (%.3f, %.3f)\n",
187 i, v->pos.x, v->pos.y, after(v)->pos.x, after(v)->pos.y);
188}
189
190/* realIntersect:
191 * Return true if a real intersection has been found
192 */
193static bool realIntersect(vertex *firstv, vertex *secondv, pointf p) {
194 const pointf vft = firstv->pos;
195 const pointf avft = after(firstv)->pos;
196 const pointf vsd = secondv->pos;
197 const pointf avsd = after(secondv)->pos;
198
199 if ((vft.x != avft.x && vsd.x != avsd.x) ||
200 (vft.x == avft.x && !EQ_PT(vft, p) && !EQ_PT(avft, p)) ||
201 (vsd.x == avsd.x && !EQ_PT(vsd, p) && !EQ_PT(avsd, p)))
202 {
203 if (Verbose > 1) {
204 fprintf(stderr, "\nintersection at %.3f %.3f\n",
205 p.x, p.y);
206 putSeg (1, firstv);
207 putSeg (2, secondv);
208 }
209 return true;
210 }
211 return false;
212}
213
214/* find_intersection:
215 * detect whether segments l and m intersect
216 * Return true if found; false otherwise;
217 */
218static bool find_intersection(vertex *l, vertex *m) {
219 double x, y;
220 int i[3];
221 sgnarea(l, m, i);
222
223 if (i[2] > 0)
224 return false;
225
226 if (i[2] < 0) {
227 sgnarea(m, l, i);
228 if (i[2] > 0)
229 return false;
230 if (!intpoint(l, m, &x, &y, i[2] < 0 ? 3 : online(m, l, abs(i[0]))))
231 return false;
232 }
233
234 else if (!intpoint(l, m, &x, &y, i[0] == i[1] ?
235 2 * MAX(online(l, m, 0),
236 online(l, m, 1)) : online(l, m, abs(i[0]))))
237 return false;
238
239 return realIntersect(l, m, (pointf){.x = x, .y = y});
240}
241
242static int gt(const void *a, const void *b) {
243 const vertex *const *i = a;
244 const vertex *const *j = b;
245 if ((*i)->pos.x > (*j)->pos.x) {
246 return 1;
247 }
248 if ((*i)->pos.x < (*j)->pos.x) {
249 return -1;
250 }
251 if ((*i)->pos.y > (*j)->pos.y) {
252 return 1;
253 }
254 if ((*i)->pos.y < (*j)->pos.y) {
255 return -1;
256 }
257 return 0;
258}
259
260/* find_ints:
261 * Check for pairwise intersection of polygon sides
262 * Return 1 if intersection found, 0 for not found, -1 for error.
263 */
264static int find_ints(vertex vertex_list[], size_t nvertices) {
265 int found = 0;
266 LIST(vertex *) all = {0};
267 vertex *tempa;
268
269 vertex **pvertex = gv_calloc(nvertices, sizeof(vertex*));
270
271 for (size_t i = 0; i < nvertices; i++)
272 pvertex[i] = vertex_list + i;
273
274/* sort vertices by x coordinate */
275 qsort(pvertex, nvertices, sizeof(vertex *), gt);
276
277/* walk through the vertices in order of increasing x coordinate */
278 for (size_t i = 0; i < nvertices; i++) {
279 vertex *const pt1 = pvertex[i];
280 vertex *pt2 = prior(pvertex[i]);
281 vertex *templ = pt2;
282 for (int k = 0; k < 2; k++) { // each vertex has 2 edges
283 switch (gt(&pt1, &pt2)) {
284
285 case -1: /* forward edge, test and insert */
286
287 /* test */
288 for (size_t j = 0; j < LIST_SIZE(&all); ++j) {
289 tempa = LIST_GET(&all, j);
290 found = find_intersection(tempa, templ);
291 if (found)
292 goto finish;
293 }
294
295 LIST_APPEND(&all, templ);
296 templ->active = templ;
297 break;
298
299 case 1: /* backward edge, delete */
300
301 if ((tempa = templ->active) == 0) {
302 agerrorf("trying to delete a non-line\n");
303 return -1;
304 }
305 LIST_REMOVE(&all, tempa);
306 templ->active = 0;
307 break;
308
309 default:
310 break; // same point; do nothing
311
312 }
313
314 pt2 = after(pvertex[i]);
315 templ = pvertex[i]; /*second neighbor */
316 }
317 }
318
319finish :
320 LIST_FREE(&all);
321 free (pvertex);
322 return found;
323}
324
325#define INBOX(p,bb) ((p.x <= bb.UR.x) && (p.x >= bb.LL.x) && (p.y <= bb.UR.y) && (p.y >= bb.LL.y))
326#define NESTED(a,b) (INBOX(a.LL,b) && INBOX(a.UR,b))
327
328/* findInside:
329 * Check if one polygon is inside another. We know that each
330 * pair is either disjoint or one is inside the other.
331 * Return 1 if an intersection is found, 0 otherwise.
332 */
333static int
334findInside(Ppoly_t ** polys, int n_polys, polygon* polygon_list)
335{
336 int i, j;
337 pointf pt;
338 Ppoly_t* p1;
339 Ppoly_t* p2;
340
341 for (i = 0; i < n_polys; i++) {
342 p1 = polys[i];
343 pt = p1->ps[0];
344 for (j = i+1; j < n_polys; j++) {
345 p2 = polys[j];
346 if (NESTED(polygon_list[i].bb,polygon_list[j].bb)) {
347 if (in_poly(*p2, pt)) return 1;
348 }
349 else if (NESTED(polygon_list[j].bb,polygon_list[i].bb)) {
350 if (in_poly(*p1, p2->ps[0])) return 1;
351 }
352 }
353 }
354 return 0;
355}
356
357/* Plegal_arrangement:
358 * Check that none of the polygons overlap.
359 * Return 1 if okay; 0 otherwise.
360 */
361int Plegal_arrangement(Ppoly_t ** polys, int n_polys)
362{
363 int i, vno, found;
364 boxf bb;
365 double x, y;
366
367 polygon *polygon_list = gv_calloc(n_polys, sizeof(polygon));
368
369 size_t nverts;
370 for (nverts = 0, i = 0; i < n_polys; i++) {
371 nverts += polys[i]->pn;
372 }
373
374 vertex *vertex_list = gv_calloc(nverts, sizeof(vertex));
375
376 for (i = vno = 0; i < n_polys; i++) {
377 polygon_list[i].start = &vertex_list[vno];
378 bb.LL.x = bb.LL.y = DBL_MAX;
379 bb.UR.x = bb.UR.y = -DBL_MAX;
380 for (size_t j = 0; j < polys[i]->pn; j++) {
381 x = polys[i]->ps[j].x;
382 y = polys[i]->ps[j].y;
383 bb.LL.x = fmin(bb.LL.x,x);
384 bb.LL.y = fmin(bb.LL.y,y);
385 bb.UR.x = fmax(bb.UR.x,x);
386 bb.UR.y = fmax(bb.UR.y,y);
387 vertex_list[vno].pos.x = x;
388 vertex_list[vno].pos.y = y;
389 vertex_list[vno].poly = &polygon_list[i];
390 vertex_list[vno].active = 0;
391 vno++;
392 }
393 polygon_list[i].finish = &vertex_list[vno - 1];
394 polygon_list[i].bb = bb;
395 }
396
397 found = find_ints(vertex_list, nverts);
398 if (found < 0) {
399 free(polygon_list);
400 free(vertex_list);
401 return 0;
402 }
403
404 if (!found) {
405 found = findInside(polys, n_polys, polygon_list);
406 }
407 free(polygon_list);
408 free(vertex_list);
409
410 return !found;
411}
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
#define le
Definition edges.h:33
static bool Verbose
Definition gml2gv.c:24
void free(void *)
void agerrorf(const char *fmt,...)
Definition agerror.c:165
bool in_poly(const Ppoly_t poly, Ppoint_t q)
Definition inpoly.c:24
static int between(double f, double g, double h)
Definition legal.c:84
static int intpoint(vertex *l, vertex *m, double *x, double *y, int cond)
Definition legal.c:119
static int find_ints(vertex vertex_list[], size_t nvertices)
Definition legal.c:264
static int gt(const void *a, const void *b)
Definition legal.c:242
static void sgnarea(vertex *l, vertex *m, int i[])
Definition legal.c:54
#define after(v)
Definition legal.c:27
static bool find_intersection(vertex *l, vertex *m)
Definition legal.c:218
int Plegal_arrangement(Ppoly_t **polys, int n_polys)
Definition legal.c:361
static bool realIntersect(vertex *firstv, vertex *secondv, pointf p)
Definition legal.c:193
static int sign(double v)
Definition legal.c:43
static int online(vertex *l, vertex *m, int i)
Definition legal.c:107
#define SLOPE(p, q)
Definition legal.c:23
struct vertex vertex
static void putSeg(int i, vertex *v)
Definition legal.c:184
static int findInside(Ppoly_t **polys, int n_polys, polygon *polygon_list)
Definition legal.c:334
#define NESTED(a, b)
Definition legal.c:326
#define prior(v)
Definition legal.c:28
#define EQ_PT(v, w)
Definition legal.c:25
type-generic dynamically expanding list
#define LIST(type)
Definition list.h:55
#define LIST_SIZE(list)
Definition list.h:80
#define LIST_APPEND(list, item)
Definition list.h:132
#define LIST_FREE(list)
Definition list.h:379
#define LIST_REMOVE(list, item)
Definition list.h:227
#define LIST_GET(list, index)
Definition list.h:165
static size_t nvertices
Definition site.c:20
size_t pn
Definition pathgeom.h:47
Ppoint_t * ps
Definition pathgeom.h:46
double x
Definition pathgeom.h:38
double y
Definition pathgeom.h:38
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
vertex * finish
Definition legal.c:39
boxf bb
Definition legal.c:40
vertex * start
Definition legal.c:39
Definition legal.c:32
pointf pos
Definition legal.c:33
polygon * poly
Definition legal.c:34
struct vertex * active
Definition legal.c:35
#define MAX(a, b)
Definition write.c:32