Skip to content

RU Компоновка силовыми полями

Jump to bottom Edit New page
mingun edited this page Jun 18, 2014 · 3 revisions

Вики ▸ Справка по API ▸ Компоновки ▸ Компоновка силовыми полями
English | Русский

Гибкая реализация компоновки графов направленными силами использует для позиционирования интегрирование Верле, удовлетворяющее простым ограничениям. Для более физических симуляций смотрите Томаса Якобсена (Thomas Jakobsen). Эта реализация использует квадродерево для ускорения взаимодействия заряда с помощью приближения Барнса-Хата. В дополнение к отталкивающей силе заряда, используется псевдо-гравитационная сила для удержания узлов в центре видимой области и избегания расшвыривания отсоединённых подграфов, в то время, как связи обеспечивают фиксированное геометрическое расстояние между узлами. Дополнительные пользовательские силы и ограничения могут быть применены по событию "tick" простым обнослением атрибутов x и y узлов.

Компоновка силовыми полями

Несколько впечатляющих примеров:

Подобно другим классам в D3, компоновки следуют шаблону цепочечных методов, по которому методы-установщики возвращают саму компоновку, что позволяет выполнять несколько сеттеров в лаконичном выражении. В отличии от некоторых других компоновок, реализации которых не содержат внутреннего состояния, компоновка силовыми полями хранит ссылки на связанные узлы и связи; таким образом, данный экземпляр компоновки силовыми полями может использоваться только с одним набором данных.

# d3.layout.force()

Создаёт новую компоновку силовыми полями с настройками по умолчанию: размер 1×1, силя связей равна 1, трение — 0.9, расстояние — 20, сила заряда — -30, сила гравитации — 0.1 и параметр тета — 0.8. По умолчанию узлы и связи являются пустыми массивами, и когда компонока запускается, внутреннее охлаждение параметра альфа устанавливается в 0.1. Общим шаблоном конструирования компоновок силовыми полями является установка всех конфигурационных свойств с последующим вызовом метода start:

var force = d3.layout.force()
    .nodes(nodes)
    .links(links)
    .size([w, h])
    .start();

Обратите внимание, что, подобно другим компоновкам D3, компоновка силовыми полями не обязана использовать какое-то определённое визуальное представление. Чаще всего узлы отображаются на элементы SVG circle, а связи отображаются на элементы SVG line. Однако, вы так же можете отображать узлы как символы или как изображения.

# force.size([size])

Если указан параметр size, устанавливает доступный размер компоновки в указанный двухэлементный массив чисел, представляющих координаты x и y. Если параметр size не указан, возвращает текущие размеры, которые по умолчанию установлены в 1×1. Размер воздействует на два аспецта компоновки силовыми полями: гравитационный центр и первоначальную случайную позицию. Центр гравитации — это просто точка с координатами [ x / 2, y / 2 ]. Когда узлы добавляются к компоновке силовыми полями, если они ещё не имеют установленных атрибутов x и y, то эти атрибуты инициализируются случайным числом с равномерным распределением в диапазонах [0, x] и [0, y] соответственно.

# force.linkDistance([distance])

Если указан параметр distance, устанавливает целевое расстояние между связанными узлами в указанное значение. Если параметр distance не указан, возвращает текущее расстояние связи, которое по умолчанию установлено в 20. Если расстояние является константой, то все связи имеют одно и то же расстояние. Если же расстояние является функцией, она вычисляется для каждой связи (в порядке следования связей); параметрами передаются связь и её индекс, контекст this привязывается к компоновке силовыми полями; возвращаемое значение функции используется для установки расстояния каждой связи. Функция выполняется каждый раз, когда компоновка запускается. Обычно расстояние задаётся в пикселях; однако, единицы измерения произвольны по отношения к размеру компоновки.

Связи реализованы не как «упругие силы», как это принято в других компоновках силовыми полями, а как слабые геометрические ограничения. С каждым тиком компоновки, вычисляется расстояние между каждой парой связанных узлов и сравнивается с расстоянием до цели; затем связи перемещаются друг к другу или друг от друга, таким образом, чтобы оказаться на нужном расстоянии. Этот метод расслабления ограничений на верхней позиции интегрирования Верле значительно более стабилен, нежели предыдущие методы с использованием упругих сил, а также позволяет гибко реализовывать другие ограничения в слушателе события tick, например, иерархическое наслоение.

# force.linkStrength([strength])

