d3-quadtree

A quadtree рекурсивно разбивает двумерное пространство на квадраты, деля каждый квадрат на четыре равных квадрата. Каждая отдельная точка находится в уникальном листе узла; совпадающие точки представлены связанным списком. Quadtrees могут ускорить различные пространственные операции, такие как приближение Барнса–Хата для вычисления сил многих тел, обнаружения столкновений и поиска близлежащих точек.

Установка

Если вы используете NPM, npm install d3-quadtree. В противном случае, скачайте последнюю версию. Вы также можете загрузить напрямую с d3js.org, как автономную библиотеку, так и как часть D3 4.0. Поддерживаются среды AMD, CommonJS и vanilla. В vanilla экспортируется глобальная переменная d3:

<script src="https://d3js.org/d3-quadtree.v1.min.js"></script>
<script>

var quadtree = d3.quadtree();

</script>

Попробуйте d3-quadtree в вашем браузере.

Справочник по API

d3.quadtree([data[, x, y]]) Источник

Создает новый пустой quadtree с пустым объёмом и стандартными x- и y-функциями доступа. Если data указан, добавляет указанный массив данных в quadtree. Это эквивалентно:

var tree = d3.quadtree()
    .addAll(data);

Если также указаны x и y, устанавливает x- и y- функции доступа к указанным функциям до добавления указанного массива данных в quadtree, что эквивалентно:

var tree = d3.quadtree()
    .x(x)
    .y(y)
    .addAll(data);

quadtree.x([x]) Источник

Если x указан, устанавливает текущую функцию доступа к x-координате и возвращает quadtree. Если x не указан, возвращает текущую функцию доступа к x, которая по умолчанию:

function x(d) {
  return d[0];
}

Функция доступа x используется для получения x-координаты данных при добавлении и удалении из дерева. Она также используется при поиске для повторного доступа к координатам данных, ранее добавленных в дерево; поэтому функции доступа x и y должны быть согласованными, возвращая одно и то же значение для одного и того же входного значения.

quadtree.y([y]) Источник

Если y указан, устанавливает текущую функцию доступа к y-координате и возвращает quadtree. Если y не указан, возвращает текущую функцию доступа к y, которая по умолчанию:

function y(d) {
  return d[1];
}

Функция доступа y используется для получения y-координаты данных при добавлении и удалении из дерева. Она также используется при поиске для повторного доступа к координатам данных, ранее добавленных в дерево; поэтому функции доступа x и y должны быть согласованными, возвращая одно и то же значение для одного и того же входного значения.

quadtree.extent([extent]) Источник

Если extent указан, расширяет quadtree до покрытия указанных точек [[x0, y0], [x1, y1]] и возвращает quadtree. Если extent не указан, возвращает текущий объём quadtree [[x0, y0], [x1, y1]], где x0 и y0 — нижние границы включительно, а x1 и y1 — верхние границы включительно, или undefined, если у quadtree нет объёма. Объём также может быть расширен вызовом quadtree.cover или quadtree.add.

quadtree.cover(x, y) Источник

Расширяет quadtree, чтобы он покрывал указанную точку ⟨x,y⟩, и возвращает quadtree. Если объём quadtree уже покрывает указанную точку, этот метод ничего не делает. Если у quadtree есть объём, объём многократно удваивается, чтобы покрыть указанную точку, обворачивая корневой узел, если необходимо; если quadtree пуст, объём инициализируется объёмом [[⌊x⌋, ⌊y⌋], [⌈x⌉, ⌈y⌉]]. (Округление необходимо для того, чтобы, если объём впоследствии удваивается, границы существующих квадрантов не изменялись из-за ошибки с плавающей точкой.)

quadtree.add(datum) Источник

Добавляет указанный datum в quadtree, определяя его координаты ⟨x,y⟩ с помощью текущих x- и y-функций доступа и возвращает quadtree. Если новая точка находится вне текущего объёма quadtree, quadtree автоматически расширяется, чтобы покрыть новую точку.

quadtree.addAll(data) Источник

Добавляет указанный массив data в quadtree, вычисляя координаты ⟨x,y⟩ каждого элемента с использованием текущих x- и y-функций доступа и возвращает этот quadtree. Это примерно эквивалентно многократному вызову quadtree.add:

