核心思想
通过定义图的能量，并不断迭代获取能量最小的布局。
源码
核心步骤：
int Layouter::do_layout() {
prepare_layout_stages();
_min_energy = calc_energy();
int de0_count = 10; // de=0 count
double de = 1; // energy delta
double prev_energy = 0;
while (de0_count > 0) {
shuffle();
de = prev_energy - _min_energy;
prev_energy = _min_energy;
if (de == 0)
--de0_count;
else
de0_count = 10;
}
// update actual figures with new coords
for (std::size_t i = 0; i < _figures.size(); ++i) {
Node &n = _figures[i];
model_FigureRef &f = n.fig;
f->left(n.x1);
f->top(n.y1);
}
}
- 图数据初始化。
- 计算图能量。
- 移动节点位置，迭代直到找到能量最小的布局。
- 根据计算结果，更新节点位置。
核心步骤
1. 初始化
void Layouter::prepare_layout_stages() {
double total_w = 0;
double total_h = 0;
// 根据节点的连接数进行排序
std::sort(_figures.begin(), _figures.end(), compare_node_links);
// reset layout
for (size_t i = 0; i < _figures.size(); ++i) {
Node &n = _figures[i];
// place all tables in some initial position
// 节点初始位置
n.move((long)_w / 4, (long)_h / 4);
// Calculate total dimensions and find max cell size.
// 计算图最小的面积。cell为节点最大的宽度和高度
total_w += n.w;
total_h += n.h;
if (_cell_w < n.w)
_cell_w = (int)n.w;
if (_cell_h < n.h)
_cell_h = (int)n.h;
}
// 单元格放大1.1倍
_cell_w = (int)(1.1 * _cell_w);
}- 将节点按照其边的连接数从小到大排序。
- 根据节点的面积叠加计算图的面积。
- 计算单元格的宽度和高度。（节点的最大高度和宽度）
- 节点位置初始化，初始化位置在画布的左上角四分之一处。
2. 计算图能量
double Layouter::calc_energy() {
double e = 0.0;
std::size_t size = _figures.size();
for (std::size_t i = 0; i < size; ++i) {
const Node &node = _figures[i];
// 位置在可视区之外的节点，能量加很大的一个值
if ((node.x1 < 0) || (node.y1 < 0) || (node.x2 + 20 > _w) || (node.y2 + 20 > _h))
e += 1000000000000.0;
// 计算任意两个节点之间的能量
for (std::size_t j = i + 1; j < size; ++j) {
if (j >= size)
break;
e += calc_node_pair(i, j);
}
}
return e;
}计算图整体的能量。
- 遍历位置在可视区之外的节点，能量增加 1,000,000,000,000。
- 遍历计算节点两两之间的能量，叠加到图能量中。
3. 计算节点之间能量
double Layouter::calc_node_pair(const std::size_t i1, const std::size_t i2) {
const Node *n1 = &(_figures[i1]);
const Node *n2 = &(_figures[i2]);
const bool is_linked = n1->is_linked_to(i2) || n2->is_linked_to(i1);
// 计算节点的面积，节点面积从小到大
long S1 = n1->w * n1->h;
long S2 = n2->w * n2->h;
if (S1 > S2) {
std::swap(n1, n2);
std::swap(S1, S2);
}
const long x11 = n1->x1;
const long y11 = n1->y1;
const long x12 = n1->x2;
const long y12 = n1->y2;
const long x21 = n2->x1;
const long y21 = n2->y1;
const long x22 = n2->x2;
const long y22 = n2->y2;
const long cx1 = x11 + (x12 - x11) / 2;
const long cy1 = y11 + (y12 - y11) / 2;
const long cx2 = x21 + (x22 - x21) / 2;
const long cy2 = y21 + (y22 - y21) / 2;
// Detect if nodes overlap 检查节点之间是否存在覆盖问题
const bool is_overlap = ((x12 >= x21) && (x22 >= x11) && (y12 >= y21) && (y22 >= y11));
static const double overlap_quot = 1000.0;
double e = 0.0;
double distance = 0;
if (is_overlap) {
distance = line_len2(cx1, cy1, cx2, cy2);
// calc area of overlap 计算重复区域的坐标和面积
const long sx1 = x11 > x21 ? x11 : x21;
const long sy1 = y11 > y21 ? y11 : y21;
const long sx2 = x12 < x22 ? x12 : x22;
const long sy2 = y12 < y22 ? y12 : y22;
const long dsx = sx2 - sx1;
const long dsy = sy2 - sy1;
const long Sov = dsx * dsy;
if (distance == 0.0)
distance = 0.0000001;
e = _min_dist * 1 / distance * 100 + Sov;
e *= overlap_quot;
} else {
bool is_horiz = false;
distance = distance_to_node(i1, i2, &is_horiz);
if (distance <= _min_dist) {
if (distance != 0) {
if (is_linked)
e += _min_dist + overlap_quot * 1 / distance;
else
e += _min_dist + overlap_quot * _min_dist / distance;
} else {
e += overlap_quot;
}
} else {
e += distance;
if (is_linked)
e += distance * distance;
}
}
return e;
}- 按照节点面积排序，节点面积小的是n1，节点面积大的是n2.
- 判断两个节点是否存在覆盖问题。如存在，能量增加重叠区域面积的指定倍数。并乘以固定值重叠能量1000
e += \_min\_dist * 1 / (distance) * 100 + (x_{12}-x_{21})*(y_{22}-y_{11})
- 计算两个节点之间的距离 distance_to_node。
- 判断两个节点之间的距离是否小于指定的最小间距。如果小于，增加固定值能量除以distance。
e += \_min\_dist + overlap\_quot * 1 / distance
e += \_min\_dist + overlap\_quot * \_min\_dist / distance
- 如果两个节点之间有边链接，能量值叠加节点间距离的平方。
e += distance * distance
- 其他情况，能量值叠加节点间距。
4. 节点距离计算
long Layouter::distance_to_node(const std::size_t i1, const std::size_t i2, bool *is_horiz) {
const Node &n1 = _figures[i1];
const Node &n2 = _figures[i2];
const long x11 = n1.x1;
const long y11 = n1.y1;
const long x12 = n1.x2;
const long y12 = n1.y2;
const long x21 = n2.x1;
const long y21 = n2.y1;
const long x22 = n2.x2;
const long y22 = n2.y2;
const long cx1 = x11 + (x12 - x11) / 2;
const long cy1 = y11 + (y12 - y11) / 2;
const long cx2 = x21 + (x22 - x21) / 2;
const long cy2 = y21 + (y22 - y21) / 2;
const long dcx = cx2 - cx1;
// 两个节点间的方位角
const double qr = atan2((double)dcx, (double)(cy2 - cy1));
double dx = 0;
double dy = 0;
double l1 = 0;
double l2 = 0;
// 如果大于90度。l1 l2 为欧式距离
if (qr > M_PI_2) {
dy = y11 - y22;
dx = x21 - x12;
l1 = dy ? ::fabs(dy / cos(qr)) : ::fabs(dx);
l2 = dx ? ::fabs(dx / sin(qr)) : ::fabs(dy);
} else if (0.0 < qr && qr <= M_PI_2) {
dy = y21 - y12;
dx = x21 - x12;
if (dy > dx)
l1 = l2 = dy ? ::fabs(dy / cos(qr)) : ::fabs(dx);
else
l1 = l2 = dx ? ::fabs(dx / sin(qr)) : ::fabs(dy);
} else if (qr < -M_PI_2) {
dy = y11 - y22;
dx = -(x22 - x11);
if (dy > dx)
l1 = l2 = dy ? ::fabs(dy / cos(qr)) : ::fabs(dx);
else
l1 = l2 = dx ? ::fabs(dx / sin(qr)) : ::fabs(dy);
} else {
dy = y21 - y12;
if (abs(dcx) > (x12 - x11) / 2)
dx = x11 - x22;
else
dx = dcx;
if (dy > dx)
l1 = l2 = dy ? ::fabs(dy / cos(qr)) : ::fabs(dx);
else
l1 = l2 = (dx && qr != 0.0) ? ::fabs(dx / sin(qr)) : ::fabs(dy);
}
// printf("qr %f (cos(qr) = %f, sin(rq) = %f), l1 %li, l2 %li, dy %li, dx %li\n", qr, cos(qr), sin(qr), l1, l2, dy,
// dx);
const double aqr = ::fabs(qr);
// 判断是否水平，角度
if (is_horiz)
*is_horiz = PI_38 < aqr && aqr < PI_58;
return l1 < l2 ? (long)l1 : (long)l2;
}在解读代码之前，先来回顾一下三角函数的计算。
c++中 atan2 求方位角。 其计算公式如下，其中arctan(a/b) = A ，arctan是tan的反函数。
然后我们再回归到源码实现部分。
情况1：角度>90。
l1 = fabs(dy / cos(qr))
又因为 atan2(dx,dy) = arctan(dy/dx) = qr
=> tan(qr) = dy/dx
=> cos(qr) = dx/\sqrt{dx^2+dy^2}
=> l1 = fabs(dy / dx * \sqrt{dx^2+dy^2})
和直接用欧拉距离对比，增加dy/dx的斜率比，可以更好的考虑整个图的长宽比。
5. 移动节点
移动节点找到可以使图能量最小的布局。
bool Layouter::shuffle() {
bool found_smaller_energy = false;
// 0-5的随机数
const int step = (rand() % 5) + 1;
for (std::size_t i = 0; i < _figures.size(); ++i) {
Node &n = _figures[i];
const int wstep = _cell_w * step;
const int hstep = _cell_w * step;
double node_energy = calc_node_energy(i, n);
const int wsteps[] = {wstep, -wstep, 0, 0};
const int hsteps[] = {0, 0, hstep, -hstep};
for (int ns = sizeof(wsteps) / sizeof(int) - 1; ns >= 0; --ns) {
// 节点朝上下左右四个方向移动，找到能量最小的那个位置
n.move_by(wsteps[ns], hsteps[ns]);
// 计算移动后节点的能量
const double energy = calc_node_energy(i, n);
if (energy < node_energy) {
node_energy = energy;
found_smaller_energy = true;
} else
n.move_by(-wsteps[ns], -hsteps[ns]); // 回归原位
}
}
// 重新计算图整体的能量
if (found_smaller_energy)
_min_energy = calc_energy();
return found_smaller_energy;
}- 生成随机移动步数step。
- 遍历节点。计算节点的能量值
- 分别将节点从上下左右四个方向，分别移动wstep和hstep位置。
- 然后重新计算节点的能量。
- 如果节点能量有变小，则标记found_smaller_energy 为true，表示找到了更合适的布局。否则，节点位置进行回退。
- 返回found_smaller_energy。
节点能量计算方法：和剩余的节点的能量之和。
double Layouter::calc_node_energy(const std::size_t node_i, const Node &node) {
double e = 0.0;
if ((node.x1 < 0) || (node.y1 < 0) || (node.x2 + 20 > _w) || (node.y2 + 20 > _h))
e += 1000000000000.0;
for (std::size_t i = 0; i < _figures.size(); ++i) {
if (node_i != i)
e += calc_node_pair(node_i, i);
}
return e;
}思考
和之前看的正交布局相关论文相比，这个算法的实现还是比较简单的。问题：
- 在判断是否最优值的时候，仅仅判断了此次计算结果和上次计算结果是否一致，容易导致产生局部最优解。
- 一次迭代的时间复杂度过高，n*n*n。
- 不知道这个能量计算公式的来由，是否最佳？
- 节点重叠的问题，只在能量计算中考虑，并不能完全避免结果中没有重叠的问题。
- 节点移动距离，单元格是按照最大的节点来定的。这样会不会产生稀疏图。