legal.c

Go to the documentation of this file.

/*************************************************************************
 * Copyright (c) 2011 AT&T Intellectual Property 
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors: Details at https://graphviz.org
 *************************************************************************/
 
#include <assert.h>
#include <float.h>
#include <math.h>
#include <limits.h>
#include <neatogen/neato.h>
#include <pathplan/pathutil.h>
#include <stddef.h>
#include <util/alloc.h>
#include <util/exit.h>
 
#define SLOPE(p,q) ( ( ( p.y ) - ( q.y ) ) / ( ( p.x ) - ( q.x ) ) )
 
#define EQ_PT(v,w) (((v).x == (w).x) && ((v).y == (w).y))
 
#define after(v) (((v)==((v)->poly->finish))?((v)->poly->start):((v)+1))
#define prior(v) (((v)==((v)->poly->start))?((v)->poly->finish):((v)-1))
 
typedef struct active_edge active_edge;
typedef struct polygon polygon;
 
    typedef struct {
        pointf pos;
        polygon *poly;
        active_edge *active;
    } vertex ;
 
    struct polygon {
        vertex *start, *finish;
        boxf bb;
    };
 
    struct active_edge {
        vertex *name;
        struct active_edge *next, *last;
    };
    typedef struct active_edge_list {
        active_edge *first, *final;
        int number;
    } active_edge_list ;
    typedef struct {
        int nvertices, ninters;
    } data ;
 
static int sign(double v) {
  if (v < 0)
    return -1;
  if (v > 0)
    return 1;
  return 0;
}
 
/* find the sign of the area of each of the triangles
    formed by adding a vertex of m to l  
    also find the sign of their product  */
static void sgnarea(vertex *l, vertex *m, int i[])
{
    double a, b, c, d, e, f, g, h, t;
    a = l->pos.x;
    b = l->pos.y;
    c = after(l)->pos.x - a;
    d = after(l)->pos.y - b;
    e = m->pos.x - a;
    f = m->pos.y - b;
    g = after(m)->pos.x - a;
    h = after(m)->pos.y - b;
    t = c * f - d * e;
    i[0] = sign(t);
    t = c * h - d * g;
    i[1] = sign(t);
    i[2] = i[0] * i[1];
}
 
static int between(double f, double g, double h) {
  if (f < g) {
    if (g < h) {
      return 1;
    }
    if (g > h) {
      return -1;
    }
    return 0;
  }
  if (f > g) {
    if (g > h) {
      return 1;
    }
    if (g < h) {
      return -1;
    }
    return 0;
  }
  return 0;
}
 
/* determine if vertex i of line m is on line l     */
static int online(vertex *l, vertex *m, int i)
{
    pointf a, b, c;
    a = l->pos;
    b = after(l)->pos;
    c = i == 0 ? m->pos : after(m)->pos;
    return a.x == b.x
      ? (a.x == c.x && -1 != between(a.y, c.y, b.y))
      : between(a.x, c.x, b.x);
}
 
/* determine point of detected intersections  */
static int intpoint(vertex *l, vertex *m, double *x, double *y, int cond)
{
    pointf ls, le, ms, me, pt1, pt2;
    double m1, m2, c1, c2;
 
    if (cond <= 0)
        return 0;
    ls = l->pos;
    le = after(l)->pos;
    ms = m->pos;
    me = after(m)->pos;
 
    switch (cond) {
 
    case 3:                     /* a simple intersection        */
        if (ls.x == le.x) {
            *x = ls.x;
            *y = me.y + SLOPE(ms, me) * (*x - me.x);
        } else if (ms.x == me.x) {
            *x = ms.x;
            *y = le.y + SLOPE(ls, le) * (*x - le.x);
        } else {
            m1 = SLOPE(ms, me);
            m2 = SLOPE(ls, le);
            c1 = ms.y - m1 * ms.x;
            c2 = ls.y - m2 * ls.x;
            *x = (c2 - c1) / (m1 - m2);
            *y = (m1 * c2 - c1 * m2) / (m1 - m2);
        }
        break;
 
    case 2:                     /*     the two lines  have a common segment  */
        if (online(l, m, 0) == -1) {    /* ms between ls and le */
            pt1 = ms;
            pt2 = online(m, l, 1) == -1
              ? (online(m, l, 0) == -1 ? le : ls) : me;
        } else if (online(l, m, 1) == -1) {     /* me between ls and le */
            pt1 = me;
            pt2 = online(l, m, 0) == -1
              ? (online(m, l, 0) == -1 ? le : ls) : ms;
        } else {
            /* may be degenerate? */
            if (online(m, l, 0) != -1)
                return 0;
            pt1 = ls;
            pt2 = le;
        }
 
        *x = (pt1.x + pt2.x) / 2;
        *y = (pt1.y + pt2.y) / 2;
        break;
 
    case 1:                     /* a vertex of line m is on line l */
        if ((ls.x - le.x) * (ms.y - ls.y) == (ls.y - le.y) * (ms.x - ls.x)) {
            *x = ms.x;
            *y = ms.y;
        } else {
            *x = me.x;
            *y = me.y;
        }
    }                           /* end switch  */
    return 1;
}
 
