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 <stdio.h>
15 #include <stdlib.h>
16 #include "simple.h"
17
18 /* this is all out of pathgeom.h and will eventually get included */
19
20 typedef struct Pxy_t {
21 double x, y;
22 } Pxy_t;
23
24 typedef struct Pxy_t Ppoint_t;
25 typedef struct Pxy_t Pvector_t;
26
27 typedef struct Ppoly_t {
28 Ppoint_t *ps;
29 int pn;
30 } Ppoly_t;
31
32 typedef Ppoly_t Ppolyline_t;
33
34 typedef struct Pedge_t {
35 Ppoint_t a, b;
36 } Pedge_t;
37
38
39 #ifdef NOTDEF
main(int argc,char ** argv)40 int main(int argc, char **argv)
41 {
42 Ppoly_t polys[2], *polys_ptr[2];
43
44 polys[0].ps = (Ppoint_t *) malloc(3 * sizeof(Ppoint_t));
45 polys[1].ps = (Ppoint_t *) malloc(3 * sizeof(Ppoint_t));
46 polys[0].pn = 3;
47 polys[1].pn = 3;
48
49 polys[0].ps[0].x = 0.0;
50 polys[0].ps[0].y = 0.0;
51 polys[0].ps[1].x = 0.0;
52 polys[0].ps[1].y = 100.0;
53 polys[0].ps[2].x = 100.0;
54 polys[0].ps[2].y = 0.0;
55
56 polys[1].ps[0].x = 70.0;
57 polys[1].ps[0].y = 70.0;
58 polys[1].ps[1].x = 70.0;
59 polys[1].ps[1].y = 100.0;
60 polys[1].ps[2].x = 100.0;
61 polys[1].ps[2].y = 70.0;
62
63 polys_ptr[0] = &polys[0];
64 polys_ptr[1] = &polys[1];
65
66 if (Plegal_arrangement(polys_ptr, 2))
67 printf(" it is legal\n");
68 else
69 printf(" it is not legal\n");
70 }
71 #endif
72
73 #ifdef NOTDEF
after(struct vertex * v)74 struct vertex *after(struct vertex *v)
75 {
76 if (v == v->poly->finish)
77 return v->poly->start;
78 else
79 return v + 1;
80 }
81
before(struct vertex * v)82 struct vertex *before(struct vertex *v)
83 {
84 if (v == v->poly->start)
85 return v->poly->finish;
86 else
87 return v - 1;
88 }
89 #endif
90
91 void find_ints(struct vertex vertex_list[], struct polygon polygon_list[],
92 struct data *input, struct intersection ilist[]);
93
Plegal_arrangement(Ppoly_t ** polys,int n_polys)94 int Plegal_arrangement(Ppoly_t ** polys, int n_polys)
95 {
96
97 int i, j, vno, nverts, rv;
98
99 struct vertex *vertex_list;
100 struct polygon *polygon_list;
101 struct data input;
102 struct intersection ilist[10000];
103
104 polygon_list = (struct polygon *)
105 malloc(n_polys * sizeof(struct polygon));
106
107 for (i = nverts = 0; i < n_polys; i++)
108 nverts += polys[i]->pn;
109
110 vertex_list = (struct vertex *)
111 malloc(nverts * sizeof(struct vertex));
112
113 for (i = vno = 0; i < n_polys; i++) {
114 polygon_list[i].start = &vertex_list[vno];
115 for (j = 0; j < polys[i]->pn; j++) {
116 vertex_list[vno].pos.x = polys[i]->ps[j].x;
117 vertex_list[vno].pos.y = polys[i]->ps[j].y;
118 vertex_list[vno].poly = &polygon_list[i];
119 vno++;
120 }
121 polygon_list[i].finish = &vertex_list[vno - 1];
122 }
123
124 input.nvertices = nverts;
125 input.npolygons = n_polys;
126
127 find_ints(vertex_list, polygon_list, &input, ilist);
128
129
130 #define EQ_PT(v,w) (((v).x == (w).x) && ((v).y == (w).y))
131 rv = 1;
132 {
133 int i;
134 struct position vft, vsd, avft, avsd;
135 for (i = 0; i < input.ninters; i++) {
136 vft = ilist[i].firstv->pos;
137 avft = after(ilist[i].firstv)->pos;
138 vsd = ilist[i].secondv->pos;
139 avsd = after(ilist[i].secondv)->pos;
140 if (((vft.x != avft.x) && (vsd.x != avsd.x)) ||
141 ((vft.x == avft.x) &&
142 !EQ_PT(vft, ilist[i]) &&
143 !EQ_PT(avft, ilist[i])) ||
144 ((vsd.x == avsd.x) &&
145 !EQ_PT(vsd, ilist[i]) && !EQ_PT(avsd, ilist[i]))) {
146 rv = 0;
147 fprintf(stderr, "\nintersection %d at %.3f %.3f\n",
148 i, ilist[i].x, ilist[i].y);
149 fprintf(stderr, "seg#1 : (%.3f, %.3f) (%.3f, %.3f)\n",
150 (double) (ilist[i].firstv->pos.x)
151 , (double) (ilist[i].firstv->pos.y)
152 , (double) (after(ilist[i].firstv)->pos.x)
153 , (double) (after(ilist[i].firstv)->pos.y));
154 fprintf(stderr, "seg#2 : (%.3f, %.3f) (%.3f, %.3f)\n",
155 (double) (ilist[i].secondv->pos.x)
156 , (double) (ilist[i].secondv->pos.y)
157 , (double) (after(ilist[i].secondv)->pos.x)
158 , (double) (after(ilist[i].secondv)->pos.y));
159 }
160 }
161 }
162 free(polygon_list);
163 free(vertex_list);
164 return rv;
165 }
166