Избегайте столкновений между узлами и ребрами в силовом макете D3.

В этом примере: http://bl.ocks.org/mbostock/1747543:

введите здесь описание изображения

...Майк показывает нам, как избежать коллизий между узлами, чтобы никакие два узла не перекрывали друг друга.

Интересно, можно ли избежать столкновения между узлами и ребрами, чтобы ни один узел не «обрезал» или не перекрывал ребро, если он не соединен этим ребром.

Следующий пример с использованием D3 force-direct показывает, что узел L перекрывается с краем, соединяющим I и A, и аналогичным образом узел M перекрывается с ребром, соединяющим L и D. Как предотвратить такие случаи?

введите здесь описание изображения


javascript d3.js algorithm force-layout graph-layout
person skyork    schedule 29.07.2013    source источник
comment
Это невозможно с принудительной реализацией макета в D3. Вам нужно будет реализовать это самостоятельно. Обратите внимание, что это на самом деле очень сложная задача (в вычислительном отношении), поэтому даже если у вас есть реализация, она, вероятно, не захочет запускать ее в браузере.   -  person Lars Kotthoff    schedule 29.07.2013
comment
@LarsKotthoff, вы говорите, что вообще ни один известный алгоритм компоновки графа (включая тот, который реализован для D3) не может эффективно решить эту проблему?   -  person skyork    schedule 29.07.2013
comment
Это зависит от вашего определения эффективности. Найти (статическое) решение для этого звучит как минимум NP-сложно для меня. Это не значит, что его вообще можно быстро решить в конкретных случаях, но в целом это сложно (а для больших графов, наверное, быстро не получится). Затем изменить это исходное решение таким образом, чтобы узлы слегка двигались (как это делает симуляция), было бы очень легко, поскольку вам нужно только выполнить локальный ремонт.   -  person Lars Kotthoff    schedule 29.07.2013
comment
Это не сложная проблема. Просто добавьте силы к краям в дополнение к узлам. Если возможно, простое увеличение размера графика значительно помогло бы.   -  person tba    schedule 11.08.2013
comment
@tba, что именно вы имеете в виду, говоря о добавлении сил к краям? Увеличение размера графика не очень гибко, поскольку область, доступная для отображения графика, может быть ограничена приложением.   -  person skyork    schedule 13.08.2013
comment
D3 визуализирует график с помощью физического моделирования — узлы имеют одинаковый заряд и, следовательно, отталкиваются друг от друга. Теоретически мы могли бы скорректировать симуляцию, добавив заряд к краям. К сожалению, D3 не поддерживает это из коробки.   -  person tba    schedule 13.08.2013
comment
Мне интересно, можно ли использовать силу столкновения, чтобы подтолкнуть узлы. github.com/d3/d3-force/ blob/master/src/collide.js#L45-L47 в этом коде вычисляет расстояние между узлом и другим. Не кажется непомерно дорогим выполнение симуляции от узла к ребру. Я пытаюсь посмотреть, смогу ли я легко реализовать это в своей среде. Я совершенно новичок в D3, и этот Q довольно старый. Так что не уверен, что мои комментарии соответствуют оригинальному Q.   -  person yosukesabai    schedule 20.01.2019

Ответы (1)


arrow_upward
7
arrow_downward

Если в вашем графе не слишком много узлов, вы можете его подделать. Просто вставьте один или несколько узлов для каждой ссылки и установите их положение вдоль ссылки в обработчике tick. Посетите http://bl.ocks.org/couchand/7190660 для примера, но изменения в версии Майка Бостока составляют в основном только:

var linkNodes = [];

graph.links.forEach(function(link) {
  linkNodes.push({
    source: graph.nodes[link.source],
    target: graph.nodes[link.target]
  });
});

а также

// force.on('tick', function() {
linkNodes.forEach(function(node) {
  node.x = (node.source.x + node.target.x) * 0.5;
  node.y = (node.source.y + node.target.y) * 0.5;
});

Это приведет к довольно серьезному снижению производительности, если у вас очень много узлов и ребер, но если ваш график не станет намного больше, чем ваш пример, это вряд ли будет заметно.

Вы также можете поиграться с относительной силой реальных узлов по сравнению с узлами связи.

Сделайте еще один шаг вперед, и вы получите красивые изогнутые ссылки http://bl.ocks.org/mbostock/4600693. .

person couchand    schedule 28.10.2013