static void
putSeg (int i, vertex* v)
{
    fprintf(stderr, "seg#%d : (%.3f, %.3f) (%.3f, %.3f)\n",
        i, v->pos.x, v->pos.y, after(v)->pos.x, after(v)->pos.y);
}
 
/* realIntersect:
 * Return 1 if a real intersection has been found
 */
static int
realIntersect (vertex *firstv, vertex *secondv, pointf p)
{
    pointf vft, vsd, avft, avsd;
 
    vft = firstv->pos;
    avft = after(firstv)->pos;
    vsd = secondv->pos;
    avsd = after(secondv)->pos;
 
    if ((vft.x != avft.x && vsd.x != avsd.x) ||
        (vft.x == avft.x && !EQ_PT(vft, p) && !EQ_PT(avft, p)) ||
        (vsd.x == avsd.x && !EQ_PT(vsd, p) && !EQ_PT(avsd, p))) 
    {
        if (Verbose > 1) {
                fprintf(stderr, "\nintersection at %.3f %.3f\n",
                        p.x, p.y);
                putSeg (1, firstv);
                putSeg (2, secondv);
        }
        return 1;
    }
    else return 0;
}
 
/* find_intersection:
 * detect whether segments l and m intersect      
 * Return 1 if found; 0 otherwise;
 */
static int find_intersection(vertex *l, vertex *m) {
    double x, y;
    pointf p;
        int i[3];
    sgnarea(l, m, i);
 
    if (i[2] > 0)
        return 0;
 
    if (i[2] < 0) {
        sgnarea(m, l, i);
        if (i[2] > 0)
            return 0;
        if (!intpoint(l, m, &x, &y, i[2] < 0 ? 3 : online(m, l, abs(i[0]))))
            return 0;
    }
 
    else if (!intpoint(l, m, &x, &y, i[0] == i[1] ?
                       2 * MAX(online(l, m, 0),
                               online(l, m, 1)) : online(l, m, abs(i[0]))))
        return 0;
 
    p.x = x;
    p.y = y;
    return realIntersect(l, m, p);
}
 
static int gt(const void *a, const void *b) {
    const vertex *const *i = a;
    const vertex *const *j = b;
    if ((*i)->pos.x > (*j)->pos.x) {
      return 1;
    }
    if ((*i)->pos.x < (*j)->pos.x) {
      return -1;
    }
    if ((*i)->pos.y > (*j)->pos.y) {
      return 1;
    }
    if ((*i)->pos.y < (*j)->pos.y) {
      return -1;
    }
    return 0;
}
 
/* find_ints:
 * Check for pairwise intersection of polygon sides
 * Return 1 if intersection found, 0 for not found, -1 for error.
 */