Если указан параметр strength, устанавливает силу (жёсткость) связей в указанное значение в диапазоне [0, 1]. Если параметр strength не указан, возвращает текущую силу связи, которая по умолчанию установлена в 1. Если сила является константой, то все связи имеют одну и ту же силу. Если же сила является функцией, она вычисляется для каждой связи (в порядке следования связей); параметрами передаются связь и её индекс, контекст this привязывается к компоновке силовыми полями; возвращаемое значение функции используется для установки силы каждой связи. Функция выполняется каждый раз, когда компоновка запускается.

# force.friction([friction])

Если указан параметр friction, устанавливает коэффициент трения в указанное значение. Если параметр friction не указан, возвращает текущий коэффициент, который по умолчанию установлен в 0.9. Название этого параметра, возможно, может ввести в заблуждение; он не соответствует привычному физическому коэффициенту трения. Вместо этого он больше приближён к спаду скорости: на каждом тике моделирования скорость частиц умножается на этот коэффициент трения. Таким образом, значение 1 соответсвует окружению без трения, а значение 0 замораживает все частицы на месте. Значения за пределами диапазона [0, 1] не рекомендуются и могут иметь дестабилизирующие эффекты.

# force.charge([charge])

Если указан параметр charge, устанавливает силу заряда в указанное значение. Если параметр charge не указан, возвращает текущую силу заряда, который по умолчанию установлена в -30. Если сила заряда является константой, то все узлы имеют один и тот же заряд. Если же сила заряда является функцией, она вычисляется для каждого узла (в порядке следования узлов); параметрами передаются узел и его индекс, контекст this привязывается к компоновке силовыми полями; возвращаемое значение функции используется для установки заряда каждого узла. Функция выполняется каждый раз, когда компоновка запускается.

Отрицательные значения дают отталкивание узлов, в то время, как положительные значения способствуют притягиванию узлов. Для компоновок графов следует использовать отрицательные значения; для моделирования n тел следует использовать положительные значения. Все узлы предполагаются бесконечномалыми точками с равными зарядами и массой. Силы зарядов эффективно реализуются через алгоритм Барнса-Хата, вычисляющего квадродерево на каждом тике. Установка силы заряда в ноль отключает вычисление квадродерева, что может заметно повысить производительность, если вам не нужны силы от n тел.

# force.chargeDistance([distance])

Если указан параметр distance, устанавливает максимальное расстояние, на котором действуют заряды. Если параметр distance не указан, возвращает текущее максимальное расстояние действия заряда, которое по умолчанию бесконечно. Установка конечного расстояния действия заряда повышает производительность компоновки силовыми полями и производит более компактные компоновки; сизы зарядов, ограниченные на расстоянии особенно полезны в сочетании с пользовательской гравитацией. Для примера смотрите «Созвездия директоров и их звёзды» (The New York Times).

# force.theta([theta])

Если указан параметр theta, устанавливает критерий приближения Барнса-Хата в указанное значение. Если параметр theta не указан, возвращает текущее значение, которое по умолчанию установлено в 0.8. В отличии от связей, которые применяются только к двум связанным узлам, сила заряда глобальна: каждый узел влияет на любой другой узел, даже если они расположены в разобщённых подграфах.

Для избегания квадратичного падения производительности для больших графов, компоновка силовыми полями использует приближение Барнса-Хата, которое даёт сложность O(n log n) на каждом тике. На каждом тике создаётся квадродерево, в которое сохраняются позиции узлов; затем для каждого узла вычисляется сумма сил зарядов всех узлов, действующих на данный узел. Для кластеров узлов, расположенных далеко, силу заряда можно аппроксимировать, трактуя далеко расположенный кластер узлов как один большой узел. Параметр theta определяет точность вычисления: если отношение площиди квадранта в квадродереве к расстоянию между узлом и центром масс квадранта меньше theta, все узлы в данном квадранте трактуются как один большой узел, а не вычисляются поодиночке.

# force.gravity([gravity])

Если указан параметр gravity, устанавливает силу гравитации в указанное значение. Если параметр gravity не указан, возвращает текущую силу гравитации, которая по умолчанию установлена в 0.1. Название этого параметра, возможно, может ввести в заблуждение; он не соответствует привычной физической гравитации (которая может быть смоделирована с использованием положительнго заряда). Вместо этого гравитация реализована как слабое геометрическое ограничение, подобное виртуальной упругой связи между узлом и центром компоновки. Этот подход обладает хорошим свойством: вблизи центра компоновки гравитационная сила всегда нулевая, что предотвращает любые местные искажения компоновки; когда узлы отдаляются от центра, гравитационная сила становится сильнее в линейной пропорции в зависимости от расстояния. Таким образом, в какой-то момент гравитация всегда преодолеет силы оттталикивания зарядов, что предотвратит покидание компоновки отсоединёнными узлами.

