d3-quadtree

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

Установка

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

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

var quadtree = d3.quadtree();

</script>

Справочник 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(данные) Источник

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

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 для данного узла, то потомки этого узла не посещаются; в противном случае посещаются все дочерние узлы. Это можно использовать для быстрого обхода только части дерева, например, при использовании приближения Барнса—Хата. Однако обратите внимание, что дочерние квадранты всегда посещаются в порядке следования: верхний левый, верхний правый, нижний левый, нижний правый. В таких случаях, как поиск, посещение потомков в определённом порядке может быть быстрее.

В качестве примера, следующее посещает дерево квадрантов и возвращает все узлы в прямоугольном объёме [xmin, ymin, xmax, ymax], игнорируя квадранты, которые не могут содержать какой-либо узел:

function search(quadtree, xmin, ymin, xmax, ymax) {
  const results = [];
  quadtree.visit(function(node, x1, y1, x2, y2) {
    if (!node.length) {
      do {
        var d = node.data;
        if (d[0] >= xmin && d[0] < xmax && d[1] >= ymin && d[1] < ymax) {
          results.push(d);
        }
      } while (node = node.next);
    }
    return x1 >= xmax || y1 >= ymax || x2 < xmin || y2 < ymin;
  });
  return results;
}

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 - нижний правый квадрант, если есть.

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

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

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

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

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

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