RU Квадродерево
Вики ▸ Справка по API ▸ Геометрия ▸ Квадродерево
English | Русский
Квадродерево — это двумерное рекурсивное пространственное разбиение. Эта реализация использует квадратные разделы, деля каждый квадрат на четыре одинаковых квадратика. Каждая точка существует в уникальном узле; если несколько точек находятся в одинаковой позиции, некоторые точки могут быть сохранены во внутренних узлах вместо листьев. Квадродеревья могут использоваться для ускорения различных пространственных операций, например, при аппроксимации Барнса-Хата (Barnes-Hut) для вычисления сил, действующих между n телами, или для определения столкновений.
# d3.geom.quadtree()
Создаёт новую фабрику квадродеревьев с умолчательными функцией доступа к координате x, функцией доступа к координате y и размером. Возвращёная функция может использоваться для создания любого количества квадродеревьев из данных с фабричной конфигурацией.
# quadtree(points)
Конструирует новое квадродерево для указанного массива точек points, возвращая корневой узел нового квадродерева. Координаты x и y каждой точки определяются текущими функциями доступа к координатам. Для построения квадродерева путём инкрементального добавления точек, указанный массив points может быть пустым, а точки могут быть добавлены позже к возвращённому корневому узлу; в этом случае вы также должны указать размеры квадродерева.
Каждый узел в квадродереве имеет несколько свойств:
- nodes — разрежённый массив из четырёх дочерних узлов в порядке: верхний-левый, верхний-правый, нижний-левый, нижний-правый
- leaf — булевый флаг, указывающий, является ли этот узел листом или внутренним узлом
- point — точка, ассоциированная с этим узлом, если она есть (может применяться как к внутренним узлам, так и к листьям)
- x — координата x ассоциированной точки, если она есть
- y — координата y ассоциированной точки, если она есть
Возвращённый корневой узел также определяет методы add и visit.
# root.add(point)
Добавляет указанную новую точку point в квадродерево.
# root.visit(callback)
Посещает каждый узел в квадродереве, выполняя указанную функцию обратного вызова callback с аргументами {node, x1, y1, x2, y2} для каждого узла. Узлы обходятся в прямом порядке. Если функция обратного вызова возвращает true для указанного узла, то потомки этого узла не посещаются; в противном случае все потомки узла посещаются.
# quadtree.x([x])
Если указан параметр x, устанавливает функцию доступа к координате x и возвращает эту фабрику квадродеревьев. Если параметр x не указан, возвращает текущую функцию доступа к координате x, которая по умолчанию установлена в:
function(d) { return d[0]; }Для каждой точки, добавленной в квадродерево либо в процессе первоначального конструирования, либо ленивого добавления, функция доступа к координате x вызывается с аргументами {d, i}, где d — это текущая точка, а i — её индекс в массиве всех точек. Функция доступа к координате x должна вернуть числовое значение, определяющее координату x данной точки. Функция доступа к координате x также может быть определена в качестве константного числа вместо функции, если нужно.
# quadtree.y([y])
Если указан параметр y, устанавливает функцию доступа к координате y и возвращает эту фабрику квадродеревьев. Если параметр y не указан, возвращает текущую функцию доступа к координате y, которая по умолчанию установлена в:
function(d) { return d[1]; }Для каждой точки, добавленной в квадродерево либо в процессе первоначального конструирования, либо ленивого добавления, функция доступа к координате y вызывается с аргументами {d, i}, где d — это текущая точка, а i — её индекс в массиве всех точек. Функция доступа к координате y должна вернуть числовое значение, определяющее координату y данной точки. Функция доступа к координате y также может быть определена в качестве константного числа вместо функции, если нужно.
# quadtree.extent([extent])
Если указан параметр extent, устанавливает текущие размеры и возвращает эту фабрику квадродеревьев. Если параметр extent не указан, возвращает текущие размеры, которые по умолчанию установлены в null. Когда равмеры установлены в null, они считаются автоматически путём сканирования массива входных точек, переданных в конструктор квадродерева. В противном случае размеры должны быть указаны как двумерный массив [[x0, y0], [x1, y1]], где x0 и y0 являются нижними границами размера, а x1 и y1 — верхними границами размера. Установка размера требуется при ленивом конструировании квадродерева из первоначально пустого множества узлов.