/*
This software may only be used by you under license from AT&T Corp.
("AT&T"). A copy of AT&T's Source Code Agreement is available at
AT&T's Internet website having the URL:
<http://www.research.att.com/sw/tools/graphviz/license/source.html>
If you received this software without first entering into a license
with AT&T, you have an infringing copy of this software and cannot use
it without violating AT&T's intellectual property rights.
*/
#pragma prototyped
/* poly.c
*/
#include <assert.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include "neato.h"
#include "poly.h"
#include "mem.h"
#define BOX 1
#define ISBOX(p) ((p)->kind & BOX)
#define CIRCLE 2
#define ISCIRCLE(p) ((p)->kind & CIRCLE)
static int maxcnt = 0;
static Point* tp1 = NULL;
static Point* tp2 = NULL;
static Point* tp3 = NULL;
void polyFree ()
{
maxcnt = 0;
free (tp1);
free (tp2);
free (tp3);
tp1 = NULL;
tp2 = NULL;
tp3 = NULL;
}
void breakPoly (Poly* pp)
{
free (pp->verts);
}
static void
bbox (Point* verts, int cnt, Point* o, Point* c)
{
double xmin, ymin, xmax, ymax;
int i;
xmin = xmax = verts->x;
ymin = ymax = verts->y;
for (i = 1; i < cnt; i++) {
verts++;
if (verts->x < xmin) xmin = verts->x;
if (verts->y < ymin) ymin = verts->y;
if (verts->x > xmax) xmax = verts->x;
if (verts->y > ymax) ymax = verts->y;
}
o->x = xmin;
o->y = ymin;
c->x = xmax;
c->y = ymax;
}
#ifdef OLD
static void
inflate (Point* prev, Point* cur, Point* next, double margin)
{
double theta = atan2 (prev->y - cur->y, prev->x - cur->x);
double phi = atan2 (next->y - cur->y, next->x - cur->x);
double beta = (theta + phi)/2.0;
double gamma = (PI + phi - theta)/2.0;
double denom;
denom = cos (gamma);
cur->x -= margin*(cos (beta))/denom;
cur->y -= margin*(sin (beta))/denom;
}
static void
inflatePts (Point* verts, int cnt, double margin)
{
int i;
Point first;
Point savepoint;
Point prevpoint;
Point* prev = &prevpoint;
Point* cur;
Point* next;
first = verts[0];
prevpoint = verts[cnt-1];
cur = &verts[0];
next = &verts[1];
for (i = 0; i < cnt-1; i++) {
savepoint = *cur;
inflate (prev,cur,next,margin);
cur++;
next++;
prevpoint = savepoint;
}
next = &first;
inflate (prev,cur,next,margin);
}
#else
static void
inflatePts (Point* verts, int cnt, double margin)
{
int i;
Point* cur;
cur = &verts[0];
for (i = 0; i < cnt; i++) {
cur->x *= margin;
cur->y *= margin;
cur++;
}
}
#endif
static int
isBox (Point* verts, int 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));
}
#define DFLT_SAMPLE 20
static Point
makeScaledPoint(int x, int y)
{
Point rv;
rv.x = PS2INCH(x);
rv.y = PS2INCH(y);
return rv;
}
static Point*
genRound (Agnode_t* n, int* sidep)
{
int sides = 0;
Point* verts;
char* p = agget(n,"samplepoints");
int i;
if (p) sides = atoi(p);
if (sides < 3) sides = DFLT_SAMPLE;
verts = N_GNEW (sides, Point);
for (i = 0; i < sides; i++) {
verts[i].x = ND_width(n)/2.0 * cos(i/(double)sides * PI * 2.0);
verts[i].y = ND_height(n)/2.0 * sin(i/(double)sides * PI * 2.0);
}
*sidep = sides;
return verts;
}
void
makePoly (Poly* pp, Agnode_t* n, double margin)
{
extern void poly_init(node_t *);
extern void record_init(node_t *);
extern void point_init(node_t *);
int i;
int sides;
Point* verts;
polygon_t *poly;
if (ND_shape(n)->initfn == poly_init) {
poly = (polygon_t*) ND_shape_info(n);
sides = poly->sides;
if (sides >= 3) { /* real polygon */
verts = N_GNEW (sides, Point);
for (i = 0; i < sides; i++) {
verts[i].x = poly->vertices[i].x;
verts[i].y = poly->vertices[i].y;
}
}
else verts = genRound (n, &sides);
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;
}
else if (ND_shape(n)->initfn == record_init) {
box b;
sides = 4;
verts = N_GNEW (sides, Point);
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;
}
else if (ND_shape(n)->initfn == point_init) {
pp->kind = CIRCLE;
verts = genRound (n, &sides);
}
else {
agerr(AGERR, "makePoly: unknown shape type %s\n", ND_shape(n)->name);
exit(1);
}
#ifdef OLD
if (margin != 0.0)
inflatePts (verts,sides,margin);
#else
if (margin != 1.0)
inflatePts (verts,sides,margin);
#endif
pp->verts = verts;
pp->nverts = sides;
bbox (verts, sides, &pp->origin, &pp->corner);
if (sides > maxcnt)
maxcnt = sides;
}
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 Pin 1
#define Qin 2
#define Unknown 0
#define advance(A,B,N) (B++, A = (A+1)%N)
static int
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 inflag = Unknown;
/* 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(origin, A, B );
bHA = leftOf( P[a1], P[a], Q[b] );
aHB = leftOf( Q[b1], Q[b], P[a] );
/* If A & B intersect, update inflag. */
if (intersection( P[a1], P[a], Q[b1], Q[b], &p ) )
return 1;
/* Advance rules. */
if ( (cross == 0) && !bHA && !aHB ) {
if ( inflag == Pin )
advance( b, ba, m);
else
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 0;
}
static int
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 */
if (tp3 == NULL)
tp3 = N_GNEW (maxcnt, 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) {
return 1 ;
}
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)
return 1;;
/* crosses ray if strictly positive intersection. */
if (x > 0) {
if ( (tp3[i].y == 0) || (tp3[i1].y == 0) ) {
crossings += .5 ; /* goes thru vertex*/
}
else {
crossings += 1.0;
}
}
}
}
/* q inside if an odd number of crossings. */
if( (((int) crossings) % 2) == 1 )
return 1;
else return 0;
}
static int
inBox (Point p, Point origin, Point corner)
{
return ((p.x <= corner.x) &&
(p.x >= origin.x) &&
(p.y <= corner.y) &&
(p.y >= origin.y));
}
static void
transCopy (Point* inp, int cnt, Point off, Point* outp)
{
int i;
for (i = 0; i < cnt; i++) {
outp->x = inp->x + off.x;
outp->y = inp->y + off.y;
inp++;
outp++;
}
}
int
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 0;
if (ISBOX(pp) && ISBOX(qp)) return 1;
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;
if ((dx*dx + dy*dy) > (d*d)/4.0) return 0;
else return 1;
}
if (tp1 == NULL) {
tp1 = N_GNEW (maxcnt, Point);
tp2 = N_GNEW (maxcnt, Point);
}
transCopy (pp->verts, pp->nverts, p, tp1);
transCopy (qp->verts, qp->nverts, q, tp2);
return (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)) );
}
|
