Используя карту STL для поиска точек, лежащих в прямоугольной области?

Question

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

Одна логика, о которой я подумал, - это хранить все точки х в качестве ключей на карте А и все точки у в качестве ключей на другой карте В. Карта A будет иметь x в качестве ключа и y значения в качестве значения. Карта B будет иметь y в качестве ключа и связанную структуру в качестве значения.

Таким образом, если заданная точка (10.5,20.6), я могу использовать upper_bound (10.5 + RECTANGLE_WIDTH) и lower_bound (10.5-RECTANGLE_WIDTH), чтобы найти диапазон значений x, лежащих в прямоугольнике, и для соответствующих значений y найдите, находятся ли значения y в диапазоне + - 20,6.

Вся моя цель использования карты заключалась в том, что у меня огромное количество точек x, y, и поиск должен выполняться каждые две секунды. Поэтому мне пришлось использовать журнал (n) поиска карты. Я чувствую, что это можно сделать более эффективным способом. Предложения?

Answer 1

Это типичное приложение для quadtree . Дерево квадрантов облегчает поиск m точек, лежащих в вашем прямоугольнике, в O (log (n) + m), где n - общее количество точек.

Редактировать: Ваш подход с использованием карты не так эффективен. Для случайно распределенных точек он будет иметь среднюю сложность O (sqrt (n)) и худший случай O (n).

Answer 2

Первое наблюдение состояло бы в том, что std::map не будет самой эффективной структурой в любом случае. Ваш вклад в значительной степени исправлен, по-видимому (из комментариев). В этом случае std::binary_search на отсортированном std::vector является более эффективным. Основное преимущество std::map перед отсортированным std::vector заключается в том, что вставка - это O (log N) вместо O (N), и вам это не нужно.

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

Например, если ваши точки лежат случайным образом в плоскости XY между (0,0) и (200 300), можно было бы создать матрицу 20x30, в которой каждый будет содержать подрайон размером (10,10). Если вам теперь нужны точки в прямоугольнике от (64,23) до (78, 45), вам нужно проверить подрайоны [6,2], [6,3], [6,4], [7,2], [7,3] and [7,4] - только 6 из 600. На втором шаге вы должны выбросить такие результаты, как ( 61, 25).

Answer 3

Если вы используете std :: map точек, поиск всегда будет O (log N), где N - это количество точек, которое у вас есть.

Другой вариант - разделить пространство поиска на:ведра и положить свою точку в ведра.Затем вы вычисляете в своем прямоугольнике:

• любые сегменты, для которых все точки находятся внутри вашего прямоугольника
• любые сегменты, для которых есть некоторое перекрытие.

Для тех, у кого есть некоторое перекрытие, вы можете найти в своей коллекции значение O (M), если вы используете правильный тип коллекции для каждой корзины, но M должно быть меньше N. Может даже случиться, что M редко превышает несколько вв этом случае вы, вероятно, можете проверить их линейно.

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

Answer 4

Как насчет хранения точек в виде простого двумерного массива указателей на эти структуры, и когда вам нужно найти точку x, y, это простая операция с индексами.То же самое относится и к любым другим точкам (x + a, y + b).