Хранить 2D точки для быстрого поиска точек внутри прямоугольника

Question

У меня есть большое количество 2D точек, и я хочу быстро получить те, которые лежат в определенном прямоугольнике. Давайте скажем «.» это любая точка, а «X» - это точка, которую я хочу найти внутри прямоугольника, в котором «T» обозначает TopLeft, а «B» - BottomRight:

. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .

Я попробовал std :: set с функтором сортировки, который сортирует точку TopLeft в начале и BottomRight в конце набора. Если сначала выполнить сортировку по значению X, это приведет к обнаружению следующих точек.

. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .

Это означает, что мне придется проверять каждую найденную точку, действительно ли она находится внутри прямоугольника. Не очень хорошо.

Что может быть лучше для этого?

Мой язык - C ++ (Windows), и у меня есть STL и усиление.

Обновление

Прочитав ответы до сих пор, я заметил, что не учел все параметры своей задачи: нет ни одного фиксированного прямоугольника. Прямоугольники могут быть установлены пользователем во время выполнения. Это означает, что сортировка набора точек обещает быть более эффективной, чем линейный поиск по всем точкам, как было предложено Артелием до этого обновления. Я все еще попробую, хотя! Я не ожидаю, что пользователь установит прямоугольник очень часто. Что касается усилий по внедрению, это может оказаться хорошим решением для меня.

Answer 1

Вы можете хранить точки в пространственном индексе, используя четырехугольные или r-деревья. Затем, учитывая прямоугольник, вы можете найти все узлы дерева, которые перекрывают его, вам нужно будет сравнить каждую точку в этом подмножестве, чтобы увидеть, попадает ли она в прямоугольник.

По сути, пространственное дерево помогает вам обрезать пространство поиска.

Возможно, вы сможете использовать более простое решение, такое как разбиение точек на диапазоны. Скажите, где х от 0,10 в качестве одного диапазона, 11,20 в качестве другого. Поможет любое решение, позволяющее сократить пространство поиска.

Answer 2

Пожалуйста, посмотрите этот вопрос . Репозиторий алгоритма Stony Brook имеет несколько реализаций KDTrees в C ++, хотя они не являются ни частью STL, ни Boost.

Answer 3

Сортировка массива занимает O ( n log n ) времени. Простая проверка каждой точки отдельно (без сортировки) занимает время O ( n ).

Ergo, просто пройти и проверить каждую точку на быстрее , чем сортировка. И это тоже быстрее, чем строить квадри.

РЕДАКТИРОВАТЬ: Если у вас есть много прямоугольников, чтобы проверить, это другая история. Но если вам нужно проверить только небольшое количество фиксированных прямоугольников, просто сделайте это «очевидным» способом!

Answer 4

По ссылке Yuval F я нашел Range Search , который, кажется, является именно тем, что вы ищете. Я перешел по некоторым ссылкам оттуда и обнаружил CGAL , библиотеку C ++ с открытым исходным кодом, которая реализует поиск по диапазону, с примерами здесь .

Answer 5

используйте quadtree, и у вас есть 3 типа узлов qtree:

1. узел находится за пределами целевого прямоугольника: игнорировать
2. узел находится внутри целевого прямоугольника: включить все точки внутри узла
3. узел частично находится за пределами прямоугольника: выполните проверку границ точек внутри узла

Answer 6

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