d3-quadtree

A quadtree recursively partitions two-dimensional space into squares, dividing each square into four equally-sized squares. Each distinct point exists in a unique leaf node; coincident points are represented by a linked list. Quadtrees can accelerate various spatial operations, such as the Barnes–Hut approximation for computing many-body forces, collision detection, and searching for nearby points.

Установка

Если вы используете npm, npm install d3-quadtree. Вы также можете загрузить последнюю версию с GitHub. Для обычного HTML в современных браузерах импортируйте d3-quadtree из Skypack:

<script type="module">

import {quadtree} from "https://cdn.skypack.dev/d3-quadtree@3";

const tree = quadtree();

</script>

Для устаревших сред вы можете загрузить UMD-пакет d3-quadtree с npm-базируемого CDN, такого как jsDelivr; экспортируется глобальная переменная d3:

<script src="https://cdn.jsdelivr.net/npm/d3-quadtree@3"></script>
<script>

const tree = d3.quadtree();

</script>

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

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

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

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

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

const 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 (let 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) Источник

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

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 и возвращает все узлы в прямоугольном объёме [xmin, ymin, xmax, ymax], игнорируя квадранты, которые не могут содержать такой узел:

function search(quadtree, xmin, ymin, xmax, ymax) {
  const results = [];
  quadtree.visit((node, x1, y1, x2, y2) => {
    if (!node.length) {
      do {
        let 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(callback) Источник

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