poly.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 <neatogen/neato.h>
#include <assert.h>
#include <string.h>
#include <math.h>
#include <neatogen/poly.h>
#include <common/geom.h>
#include <stdbool.h>
#include <util/alloc.h>
#include <util/streq.h>
 
static const int BOX = 1;
static const int CIRCLE = 2;
 
static bool ISBOX(const Poly *p) { return p->kind & BOX; }
static bool ISCIRCLE(const Poly *p) { return p->kind & CIRCLE; }
 
void breakPoly(Poly * pp)
{
    free(pp->verts);
}
 
static void bbox(Point *verts, size_t cnt, Point *o, Point *c) {
    double x_min, y_min, x_max, y_max;
 
    x_min = x_max = verts->x;
    y_min = y_max = verts->y;
    for (size_t i = 1; i < cnt; i++) {
        verts++;
        x_min = fmin(x_min, verts->x);
        y_min = fmin(y_min, verts->y);
        x_max = fmax(x_max, verts->x);
        y_max = fmax(y_max, verts->y);
    }
    o->x = x_min;
    o->y = y_min;
    c->x = x_max;
    c->y = y_max;
}
 
static void inflatePts(Point *verts, size_t cnt, double xmargin,
                       double ymargin) {
    Point *cur;
 
    cur = &verts[0];
    for (size_t i = 0; i < cnt; i++) {
        cur->x *= xmargin;
        cur->y *= ymargin;
        cur++;
    }
}
 
static int isBox(Point *verts, size_t cnt) {
    if (cnt != 4)
        return 0;
 
    if (verts[0].y == verts[1].y)
        return ((verts[2].y == verts[3].y) &&
                (verts[0].x == verts[3].x) && (verts[1].x == verts[2].x));
    else
        return ((verts[0].x == verts[1].x) &&
                (verts[2].x == verts[3].x) &&
                (verts[0].y == verts[3].y) && (verts[1].y == verts[2].y));
}
 
static Point makeScaledTransPoint(double x, double y, double dx, double dy) {
    Point rv;
    rv.x = PS2INCH(x) + dx;
    rv.y = PS2INCH(y) + dy;
    return rv;
}
 
static Point makeScaledPoint(double x, double y)
{
    Point rv;
    rv.x = PS2INCH(x);
    rv.y = PS2INCH(y);
    return rv;
}
 
static Point *genRound(Agnode_t *n, size_t *sidep, double xm, double ym) {
    size_t sides = 0;
    char *p = agget(n, "samplepoints");
 
    int isides = 0;
    if (p)
        isides = atoi(p);
    sides = isides < 3 ? DFLT_SAMPLE : (size_t)isides;
    Point *verts = gv_calloc(sides, sizeof(Point));
    for (size_t i = 0; i < sides; i++) {
        verts[i].x =
            (ND_width(n) / 2.0 + xm) * cos((double)i / (double)sides * M_PI * 2.0);
        verts[i].y =
            (ND_height(n) / 2.0 + ym) * sin((double)i / (double)sides * M_PI * 2.0);
    }
    *sidep = sides;
    return verts;
}
 
#define PUTPT(P,X,Y) ((P).x=(X),(P).y=(Y))
 
