Алгоритм автоматического размещения форм блок-схемы
Моей команде нужно построить генератор блок-схем на JavaScript, используя либо HTML5 Canvas, либо библиотеку D3 (или что-нибудь еще более подходящее, предложения приветствуются). Блок-схема будет сгенерирована из ориентированного графика, определенного в документе JSON. Мой вопрос заключается в следующем: какой стандартный алгоритм мы могли бы использовать для облегчения автоматического размещения фигур в блок-схеме (узлы в графике), чтобы минимизировать количество перекрывающихся соединений и их длины?
4 ответов:
Стандартный алгоритм, который вы ищете, - это силовой ориентированный граф: http://en.wikipedia.org/wiki/Force-based_algorithms_ (graph_drawing) Если вам нужна легкая, браузерная и эффективная библиотека FD js, взгляните на arbor.js: https://github.com/samizdatco/arbor
IMHO D3-самая мощная библиотека, которую вы найдете (она встраивает алгоритм, основанный на силе), но она не совместима с IE
JIT также является хорошей библиотекой (в нее также встроен алгоритм на основе силы), не совместимый с IE
WireIt (YUI3) и JSplump (jQuery) являются хорошими библиотеками сантехники, но не включают алгоритмы FD.
Силовой алгоритм не совсем оптимален для такого рода задач. Я бы скорее предложил использовать многослойный графический рисунок (http://en.wikipedia.org/wiki/Layered_graph_drawing ) алгоритм. Хорошей JS-реализацией такого алгоритма является Dagre (https://github.com/cpettitt/dagre ). вы также можете взглянуть на мой пост в блоге об автоматической верстке и рендеринге направленных графов: http://www.daviddurman.com/automatic-graph-layout-with-jointjs-and-dagre.html .
JavaScript InfoVis Toolkit (JIT) может иметь некоторые инструменты, которые подходят для ваших целей:
Comments