Задача поисковой оптимизации

Question

Предположим, у вас есть список 2D-точек с назначенной им ориентацией.Пусть множество S определено следующим образом:

S={ (x,y,a) | (x,y) is a 2D point, a is an orientation (an angle) }.

Для данного элемента s из S мы будем указывать с помощью s_p точечную часть, а с s_a - угловую часть.Я хотел бы знать, существует ли эффективная структура данных, такая, что, учитывая точку запроса q, способна вернуть все элементы s в S, такие что

(dist(q_p, s_p) < threshold_1) AND (angle_diff(q_a, s_a) < threshold_2)   (1)

где dist (p1, p2),с p1, p2 2D точки, это евклидово расстояние, а angle_diff (a1, a2), с углами a1, a2, это разница между углами (принимается за наименьший).Структура данных должна быть эффективной по вставке / удалению элементов и поиску, как определено выше.Число векторов может вырасти до 10.000 и более, но примите это с крошкой соли.

Теперь предположим, что изменим вышеуказанное требование: вместо использования условия (1), давайте запросим все элементыS такой, что при заданной функции расстояния d мы хотим, чтобы все элементы S были такими, что d (q, s) <порог.Если я хорошо помню, эта последняя настройка называется поиском по диапазону.Я не знаю, можно ли преобразовать первый случай во второй. </p>

Answer 1

Для поиска на расстоянии, я считаю, что принятым лучшим методом является дерево двоичных разделов пространства.Это может быть сохранено как серия битов.Каждые два бита (для 2D-дерева) или три бита (для 3D-дерева) делят пространство еще на один уровень, увеличивая разрешение.

Используя BSP, найти набор объектов для сравнения расстояний довольно просто,Просто найдите наименьший набор квадратов или кубов, которые содержат края вашего поля расстояния.

Что касается угла, я ничего не знаю.Я предполагаю, что вы можете хранить каждый объект во втором списке или в дереве, отсортированном по его углу.Затем вы найдете каждый объект на правильном расстоянии, используя BSP, каждый объект на правильных углах, используя дерево углов, а затем выполните пересечение набора.

Answer 2

Вы эффективно описали «трехмерное циклическое пространство», т.е. пространство, которое локально трехмерно, но где одно измерение топологически циклически. Другими словами, он локально плоский и может быть смоделирован как граница четырехмерного объекта C4 в (x, y, z, w), определяемая как

z^2 + w^2 = 1

где

a = arctan(w/z)

В этой модели пространство, определяемое вашими ограничениями, представляет собой 2-мерный цилиндр, обернутый «по длине» вокруг клина поперечного сечения, где клин оборачивается вокруг 4-го цилиндрического пространства с углом 2 * threshold_2. Это может быть смоделировано с использованием подхода «модифицированного дерева k-d» (модифицированного дерева 3d), где структура данных - это не дерево, а фактически граф (в нем есть циклы). Вы все еще можете разделить это пространство на ячейки с разделением гиперплоскости, но путешествие по кривой, определенной (z, w) в положительном направлении, может встретить точку, встреченную в отрицательном направлении. Дерево должно быть модифицировано так, чтобы фактически приводить к этим узлам с обоих направлений, чтобы ребра были двунаправленными (в направлении кривой z-w - остальные, очевидно, все еще однонаправлены).

Эти циклы не изменяют эффективность структуры данных при поиске соседних точек или разрешении поиска по ограничениям. Фактически, по большей части, эти алгоритмы модифицированы лишь незначительно (самый простой подход состоит в том, чтобы удерживать структуру данных посещенного узла, чтобы предотвратить циклы в поиске - вы проверяете следующих соседей, которые должны быть найдены).

Это будет работать особенно хорошо для ваших критериев, поскольку определяемый вами регион эффективно ограничен этими ограниченными осью гиперплоскостными ячейками дерева kd, и поэтому при поиске в результате регион в среднем останется заполненным вокруг pi / 4. процентов площади.