d3-quadtree

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

Установка

Если вы используете 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([данные[, x, y]]) Исходный код

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

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

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

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

quadtree.x([x]) Исходный код

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

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

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

quadtree.y([y]) Исходный код

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

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

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

quadtree.extent([объём]) Исходный код

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

quadtree.cover(x, y) Исходный код

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

quadtree.add(данные) Исходный код

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

quadtree.addAll(данные) Исходный код

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

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

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

quadtree.remove(данные) Исходный код

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

quadtree.removeAll(данные) Исходный код

…

quadtree.copy()

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

quadtree.root() Исходный код

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

quadtree.data() Исходный код

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

quadtree.size() Исходный код

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

quadtree.find(x, y[, радиус]) Исходный код

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

quadtree.visit(обработчик) Исходный код

Посещает каждый узел в дереве квадрантов в ходе предварительного обхода, вызывая указанный обработчик с аргументами узел, x0, y0, x1, y1 для каждого узла, где узел — это посещаемый узел, ⟨x0, y0⟩ — нижние границы узла, а ⟨x1, y1⟩ — верхние границы, и возвращает дерево квадрантов.

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

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

quadtree.visitAfter(обработчик) Исходный код

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

Узлы

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

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

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

END_OF_DOCUMENT_MARKER

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

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

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

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

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