Гравитация может быть отключена путём установки гравитационной силы в ноль. Если вы отключите гравитацию, вам рекомендуется реализовать какие-нибудь другие геометрические ограничения для предотвращения покидания узлов пределов компоновки, например, ограничивать их границами компоновки.

# force.nodes([nodes])

Если указан параметр nodes, устанавливает ассоциированные с компоновкой узлы в указанный массив. Если параметр nodes не указан, возвращает текущий массив узлов, который по умолчанию установлен в пустой массив. Каждый узел имеет следующие атрибуты:

  • index — начинающийся с нуля индекс узла в массиве nodes.
  • x — координата x текущей позиции узла.
  • y — координата y текущей позиции узла.
  • px — координата x предыдущей позиции узла.
  • py — координата y предыдущей позиции узла.
  • fixed — булево значение, указывающее, является ли позиция узла неизменной.
  • weight — вес узла; количество ассоциированных связей.

Эти атрибуты не обязательно устанавливать перед передачей массива узлов в компоновку; если они не установлены, они будут инициализированы подходящими значениями по умолчанию при вызове метода start компоновки. Однако следует помнить, что если вы храните в узлах другие данные, ваши атрибуты не должны конфликтовать с перечисленными выше свойствами, используемыми компоновкой.

# force.links([links])

Если указан параметр links, устанавливает ассоциированные с компоновкой связи в указанный массив. Если параметр links не указан, возвращает текущий массив связей, который по умолчанию установлен в пустой массив. Каждая связь имеет следующие атрибуты:

  • source — исходный узел (элемент в массиве nodes).
  • target — целевой узел (элемент в массиве nodes).

Обратите внимание: значения исходного и целевого узла могут быть изначально указаны как индексы в массиве nodes; они будут заменены на ссылки после вызова метода start. Объекты связи могут иметь дополнительные поля, которые вы можете определить; эти данные могут использоваться для вычисления силы связи и расстояния, на котором она действует, через функции доступа.

# force.start()

Запускает моделирование; этот метод должен быть вызван при первом создании компоновки, после назначения узлов и связей. Кроме того, он снова должен быть вызван при изменении узлов или связей. Внутри компоновка использует охлаждающий параметр alpha, который контролирует температуру компоновки: когда физическое моделирование сходится к стабильной компоновке, температура понижается, вызывая более медленое движение узлов. В конце концов, alpha понижается до порогового значения и моделирование полностью останавливается, освобождая CPU и предотвращая расход батареи. Компоновка может быть снова разогрета методом resume или путём повторного запуска; это происходит автоматически при использовании поведения перетаскивания.

При запуске компоновка инициализирует различные атрибуты на ассоциированных узлах. Атрибут index каждого узла вычисляется путём обхода массива, начиная с нуля. Начальные координаты x и y, если они ещё не установлены внешним кодом в допустимые числа, вычисляются путём узучения соседних узлов: если связанный узел уже имеет начальную позицию по x или y, соответствующие координаты применяются к новому узлу. Это повышает стабильность компоновки графа при добавлении новых узлов по сравнению с использованием значений по умолчанию, которые инициализируют позицию случайным числом в пределах размера компоновки. Предыдущие позиции px и py, если они ещё не установлены, устанавливаются в начальную позицию давая новым узлам нулевую скорость. Наконец, флаг fixed по умолчанию устанавливание в false.

Компоновка также инициализирует атрибуты source и target на ассоциированных связях: для удобства эти атрибуты могут быть определены числовыми индексами, а не прямыми связями, так что узлы и связи могут быть прочитаны из файла JSON или другого статического описания, которое не позволяет цикличесвие ссылки. Атрибуты source и target на поступающих связях, если они являются числами, просто заменяются на соответствующие записи в массиве nodes; таким образом, атрибуты на существующих связях не затрагиваются при повторном запуске компоновки. Расстояния и силы связей так же рассчитываются при запуске.

# force.alpha([value])

Возвращает / устанавливает охлажающий параметр компоновки силовыми полями, alpha. Если указан параметр value, устанавливает alpha в указанное значение и возвращает компоновку. Если значение больше нуля, этот метод также перезапускает компоновку, если она ещё не запущена, рассылает событие "start" и включает таймер. Если значение неположительно и компоновка уже запущена, этот метод останавливает компоновку на следующем тике и рассылает событие "end". Если параметр value не указан, возвращает текущее значение alpha.

# force.resume()

Эквивалентен коду:

force.alpha(0.1);

