Двоичное дерево поиска

Ссылка на API ▸ Геометрия ▸ Двоичное дерево поиска

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

d3.geom.quadtree()

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

quadtree(points), quadtree(points, x2, y2), quadtree(points, x1, y1, x2, y2)

Строит новое дерево поиска для указанного массива данных points, возвращая корневой узел нового дерева поиска. Элементы массива points должны иметь члены x и y, определяющие их координаты. Текущие x- и y- функции доступа игнорируются. Объём также может быть задан с помощью дополнительных необязательных аргументов с x1 и y1 явно указанными или принятыми за ноль, если опущены. Чтобы построить дерево поиска, добавляя точки постепенно, указанный массив points может быть пустым, а затем точки могут быть позднее добавлены в возвращённый корневой узел; в этом случае вы также должны указать объём дерева поиска.

Каждый узел в дереве поиска имеет несколько свойств:

• nodes - разреженный массив из четырёх дочерних узлов в порядке: верхний левый, верхний правый, нижний левый, нижний правый
• leaf - булево значение, указывающее, является ли это внутренним узлом или листом
• point - точка, связанная с этим узлом, если она есть (может относиться как к внутренним, так и к листовым узлам)
• x - координата x связанной точки, если она есть
• y - координата y связанной точки, если она есть

Возвращаемый корневой узел также определяет методы add и visit.

root.add(point)

Добавляет указанную новую точку в дерево поиска.

root.visit(callback)

Посещает каждый узел в дереве поиска, вызывая указанную callback с аргументами {node, x1, y1, x2, y2} для каждого узла, где node — посещаемый узел, а оставшиеся аргументы — координаты верхнего левого и нижнего правого углов узла соответственно. (Примечание: определение координатной системы, используемой деревом поиска, произвольно, поэтому более точное правило заключается в том, что x1 <= x2 и y1 <= y2. В типичной системе координат, используемой SVG и Canvas, начало ⟨0,0⟩ находится в верхнем левом углу, и, следовательно, ⟨x1, y1⟩ также является верхним левым углом текущего узла.) Узлы обходятся в порядке обхода.

root.find(point)

Для заданной точки [x,y] возвращает ближайшую точку в дереве поиска.

quadtree.x([x])

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

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

Для каждой точки, добавленной в дерево поиска, либо во время начальной инициализации, либо позже добавленной, функция доступа x вызывается с аргументами {d, i}, где d — текущая точка, а i — её индекс в массиве всех точек. Функция доступа x должна затем вернуть числовое значение, обозначающее координату x данной точки. Функция доступа x также может быть определена как константа, а не как функция, если необходимо.

quadtree.y([y])

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

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

Для каждой точки, добавленной в дерево поиска, либо во время начальной инициализации, либо позже добавленной, функция доступа y вызывается с аргументами {d, i}, где d — текущая точка, а i — её индекс в массиве всех точек. Функция доступа y должна затем вернуть числовое значение, обозначающее координату y данной точки. Функция доступа y также может быть определена как константа, а не как функция, если необходимо.

quadtree.extent([extent])

Если extent указан, устанавливает текущий объём и возвращает этот фабричный метод quadtree. Если extent не указан, возвращает текущий объём, который по умолчанию равен null. Когда объём равен null, объём будет вычислен автоматически путём сканирования массива входных точек, переданных в конструктор quadtree. В противном случае extent должен быть указан как двумерный массив [​[x0, y0], [​x1, y1]​], где x0 и y0 — нижние границы объёма, а x1 и y1 — верхние границы объёма. Установка объёма требуется при построении дерева поиска по частям из первоначально пустого набора узлов.