for (var i = 0, n = data.length; i < n; ++i) {
  quadtree.add(data[i]);
}

Однако этот метод приводит к более компактному quadtree, поскольку объём data вычисляется сначала, прежде чем добавлять данные.

quadtree.remove(datum) Источник

Удаляет указанный datum из quadtree, определяя его координаты ⟨x,y⟩ с помощью текущих x- и y-функций доступа и возвращает quadtree. Если указанный datum не существует в этом quadtree, этот метод ничего не делает.

quadtree.removeAll(data) Источник

…

quadtree.copy()

Возвращает копию quadtree. Все узлы в возвращаемом quadtree являются идентичными копиями соответствующего узла в quadtree; однако любые данные в quadtree объединены по ссылке, а не копируются.

quadtree.root() Источник

Возвращает корневой узел quadtree.

quadtree.data() Источник

Возвращает массив всех данных в quadtree.

quadtree.size() Источник

Возвращает общее количество данных в quadtree.

quadtree.find(x, y[, radius]) Источник

Возвращает элемент данных, ближайший к позиции ⟨x,y⟩ с заданным радиусом поиска radius. Если radius не указан, он по умолчанию равен бесконечности. Если данных в области поиска нет, возвращает undefined.

quadtree.visit(callback) Источник

Обрабатывает каждый узел в quadtree в порядке обхода в прямом порядке, вызывая указанную callback с аргументами node, x0, y0, x1, y1 для каждого узла, где node — посещаемый узел, ⟨x0, y0⟩ — нижние границы узла, а ⟨x1, y1⟩ — верхние границы, и возвращает quadtree. (Предполагая, что положительное x — справа, а положительное y — снизу, как обычно бывает в Canvas и SVG, ⟨x0, y0⟩ — верхний левый угол, а ⟨x1, y1⟩ — нижний правый угол; однако система координат произвольна, поэтому формально x0 <= x1 и y0 <= y1.)

Если callback возвращает true для данного узла, то потомки этого узла не посещаются; в противном случае все дочерние узлы посещаются. Это может использоваться для быстрого посещения только частей дерева, например, при использовании приближения Барнса–Хата. Однако обратите внимание, что дочерние квадранты всегда посещаются в порядке следования братьев: сверху слева, сверху справа, снизу слева, снизу справа. В таких случаях, как поиск, посещение братьев в определённом порядке может быть быстрее.

quadtree.visitAfter(callback) Источник

Обрабатывает каждый узел в quadtree в порядке обхода снизу вверх, вызывая указанную callback с аргументами node, x0, y0, x1, y1 для каждого узла, где node — посещаемый узел, ⟨x0, y0⟩ — нижние границы узла, а ⟨x1, y1⟩ — верхние границы, и возвращает quadtree. (Предполагая, что положительное x — справа, а положительное y — снизу, как обычно бывает в Canvas и SVG, ⟨x0, y0⟩ — верхний левый угол, а ⟨x1, y1⟩ — нижний правый угол; однако система координат произвольна, поэтому формально x0 <= x1 и y0 <= y1.) Возвращает root.

Узлы

Внутренние узлы quadtree представлены массивами из четырех элементов в порядке слева направо, сверху вниз:

• 0 — квадрант верхний левый, если есть.
• 1 — квадрант верхний правый, если есть.
• 2 — квадрант нижний левый, если есть.
• 3 — квадрант нижний правый, если есть.

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

Листовые узлы представлены в виде объектов со следующими свойствами:

• data - данные, связанные с этой точкой, переданные в quadtree.add.
• next - следующие данные в этом листе, если таковые имеются.

Свойство length может использоваться для различения листовых узлов от внутренних узлов: оно неопределено для листовых узлов и равно 4 для внутренних узлов. Например, чтобы перебрать все данные в листовом узле:

if (!node.length) do console.log(node.data); while (node = node.next);

Координаты точки по x и y не должны изменяться, пока точка находится в квадродереве. Чтобы обновить положение точки, удалите точку с помощью удаления, а затем снова добавьте её в квадродерево в новом положении. В качестве альтернативы, вы можете полностью удалить существующее квадродерево и создать новое с нуля; это может быть более эффективным, если многие точки сместились.