int makeAddPoly(Poly *pp, Agnode_t *n, double xmargin, double ymargin) {
    size_t sides;
    Point *verts;
    polygon_t *poly;
 
    if (ND_clust(n)) {
        Point b;
        sides = 4;
        b.x = ND_width(n) / 2.0 + xmargin;
        b.y = ND_height(n) / 2.0 + ymargin;
        pp->kind = BOX;
        verts = gv_calloc(sides, sizeof(Point));
        PUTPT(verts[0], b.x, b.y);
        PUTPT(verts[1], -b.x, b.y);
        PUTPT(verts[2], -b.x, -b.y);
        PUTPT(verts[3], b.x, -b.y);
    } else
        switch (shapeOf(n)) {
        case SH_POLY:
            poly = ND_shape_info(n);
            sides = poly->sides;
 
            if (streq(ND_shape(n)->name, "box"))
                pp->kind = BOX;
            else if (streq(ND_shape(n)->name, "polygon")
                     && isBox(poly->vertices, sides))
                pp->kind = BOX;
            else if ((poly->sides < 3) && poly->regular)
                pp->kind = CIRCLE;
            else
                pp->kind = 0;
 
            if (sides >= 3) {   /* real polygon */
                verts = gv_calloc(sides, sizeof(Point));
                if (pp->kind == BOX) {
                        /* To do an additive margin, we rely on knowing that
                         * the vertices are CCW starting from the UR
                         */
                    verts[0].x = PS2INCH(poly->vertices[0].x) + xmargin;
                    verts[0].y = PS2INCH(poly->vertices[0].y) + ymargin;
                    verts[1].x = PS2INCH(poly->vertices[1].x) - xmargin;
                    verts[1].y = PS2INCH(poly->vertices[1].y) + ymargin;
                    verts[2].x = PS2INCH(poly->vertices[2].x) - xmargin;
                    verts[2].y = PS2INCH(poly->vertices[2].y) - ymargin;
                    verts[3].x = PS2INCH(poly->vertices[3].x) + xmargin;
                    verts[3].y = PS2INCH(poly->vertices[3].y) - ymargin;
 
                }
                else {
                    for (size_t i = 0; i < sides; i++) {
                        const double h = hypot(poly->vertices[i].x, poly->vertices[i].y);
                        verts[i].x = poly->vertices[i].x * (1.0 + xmargin/h);
                        verts[i].y = poly->vertices[i].y * (1.0 + ymargin/h);
                        verts[i].x = PS2INCH(verts[i].x);
                        verts[i].y = PS2INCH(verts[i].y);
                    }
                }
            } else
                verts = genRound(n, &sides, xmargin, ymargin);
            break;
        case SH_RECORD: {
            sides = 4;
            verts = gv_calloc(sides, sizeof(Point));
            boxf b = ((field_t*)ND_shape_info(n))->b;
            verts[0] = makeScaledTransPoint(b.LL.x, b.LL.y, -xmargin, -ymargin);
            verts[1] = makeScaledTransPoint(b.UR.x, b.LL.y, xmargin, -ymargin);
            verts[2] = makeScaledTransPoint(b.UR.x, b.UR.y, xmargin, ymargin);
            verts[3] = makeScaledTransPoint(b.LL.x, b.UR.y, -xmargin, ymargin);
            pp->kind = BOX;
            break;
        }
        case SH_POINT:
            pp->kind = CIRCLE;
            verts = genRound(n, &sides, xmargin, ymargin);
            break;
        default:
            agerrorf("makeAddPoly: unknown shape type %s\n",
                  ND_shape(n)->name);
            return 1;
        }
 
    pp->verts = verts;
    pp->nverts = (int)sides;
    bbox(verts, sides, &pp->origin, &pp->corner);
 
    return 0;
}
 
int makePoly(Poly *pp, Agnode_t *n, double xmargin, double ymargin) {
    size_t sides;
    Point *verts;
    polygon_t *poly;
 
    if (ND_clust(n)) {
        Point b;
        sides = 4;
        b.x = ND_width(n) / 2.0;
        b.y = ND_height(n) / 2.0;
        pp->kind = BOX;
        verts = gv_calloc(sides, sizeof(Point));
        PUTPT(verts[0], b.x, b.y);
        PUTPT(verts[1], -b.x, b.y);
        PUTPT(verts[2], -b.x, -b.y);
        PUTPT(verts[3], b.x, -b.y);
    } else
        switch (shapeOf(n)) {
        case SH_POLY:
            poly = ND_shape_info(n);
            sides = poly->sides;
            if (sides >= 3) {   /* real polygon */
                verts = gv_calloc(sides, sizeof(Point));
                for (size_t i = 0; i < sides; i++) {
                    verts[i].x = PS2INCH(poly->vertices[i].x);
                    verts[i].y = PS2INCH(poly->vertices[i].y);
                }
            } else
                verts = genRound(n, &sides, 0, 0);
 
            if (streq(ND_shape(n)->name, "box"))
                pp->kind = BOX;
            else if (streq(ND_shape(n)->name, "polygon")
                     && isBox(verts, sides))
                pp->kind = BOX;
            else if ((poly->sides < 3) && poly->regular)
                pp->kind = CIRCLE;
            else
                pp->kind = 0;
 
            break;
        case SH_RECORD: {
            sides = 4;
            verts = gv_calloc(sides, sizeof(Point));
            boxf b = ((field_t *) ND_shape_info(n))->b;
            verts[0] = makeScaledPoint(b.LL.x, b.LL.y);
            verts[1] = makeScaledPoint(b.UR.x, b.LL.y);
            verts[2] = makeScaledPoint(b.UR.x, b.UR.y);
            verts[3] = makeScaledPoint(b.LL.x, b.UR.y);
            pp->kind = BOX;
            break;
        }
        case SH_POINT:
            pp->kind = CIRCLE;
            verts = genRound(n, &sides, 0, 0);
            break;
        default:
            agerrorf("makePoly: unknown shape type %s\n",
                  ND_shape(n)->name);
            return 1;
        }
 
    if ((xmargin != 1.0) || (ymargin != 1.0))
        inflatePts(verts, sides, xmargin, ymargin);
 
    pp->verts = verts;
    pp->nverts = (int)sides;
    bbox(verts, sides, &pp->origin, &pp->corner);
 
    return 0;
}
 
static int
pintersect(Point originp, Point cornerp, Point originq, Point cornerq)
{
    return originp.x <= cornerq.x && originq.x <= cornerp.x &&
           originp.y <= cornerq.y && originq.y <= cornerp.y;
}
 
#define advance(A,B,N) (B++, A = (A+1)%N)
 