static int find_ints(vertex vertex_list[], size_t nvertices) {
    int j, k, found = 0;
    active_edge_list all;
    active_edge *new, *tempa;
    vertex *pt1, *pt2, *templ;
 
    all.first = all.final = 0;
    all.number = 0;
 
    vertex **pvertex = gv_calloc(nvertices, sizeof(vertex*));
 
    for (size_t i = 0; i < nvertices; i++)
        pvertex[i] = vertex_list + i;
 
/* sort vertices by x coordinate        */
    qsort(pvertex, nvertices, sizeof(vertex *), gt);
 
/* walk through the vertices in order of increasing x coordinate        */
    for (size_t i = 0; i < nvertices; i++) {
        pt1 = pvertex[i];
        templ = pt2 = prior(pvertex[i]);
        for (k = 0; k < 2; k++) {       /* each vertex has 2 edges */
            switch (gt(&pt1, &pt2)) {
 
            case -1:            /* forward edge, test and insert      */
 
                 /* test */
                for (tempa = all.first, j = 0; j < all.number;
                     j++, tempa = tempa->next) {
                    found = find_intersection(tempa->name, templ);
                    if (found)
                        goto finish;
                }
 
                new = gv_alloc(sizeof(active_edge));
                if (all.number == 0) {
                    all.first = new;
                    new->last = 0;
                } /* insert */
                else {
                    all.final->next = new;
                    new->last = all.final;
                }
 
                new->name = templ;
                new->next = 0;
                templ->active = new;
                all.final = new;
                all.number++;
 
                break;          /* end of case -1       */
 
            case 1:             /* backward edge, delete        */
 
                if ((tempa = templ->active) == 0) {
                    agerrorf("trying to delete a non-line\n");
                    return -1;
                }
                if (all.number == 1)
                    all.final = all.first = 0;  /* delete the line */
                else if (tempa == all.first) {
                    all.first = all.first->next;
                    all.first->last = 0;
                } else if (tempa == all.final) {
                    all.final = all.final->last;
                    all.final->next = 0;
                } else {
                    tempa->last->next = tempa->next;
                    tempa->next->last = tempa->last;
                }
                free(tempa);
                all.number--;
                templ->active = 0;
                break;          /* end of case 1        */
 
            default:
                break; // same point; do nothing
 
            }                   /* end switch   */
 
            pt2 = after(pvertex[i]);
            templ = pvertex[i]; /*second neighbor */
        }                       /* end k for loop       */
    }                           /* end i for loop       */
 
finish :
    for (tempa = all.first, j = 0; j < all.number;
                     j++, tempa = new) {
        new = tempa->next;
        free (tempa);
    }
    free (pvertex);
    return found;
}
 
#define INBOX(p,bb) ((p.x <= bb.UR.x) && (p.x >= bb.LL.x) && (p.y <= bb.UR.y) && (p.y >= bb.LL.y))
#define NESTED(a,b) (INBOX(a.LL,b) && INBOX(a.UR,b))
 
/* findInside:
 * Check if one polygon is inside another. We know that each
 * pair is either disjoint or one is inside the other.
 * Return 1 if an intersection is found, 0 otherwise.
 */
static int
findInside(Ppoly_t ** polys, int n_polys, polygon* polygon_list)
{
    int i, j;
    pointf pt;
    Ppoly_t* p1;
    Ppoly_t* p2;
 
    for (i = 0; i < n_polys; i++) {
        p1 = polys[i];
        pt = p1->ps[0];
        for (j = i+1; j < n_polys; j++) {
            p2 = polys[j];
            if (NESTED(polygon_list[i].bb,polygon_list[j].bb)) {
                if (in_poly(*p2, pt)) return 1;
            }
            else if (NESTED(polygon_list[j].bb,polygon_list[i].bb)) {
                if (in_poly(*p1, p2->ps[0])) return 1;
            }
        }
    }
    return 0;
}
 
/* Plegal_arrangement:
 * Check that none of the polygons overlap.
 * Return 1 if okay; 0 otherwise.
 */
int Plegal_arrangement(Ppoly_t ** polys, int n_polys)
{
    int i, vno, found;
    boxf bb;
    double x, y;
 
    polygon *polygon_list = gv_calloc(n_polys, sizeof(polygon));
 
    size_t nverts;
    for (nverts = 0, i = 0; i < n_polys; i++) {
        nverts += polys[i]->pn;
    }
 
    vertex *vertex_list = gv_calloc(nverts, sizeof(vertex));
 
    for (i = vno = 0; i < n_polys; i++) {
        polygon_list[i].start = &vertex_list[vno];
        bb.LL.x = bb.LL.y = DBL_MAX;
        bb.UR.x = bb.UR.y = -DBL_MAX;
        for (size_t j = 0; j < polys[i]->pn; j++) {
            x = polys[i]->ps[j].x;
            y = polys[i]->ps[j].y;
            bb.LL.x = fmin(bb.LL.x,x);
            bb.LL.y = fmin(bb.LL.y,y);
            bb.UR.x = fmax(bb.UR.x,x);
            bb.UR.y = fmax(bb.UR.y,y);
            vertex_list[vno].pos.x = x;
            vertex_list[vno].pos.y = y;
            vertex_list[vno].poly = &polygon_list[i];
            vertex_list[vno].active = 0;
            vno++;
        }
        polygon_list[i].finish = &vertex_list[vno - 1];
        polygon_list[i].bb = bb;
    }
 
    found = find_ints(vertex_list, nverts);
    if (found < 0) {
        free(polygon_list);
        free(vertex_list);
        return 0;
    }
 
    if (!found) {
        found = findInside(polys, n_polys, polygon_list);
    }
    free(polygon_list);
    free(vertex_list);
 
    return !found;
}