#pragma prototyped
#include "dot.h"
static point
midPt (point p, point q)
{
point v;
v.x = (p.x + q.x)/2;
v.y = (p.y + q.y)/2;
return v;
}
static char*
p2s (point p, char* buf)
{
sprintf (buf, "(%d,%d)", p.x, p.y);
return buf;
}
static point
boxIntersect (point pp, point cp, box* bp)
{
point ipp;
double ppx = pp.x;
double ppy = pp.y;
double cpx = cp.x;
double cpy = cp.y;
point ll = bp->LL;
point ur = bp->UR;
if (cp.x < ll.x) {
ipp.x = ll.x;
ipp.y = pp.y + (int)((ipp.x - ppx) * (ppy - cpy) / (ppx - cpx));
if (ipp.y >= ll.y && ipp.y <= ur.y)
return ipp;
}
if (cp.x > ur.x) {
ipp.x = ur.x;
ipp.y = pp.y + (int)((ipp.x - ppx) * (ppy - cpy) / (ppx - cpx));
if (ipp.y >= ll.y && ipp.y <= ur.y)
return ipp;
}
if (cp.y < ll.y) {
ipp.y = ll.y;
ipp.x = pp.x + (int)((ipp.y - ppy) * (ppx - cpx) / (ppy - cpy));
if (ipp.x >= ll.x && ipp.x <= ur.x)
return ipp;
}
if (cp.y > ur.y) {
ipp.y = ur.y;
ipp.x = pp.x + (int)((ipp.y - ppy) * (ppx - cpx) / (ppy - cpy));
if (ipp.x >= ll.x && ipp.x <= ur.x)
return ipp;
}
{
char ppbuf[100], cpbuf[100], llbuf[100], urbuf[100];
agerr(AGERR, "segment [%s,%s] does not intersect box ll=%s,ur=%s\n",
p2s(pp,ppbuf), p2s(cp, cpbuf), p2s(ll,llbuf), p2s(ur,urbuf));
assert (0);
}
return ipp;
}
static int
inBox (point p, box* bb)
{
return ((p.x >= bb->LL.x) && (p.x <= bb->UR.x) &&
(p.y >= bb->LL.y) && (p.y <= bb->UR.y));
}
static graph_t*
getCluster (graph_t* g, char* cluster_name)
{
graph_t* sg;
if (!cluster_name || (*cluster_name == '\0')) return NULL;
sg = agfindsubg (g, cluster_name);
if (sg == NULL)
agerr(AGWARN, "cluster named %s not found\n", cluster_name);
return sg;
}
#define SGN(a,b) (((a)<(b)) ? -1 : 1)
#define ZSGN(a,b) (((a)<(b)) ? -1 : (a)>(b) ? 1 : 0)
static int
countVertCross (pointf* pts, int xcoord)
{
int i;
int sign, old_sign;
int num_crossings = 0;
sign = old_sign = ZSGN(pts[0].x, xcoord);
if (sign == 0) num_crossings++;
for (i = 1; i <= 3; i++) {
sign = ZSGN(pts[i].x, xcoord);
if ((sign != old_sign) && (old_sign != 0)) num_crossings++;
old_sign = sign;
}
return num_crossings;
}
static int
countHorzCross (pointf* pts, int ycoord)
{
int i;
int sign, old_sign;
int num_crossings = 0;
sign = old_sign = ZSGN(pts[0].y, ycoord);
if (sign == 0) num_crossings++;
for (i = 1; i <= 3; i++) {
sign = ZSGN(pts[i].y, ycoord);
if ((sign != old_sign) && (old_sign != 0)) num_crossings++;
old_sign = sign;
}
return num_crossings;
}
static double
findVertical (pointf* pts, double tmin, double tmax,
int xcoord, int ymin, int ymax)
{
pointf Left[4];
pointf Right[4];
double t;
int no_cross = countVertCross (pts, xcoord);
if (no_cross == 0) return -1.0;
if ((no_cross == 1) && (ROUND(pts[3].x) == xcoord)) {
if ((ymin <= pts[3].y) && (pts[3].y <= ymax)) {
return tmax;
}
else return -1.0;
}
Bezier (pts, 3, 0.5, Left, Right);
t = findVertical (Left, tmin, (tmin + tmax)/2.0, xcoord, ymin, ymax);
if (t >= 0.0) return t;
return findVertical (Right, (tmin + tmax)/2.0, tmax, xcoord, ymin, ymax);
}
static double
findHorizontal (pointf* pts, double tmin, double tmax,
int ycoord, int xmin, int xmax)
{
pointf Left[4];
pointf Right[4];
double t;
int no_cross = countHorzCross (pts, ycoord);
if (no_cross == 0) return -1.0;
if ((no_cross == 1) && (ROUND(pts[3].y) == ycoord)) {
if ((xmin <= pts[3].x) && (pts[3].x <= xmax)) {
return tmax;
}
else return -1.0;
}
Bezier (pts, 3, 0.5, Left, Right);
t = findHorizontal (Left, tmin, (tmin + tmax)/2.0, ycoord, xmin, xmax);
if (t >= 0.0) return t;
return findHorizontal (Right, (tmin + tmax)/2.0, tmax, ycoord, xmin, xmax);
}
#define P2PF(p, pf) (pf.x = p.x, pf.y = p.y)
#define PF2P(pf, p) (p.x = ROUND (pf.x), p.y = ROUND (pf.y))
static int
splineIntersect (point* ipts, box* bb)
{
double tmin = 2.0;
double t;
pointf pts[4];
pointf origpts[4];
int i;
for (i = 0; i < 4; i++) {
P2PF (ipts[i], origpts[i]);
pts[i] = origpts[i];
}
t = findVertical (pts, 0.0, 1.0, bb->LL.x, bb->LL.y, bb->UR.y);
if ((t >= 0) && (t < tmin)) {
Bezier (origpts, 3, t, pts, NULL);
tmin = t;
}
t = findVertical (pts, 0.0, MIN(1.0,tmin), bb->UR.x, bb->LL.y, bb->UR.y);
if ((t >= 0) && (t < tmin)) {
Bezier (origpts, 3, t, pts, NULL);
tmin = t;
}
t = findHorizontal (pts, 0.0, MIN(1.0,tmin), bb->LL.y, bb->LL.x, bb->UR.x);
if ((t >= 0) && (t < tmin)) {
Bezier (origpts, 3, t, pts, NULL);
tmin = t;
}
t = findHorizontal (pts, 0.0, MIN(1.0,tmin), bb->UR.y, bb->LL.x, bb->UR.x);
if ((t >= 0) && (t < tmin)) {
Bezier (origpts, 3, t, pts, NULL);
tmin = t;
}
if (tmin < 2.0) {
for (i = 0; i < 4; i++) {
PF2P (pts[i], ipts[i]);
}
return 1;
}
else return 0;
}
static void
makeCompoundEdge (graph_t* g, edge_t* e)
{
graph_t* lh;
graph_t* lt;
bezier* bez;
bezier* nbez;
int starti=0, endi=0;
node_t* head;
node_t* tail;
box* bb;
int i, j;
int size;
point pts[4];
point p;
int fixed;
inside_t inside_context;
inside_context.e = e;
lh = getCluster (g, agget (e, "lhead"));
lt = getCluster (g, agget (e, "ltail"));
if (!lt && !lh) return;
if (ED_spl(e)->size > 1) {
agerr(AGWARN, "%s -> %s: spline size > 1 not supported\n",
e->tail->name, e->head->name);
return;
}
bez = ED_spl(e)->list;
size = bez->size;
head = e->head;
tail = e->tail;
nbez = GNEW(bezier);
nbez->eflag = bez->eflag;
nbez->sflag = bez->sflag;
fixed = 0;
if (lh) {
bb = &(GD_bb(lh));
if (!inBox (ND_coord_i(head), bb)) {
agerr(AGWARN, "%s -> %s: head not inside head cluster %s\n",
e->tail->name, e->head->name, agget (e, "lhead"));
}
else {
if (inBox (bez->list[0], bb)) {
if (inBox (ND_coord_i(tail), bb)) {
agerr(AGWARN, "%s -> %s: tail is inside head cluster %s\n",
e->tail->name, e->head->name, agget (e, "lhead"));
}
else {
assert (bez->sflag);
p = boxIntersect (bez->list[0], bez->sp, bb);
bez->list[3] = p;
bez->list[1] = midPt(p,bez->sp);
bez->list[0] = midPt(bez->list[1],bez->sp);
bez->list[2] = midPt(bez->list[1],p);
if (bez->eflag)
endi = arrowEndClip (&inside_context, bez->list, starti, 0, nbez, bez->eflag);
endi += 3;
fixed = 1;
}
}
else {
for (endi = 0; endi < size-1; endi += 3) {
if (splineIntersect (&(bez->list[endi]), bb)) break;
}
if (endi == size - 1) {
assert (bez->eflag);
nbez->ep = boxIntersect (bez->ep, bez->list[endi], bb);
}
else {
if (bez->eflag)
endi = arrowEndClip (&inside_context, bez->list, starti, endi, nbez, bez->eflag);
endi += 3;
}
fixed = 1;
}
}
}
if (fixed == 0) {
endi = size - 1;
if (bez->eflag) nbez->ep = bez->ep;
}
fixed = 0;
if (lt) {
bb = &(GD_bb(lt));
if (!inBox (ND_coord_i(tail), bb)) {
agerr(AGWARN, "%s -> %s: tail not inside tail cluster %s\n",
e->tail->name, head->name, agget (e, "ltail"));
}
else {
if (inBox (bez->list[endi], bb)) {
if (inBox (ND_coord_i(head), bb)) {
agerr(AGWARN, "%s -> %s: head is inside tail cluster %s\n",
e->tail->name, e->head->name, agget (e, "ltail"));
}
else {
assert (bez->eflag);
p = boxIntersect (bez->list[endi], nbez->ep, bb);
starti = endi - 3;
bez->list[starti] = p;
bez->list[starti+2] = midPt(p,nbez->ep);
bez->list[starti+3] = midPt(bez->list[starti+2],nbez->ep);
bez->list[starti+1] = midPt(bez->list[starti+2],p);
if (bez->sflag)
starti = arrowStartClip (&inside_context, bez->list, starti, endi-3, nbez, bez->sflag);
fixed = 1;
}
}
else {
for (starti = endi; starti > 0; starti -= 3) {
for (i=0; i < 4; i++)
pts[i] = bez->list[starti-i];
if (splineIntersect (pts, bb)) {
for (i=0; i < 4; i++)
bez->list[starti-i] = pts[i];
break;
}
}
if (starti == 0) {
assert (bez->sflag);
nbez->sp = boxIntersect (bez->sp, bez->list[starti], bb);
}
else {
starti -= 3;
if (bez->sflag)
starti = arrowStartClip (&inside_context, bez->list, starti, endi-3, nbez, bez->sflag);
}
fixed = 1;
}
}
}
if (fixed == 0) {
if (bez->sflag) nbez->sp = bez->sp;
}
nbez->size = endi - starti + 1;
nbez->list = N_GNEW(nbez->size,point);
for (i = 0, j = starti; i < nbez->size; i++,j++)
nbez->list[i] = bez->list[j];
free (bez->list);
free (bez);
ED_spl(e)->list = nbez;
}
void
dot_compoundEdges (graph_t* g)
{
edge_t* e;
node_t* n;
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
makeCompoundEdge (g, e);
}
}
}