23#define SLOPE(p,q) ( ( ( p.y ) - ( q.y ) ) / ( ( p.x ) - ( q.x ) ) )
25#define EQ_PT(v,w) (((v).x == (w).x) && ((v).y == (w).y))
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))
56 double a, b, c, d, e, f, g, h, t;
59 c =
after(l)->pos.x - a;
60 d =
after(l)->pos.y - b;
63 g =
after(m)->pos.x - a;
64 h =
after(m)->pos.y - b;
84static int between(
double f,
double g,
double h) {
112 c = i == 0 ? m->
pos :
after(m)->pos;
122 double m1, m2, c1, c2;
136 *y = me.
y +
SLOPE(ms, me) * (*x - me.
x);
137 }
else if (ms.
x == me.
x) {
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);
151 if (
online(l, m, 0) == -1) {
153 pt2 =
online(m, l, 1) == -1
154 ? (
online(m, l, 0) == -1 ?
le : ls) : me;
155 }
else if (
online(l, m, 1) == -1) {
157 pt2 =
online(l, m, 0) == -1
158 ? (
online(m, l, 0) == -1 ?
le : ls) : ms;
161 if (
online(m, l, 0) != -1)
167 *x = (pt1.
x + pt2.
x) / 2;
168 *y = (pt1.
y + pt2.
y) / 2;
172 if ((ls.
x -
le.x) * (ms.
y - ls.
y) == (ls.
y -
le.y) * (ms.
x - ls.
x)) {
186 fprintf(stderr,
"seg#%d : (%.3f, %.3f) (%.3f, %.3f)\n",
199 if ((vft.
x != avft.
x && vsd.
x != avsd.
x) ||
200 (vft.
x == avft.
x && !
EQ_PT(vft, p) && !
EQ_PT(avft, p)) ||
204 fprintf(stderr,
"\nintersection at %.3f %.3f\n",
230 if (!
intpoint(l, m, &x, &y, i[2] < 0 ? 3 :
online(m, l, abs(i[0]))))
234 else if (!
intpoint(l, m, &x, &y, i[0] == i[1] ?
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) {
248 if ((*i)->pos.x < (*j)->pos.x) {
251 if ((*i)->pos.y > (*j)->pos.y) {
254 if ((*i)->pos.y < (*j)->pos.y) {
272 pvertex[i] = vertex_list + i;
279 vertex *
const pt1 = pvertex[i];
282 for (
int k = 0; k < 2; k++) {
283 switch (
gt(&pt1, &pt2)) {
288 for (
size_t j = 0; j <
LIST_SIZE(&all); ++j) {
301 if ((tempa = templ->
active) == 0) {
302 agerrorf(
"trying to delete a non-line\n");
314 pt2 =
after(pvertex[i]);
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))
341 for (i = 0; i < n_polys; i++) {
344 for (j = i+1; j < n_polys; j++) {
346 if (
NESTED(polygon_list[i].bb,polygon_list[j].bb)) {
347 if (
in_poly(*p2, pt))
return 1;
349 else if (
NESTED(polygon_list[j].bb,polygon_list[i].bb)) {
370 for (nverts = 0, i = 0; i < n_polys; i++) {
371 nverts += polys[i]->
pn;
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;
393 polygon_list[i].
finish = &vertex_list[vno - 1];
394 polygon_list[i].
bb = bb;
405 found =
findInside(polys, n_polys, polygon_list);
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
void agerrorf(const char *fmt,...)
bool in_poly(const Ppoly_t poly, Ppoint_t q)
static int between(double f, double g, double h)
static int intpoint(vertex *l, vertex *m, double *x, double *y, int cond)
static int find_ints(vertex vertex_list[], size_t nvertices)
static int gt(const void *a, const void *b)
static void sgnarea(vertex *l, vertex *m, int i[])
static bool find_intersection(vertex *l, vertex *m)
int Plegal_arrangement(Ppoly_t **polys, int n_polys)
static bool realIntersect(vertex *firstv, vertex *secondv, pointf p)
static int sign(double v)
static int online(vertex *l, vertex *m, int i)
static void putSeg(int i, vertex *v)
static int findInside(Ppoly_t **polys, int n_polys, polygon *polygon_list)
type-generic dynamically expanding list
#define LIST_APPEND(list, item)
#define LIST_REMOVE(list, item)
#define LIST_GET(list, index)