static bool edgesIntersect(Point *P, Point *Q, int n, int m) {
    int a = 0;
    int b = 0;
    int aa = 0;
    int ba = 0;
    int a1, b1;
    Point A, B;
    double cross;
    int bHA, aHB;
    Point p;
    /* int      i = 0; */
    /* int      Reset = 0; */
 
    do {
        a1 = (a + n - 1) % n;
        b1 = (b + m - 1) % m;
 
        subpt(&A, P[a], P[a1]);
        subpt(&B, Q[b], Q[b1]);
 
        cross = area_2((Point){0}, A, B);
        bHA = leftOf(P[a1], P[a], Q[b]);
        aHB = leftOf(Q[b1], Q[b], P[a]);
 
        // do A & B intersect?
        if (intersection(P[a1], P[a], Q[b1], Q[b], &p))
            return true;
 
        /* Advance rules. */
        if (cross == 0 && !bHA && !aHB) {
            advance(a, aa, n);
        } else if (cross >= 0)
            if (bHA)
                advance(a, aa, n);
            else {
                advance(b, ba, m);
        } else {                /* if ( cross < 0 ) */
 
            if (aHB)
                advance(b, ba, m);
            else
                advance(a, aa, n);
        }
 
    } while ((aa < n || ba < m) && aa < 2 * n && ba < 2 * m);
 
    return false;
 
}
 
/* Return true if q is inside polygon vertex[]
 * Assume points are in CCW order
 */
static bool inPoly(Point vertex[], int n, Point q) {
    int i, i1;                  /* point index; i1 = i-1 mod n */
    double x;                   /* x intersection of e with ray */
    double crossings = 0;       /* number of edge/ray crossings */
 
    Point *const tp3 = gv_calloc((size_t)n, sizeof(Point));
 
    /* Shift so that q is the origin. */
    for (i = 0; i < n; i++) {
        tp3[i].x = vertex[i].x - q.x;
        tp3[i].y = vertex[i].y - q.y;
    }
 
    /* For each edge e=(i-1,i), see if crosses ray. */
    for (i = 0; i < n; i++) {
        i1 = (i + n - 1) % n;
 
        /* if edge is horizontal, test to see if the point is on it */
        if (tp3[i].y == 0 && tp3[i1].y == 0) {
            if (tp3[i].x * tp3[i1].x < 0) {
                free(tp3);
                return true;
            } else {
                continue;
            }
        }
 
        /* if e straddles the x-axis... */
        if ((tp3[i].y >= 0 && tp3[i1].y <= 0) ||
            (tp3[i1].y >= 0 && tp3[i].y <= 0)) {
            /* e straddles ray, so compute intersection with ray. */
            x = (tp3[i].x * tp3[i1].y - tp3[i1].x * tp3[i].y)
                / (double) (tp3[i1].y - tp3[i].y);
 
            /* if intersect at origin, we've found intersection */
            if (x == 0) {
                free(tp3);
                return true;
            }
 
            /* crosses ray if strictly positive intersection. */
            if (x > 0) {
                if (tp3[i].y == 0 || tp3[i1].y == 0) {
                    crossings += .5;    /* goes through vertex */
                } else {
                    crossings += 1.0;
                }
            }
        }
    }
    free(tp3);
 
    /* q inside if an odd number of crossings. */
    return (int)crossings % 2 == 1;
}
 
static bool inBox(Point p, Point origin_point, Point corner) {
    return p.x <= corner.x && p.x >= origin_point.x && p.y <= corner.y &&
           p.y >= origin_point.y;
}
 
static Point *transCopy(Point *inp, int cnt, Point off) {
    Point *const out = gv_calloc((size_t)cnt, sizeof(out[0]));
    int i;
 
    for (i = 0; i < cnt; i++) {
        out[i].x = inp->x + off.x;
        out[i].y = inp->y + off.y;
        inp++;
    }
    return out;
}
 
bool polyOverlap(Point p, Poly *pp, Point q, Poly *qp) {
    Point op, cp;
    Point oq, cq;
 
    /* translate bounding boxes */
    addpt(&op, p, pp->origin);
    addpt(&cp, p, pp->corner);
    addpt(&oq, q, qp->origin);
    addpt(&cq, q, qp->corner);
 
    /* If bounding boxes don't overlap, done */
    if (!pintersect(op, cp, oq, cq))
        return false;
 
    if (ISBOX(pp) && ISBOX(qp))
        return true;
    if (ISCIRCLE(pp) && ISCIRCLE(qp)) {
        double d = pp->corner.x - pp->origin.x + qp->corner.x - qp->origin.x;
        double dx = p.x - q.x;
        double dy = p.y - q.y;
        return dx * dx + dy * dy <= d * d / 4.0;
    }
 
    Point *const tp1 = transCopy(pp->verts, pp->nverts, p);
    Point *const tp2 = transCopy(qp->verts, qp->nverts, q);
 
    bool result = edgesIntersect(tp1, tp2, pp->nverts, qp->nverts) ||
            (inBox(*tp1, oq, cq) && inPoly(tp2, qp->nverts, *tp1)) ||
            (inBox(*tp2, op, cp) && inPoly(tp1, pp->nverts, *tp2));
    free(tp1);
    free(tp2);
    return result;
}