Ответ 1
Вот одно из решений проблемы: http://jsfiddle.net/5u9mzfse/
Более или менее меня просто интересовала эта актуальная проблема определения оптимального рендеринга, как это сделать алгоритмически.
Идея состоит в том, чтобы использовать тот факт, что порядок обрабатываемых узлов имеет значение, поэтому вы можете перетасовать заказ и найти порядок, который создает наилучшие результаты. Самый простой способ сделать это - проверить, сталкиваются ли перегородки строк, с которыми сталкиваются края. Здесь я предполагаю, что начало и конец ребер - достаточно хорошая оценка для ограничивающей рамки.
Края должны быть сначала сохранены в списке
var edgeList = [["10007154_1100","148570017_1100",{"label":""}, ...]
Тогда
- Перетасовать список
- Удалить узлы
- Вычислить ограничивающие поля ребер из выходных
- Рассчитать, сколько ограничивающих полей перекрывается
- Если количество столкновений равно нулю, выводите вывод, в противном случае продолжайте до тех пор, пока не будут выполнены итерации max_cnt и выберите наилучшее пока
Ограничивающие прямоугольники ребер от отображаемого вывода можно найти, используя следующее:
var nn = svg.select(".edgePaths");
var paths = nn[0][0];
var fc = paths.firstChild;
var boxes = [];
while(fc) {
var path = fc.firstChild.getAttribute("d");
var coords = path.split(/,|L/).map(function(c) {
var n = c;
if((c[0]=="M" || c[0]=="L")) n = c.substring(1);
return parseFloat(n);
})
boxes.push({ left : coords[0], top : coords[1],
right : coords[coords.length-2],
bottom : coords[coords.length-1]});
fc = fc.nextSibling;
}
Вы просто подсчитаете, столкнулись ли ящики, я понял, что что-то вроде этого дает приблизительно правильные результаты:
var collisionCnt = 0;
boxes.forEach( function(a) {
// --> test for collisions against other nodes...
boxes.forEach(function(b) {
if(a==b) return;
// test if outside
if ( (a.right < b.left) ||
(a.left > b.right) ||
(a.top > b.bottom) ||
(a.bottom < b.top) ) {
// test if inside
if(a.left >= b.left && a.left <=b.right
|| a.right >= b.left && a.right <=b.right) {
if(a.top <= b.top && a.top >= b.bottom) {
collisionCnt++;
}
if(a.bottom <= b.top && a.bottom >= b.bottom) {
collisionCnt++;
}
}
} else {
collisionCnt++;
}
})
})
Затем вы знаете, сколько ребер пересекает друг друга с помощью этого набора ребер.
Затем, после каждого раунда, проверьте, что если это лучший массив, который мы имеем до сих пор, или если немедленный выход не происходит,
if(collisionCnt==0) {
optimalArray = list.slice();
console.log("Iteration cnt ", iter_cnt);
break;
}
if(typeof(best_result) == "undefined") {
best_result = collisionCnt;
} else {
if(collisionCnt < best_result) {
optimalArray = list.slice();
best_result = collisionCnt;
}
}
Во время тестирования, по крайней мере, с помощью простого графика алгоритм требовал 1-5 раундов для расчета оптимального порядка ребер, поэтому он выглядит так, как будто он может работать довольно хорошо, если диаграмма не слишком велика.