Устанавливает охлаждающий параметр alpha в 0.1. Этот метод устанавливает внутренний параметр alpha в 0.1 и перезапускает таймер. Обычно вам не нужно вызывать данный метод непосредственно; он автоматически вызывается при запуске. Так же он автоматически вызывается в процессе перетаскивания.

# force.stop()

Эквивалентен коду:

force.alpha(0);

Завершает моделирование, устанавливая параметр охлаждения alpha в ноль. Метод может использоваться для явного завершения моделирования, например, если вы хотите показать анимацию или позволить провести другие взаимодействия. Если вы не остановите компоновку явно, она всё равно остановится автоматически после того, как охлаждающий параметр компоновки достигнет некоторого критического значения.

# force.tick()

Запускает один тик моделирования компоновки силовыми полями. Этот метод может использоваться в сочетании с методами start и stop для вычисления статической компоновки. Например:

force.start();
for (var i = 0; i < n; ++i) force.tick();
force.stop();

Количество итераций зависит от размера графа и его сложности. Выбор начальных позиций также может иметь значительное влияние на то, как скоро граф сойдётся к хорошему решению. Например, здесь узлы выстраиваются по диагонали:

var n = nodes.length;
nodes.forEach(function(d, i) {
  d.x = d.y = width / n * i;
});

Если вы не инициализаруете позиции вручную, компоновка инициализирует их случайными значениями, что может привести к непредсказуемому поведению.

# force.on(type, listener)

Регистрирует указанного слушателя listener для приёма указанных типов событий type, генерируемых компоновкой силовыми полями. На текущий момент поддерживаются события "start", "tick" и "end". Событие "tick" рассылается по каждому тику моделирования. Слушайте событие tick для обновления отображаемых позиций узлов и связей. Например, если вы изначально отображали узлы и связи следующим образом:

var link = vis.selectAll("line")
    .data(links)
  .enter().append("line");

var node = vis.selectAll("circle")
    .data(nodes)
  .enter().append("circle")
    .attr("r", 5);

Вы можете установить их позиции по тику:

force.on("tick", function() {
  link.attr("x1", function(d) { return d.source.x; })
      .attr("y1", function(d) { return d.source.y; })
      .attr("x2", function(d) { return d.target.x; })
      .attr("y2", function(d) { return d.target.y; });

  node.attr("cx", function(d) { return d.x; })
      .attr("cy", function(d) { return d.y; });
});

В этом случае мы сохранили выбранные узлы node и связи link при инициализации, так что нам не пришлось выбирать их на каждом тике. Если вы хотите, можете отобрахать узлы и связи по разному; например, вы можете использовать символы вместо кружочков.

Событие "end" рассылается, когда внутренний охлаждающий параметр моделирования alpha достигнет нуля.

# force.drag()

Привязывает поведение к узлам для возможности их интерактивного перемещения с помощью мыши или прикосновений. Используйте этот метод в сочетании с оператором call на узлах; например, напишите node.call(force.drag) при инициализации. Событие drag устанавливает атрибут fixed на узлах по событию браузера mouseover, так что как только курсор оказывается над узлом, тот перестаёт перемещаться. Фиксация по событию mouseover вместо события mousedown упрощает захват движущихся узлов. Когда поступает событие mousedown, в каждом последующем событии mousemove до возникновения события mouseup центр узла устанавливается в текущую позицию мыши. Кроме того, каждое событие mousemove вызывает resume на компоновке, разогревая моделирвание. Если вы хотите, чтобы перемещённые узлы оставались зафиксированными после перемещения, устанавливайте атрибут fixed в true по событию dragstart, как показано в примере липучей компоновки силовыми полями.

Замечания по реализации: слушатели событий mousemove и mouseup регистрируются для текущего окна, так что когда пользователь начинает перетаскивать узел, он может продолжить его перетаскивать даже когда мышь покинет окно. Слушатели событий используют пространство имён "force" для избегания пересечений с другими слушателями событий, которые вы можете захотеть привязать к узлам или к окну. Если узел перемещается поведением перетаскивания, последующее событие click, которое будет вызвано после последнего mouseup перехватывается и его поведение по умолчанию отменяется. Если вы регистрируете слушатель события click, вы может еигнорировать эти щелчки при перетаскивании, если вы видите, что поведение по умолчанию было отменено:

selection.on("click", function(d) {
  if (d3.event.defaultPrevented) return; // игнорируем перетаскивание
  otherwiseDoAwesomeThing();
});

Смотрите схлопываемую компоновку силовыми полями и расталкивающие силы в качестве примеров.

Add a custom footer
Add a custom sidebar
Clone this wiki locally