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

StackOverflow https://stackoverflow.com/questions/303243

Вопрос

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

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

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

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

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

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

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

Update

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

Это было полезно?

Решение

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

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

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

Другие советы

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

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

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

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

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

<Ол> Узел
  • находится за пределами целевого прямоугольника: игнорировать
  • узел находится внутри целевого прямоугольника: включить все точки внутри узла
    • Узел
  • частично находится за пределами прямоугольника: выполните проверку границ точек внутри узла

    • По ссылке Ювала Ф. я обнаружил Поиск диапазона Это именно то, что вы ищете. Я перешел по некоторым ссылкам оттуда и нашел CGAL , библиотеку C ++ с открытым исходным кодом, которая реализует поиск по диапазону, с примерами здесь . . р>

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

    Лицензировано под: CC-BY-SA с атрибуция
    Не связан с StackOverflow
    scroll top