#pragma prototyped
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include "blockpath.h"
#define LEN(x,y) (sqrt((x)*(x) + (y)*(y)))
static double
getRotation(block_t* sn, Agraph_t* g, double x, double y, double theta)
{
double mindist;
Agraph_t* subg;
Agnode_t *n, *closest_node, *neighbor;
nodelist_t* list;
double len, newX, newY;
int count;
subg = sn->sub_graph;
#ifdef OLD
parent = sn->parent;
#endif
list = sn->circle_list;
if(sn->parent_pos >= 0) {
theta += PI - sn->parent_pos;
if(theta < 0)
theta += 2 * PI;
return theta;
}
count = sizeNodelist(list);
if (count == 2) {
return (theta - PI/2.0);
}
neighbor = CHILD(sn);
#ifdef OLD
for(e = agfstedge(g, parent); e; e = agnxtedge(g, e, parent)) {
n = e->head;
if(n == parent) n = e->tail;
if ((BLOCK(n) == sn) && (PARENT(n) == parent)) {
neighbor = n;
break;
}
}
#endif
newX = ND_pos(neighbor)[0] + x;
newY = ND_pos(neighbor)[1] + y;
mindist = LEN(newX, newY);
closest_node = neighbor;
for(n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
if (n == neighbor) continue;
newX = ND_pos(n)[0] + x;
newY = ND_pos(n)[1] + y;
len = LEN(newX, newY);
if (len < mindist) {
mindist = len;
closest_node = n;
}
}
if (neighbor != closest_node) {
double rho = sn->rad0;
double r = sn->radius - rho;
double n_x = ND_pos(neighbor)[0];
if (COALESCED(sn) && (-r < n_x)) {
double R = LEN(x,y);
double n_y = ND_pos(neighbor)[1];
double phi = atan2 (n_y, n_x + r);
double l = r - rho/(cos(phi));
theta += PI/2.0 - phi - asin((l/R)*(cos(phi)));
}
else {
double phi = atan2(ND_pos(neighbor)[1],ND_pos(neighbor)[0]);
theta += PI - phi - PSI(neighbor);
if (theta > 2*PI) theta -= 2*PI;
}
}
else theta = 0;
return theta;
}
static void
applyDelta(block_t* sn, double x, double y, double rotate)
{
block_t* child;
Agraph_t* subg;
Agnode_t* n;
subg = sn->sub_graph;
for(n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
double X, Y;
if (rotate != 0) {
double tmpX, tmpY;
double cosR, sinR;
tmpX = ND_pos(n)[0];
tmpY = ND_pos(n)[1];
cosR = cos(rotate);
sinR = sin(rotate);
X = tmpX*cosR - tmpY*sinR;
Y = tmpX*sinR + tmpY*cosR;
}
else {
X = ND_pos(n)[0];
Y = ND_pos(n)[1];
}
ND_pos(n)[0] = X + x;
ND_pos(n)[1] = Y + y;
}
for (child = sn->children.first; child; child = child->next)
applyDelta(child, x, y, rotate);
}
typedef struct {
double radius;
double subtreeR;
double nodeAngle;
double firstAngle;
double lastAngle;
block_t* cp;
node_t* neighbor;
} posstate;
static double
doParent (Agraph_t* g, double theta, Agnode_t* n,
int length, double min_dist, posstate* stp)
{
block_t* child;
double mindistance;
double childAngle;
double deltaX, deltaY;
double snRadius = stp->subtreeR;
double firstAngle = stp->firstAngle;
double lastAngle = stp->lastAngle;
double rotateAngle;
double incidentAngle;
int childCount = 0;
double maxRadius = 0;
double childRadius;
double diameter = 0;
double mindistAngle;
int cnt, midChild;
double midAngle;
for (child = stp->cp; child; child = child->next) {
if(BLK_PARENT(child) == n) {
childCount++;
if(maxRadius < child->radius) {
maxRadius = child->radius;
}
diameter += 2 * child->radius + min_dist;
}
}
if(length == 1)
childAngle = 0;
else
childAngle = theta - stp->nodeAngle/2;
childRadius = length * diameter/(2 * PI);
mindistance = stp->radius + min_dist + maxRadius;
if(childRadius < mindistance)
childRadius = mindistance;
if((childRadius + maxRadius) > snRadius)
snRadius = childRadius + maxRadius;
mindistAngle = min_dist/childRadius;
cnt = 0;
midChild = (childCount + 1)/2;
for (child = stp->cp; child; child = child->next) {
if(BLK_PARENT(child) != n) continue;
if(sizeNodelist(child->circle_list) <= 0) continue;
incidentAngle = child->radius/childRadius;
if(length == 1) {
if(childAngle != 0)
childAngle += incidentAngle;
if(firstAngle < 0)
firstAngle = childAngle;
lastAngle = childAngle;
}
else {
if(childCount == 1) {
childAngle = theta;
}
else {
childAngle += incidentAngle + mindistAngle/2;
}
}
deltaX = childRadius * cos(childAngle);
deltaY = childRadius * sin(childAngle);
rotateAngle = getRotation(child, g, deltaX, deltaY, childAngle);
applyDelta(child, deltaX, deltaY, rotateAngle);
if(length == 1) {
childAngle += incidentAngle + mindistAngle;
} else {
childAngle += incidentAngle + mindistAngle/2;
}
cnt++;
if (cnt == midChild) midAngle = childAngle;
}
if ((length > 1) && (n == stp->neighbor)) {
PSI(n) = midAngle;
}
stp->subtreeR = snRadius;
stp->firstAngle = firstAngle;
stp->lastAngle= lastAngle;
return maxRadius;
}
static double
position (Agraph_t*g, int childCount, int length, nodelist_t* path, block_t* sn, double min_dist)
{
nodelistitem_t* item;
Agnode_t* n;
posstate state;
int counter = 0;
double maxRadius = 0.0;
double angle;
double theta = 0.0;
state.cp = sn->children.first;
state.subtreeR = sn->radius;
state.radius = sn->radius;
state.neighbor = CHILD(sn);
state.nodeAngle = 2 * PI / length;
state.firstAngle = -1;
state.lastAngle = -1;
for (item = path->first; item; item = item->next) {
n = item->curr;
if(length != 1) {
theta = counter * state.nodeAngle;
counter++;
}
if(ISPARENT(n))
maxRadius = doParent(g, theta, n, length, min_dist, &state);
}
if(childCount == 1) {
applyDelta(sn, -(maxRadius + min_dist/2), 0, 0);
sn->radius += min_dist/2 + maxRadius;
SET_COALESCED(sn);
}
else
sn->radius = state.subtreeR;
angle = (state.firstAngle+state.lastAngle)/2.0 - PI;
return angle;
}
static void
doBlock(Agraph_t* g, block_t* sn, double min_dist)
{
block_t* child;
nodelist_t* longest_path;
int childCount, length;
double centerAngle = PI;
childCount = 0;
for (child = sn->children.first; child; child = child->next) {
doBlock(g, child, min_dist);
childCount++;
}
longest_path = layout_block(g, sn, min_dist);
sn->circle_list = longest_path;
length = sizeNodelist(longest_path);
if(childCount > 0)
centerAngle = position (g, childCount, length, longest_path, sn, min_dist);
if ((length == 1) && (BLK_PARENT(sn))) {
sn->parent_pos = centerAngle;
if(sn->parent_pos < 0)
sn->parent_pos += 2 * PI;
}
}
void
circPos(Agraph_t* g, block_t* sn, circ_state* state)
{
doBlock(g, sn, state->min_dist);
}