Проверьте, насколько эффективна точка, расположенная внутри прямоугольника, выровненного по оси, включая край?

Question

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

Из-за ограничения библиотеки я, необходимой для использования, реализации этого уже стало весьма ресурсоемким:

1. На начальной мыши, сохранить положение курсора мыши.

2. На каждом пикселе, что мыши курсор перемещается, выполните следующие действия:

   1. Destroy предыдущий прямоугольник выбора, если она существует, поэтому он не появляется на экране больше.

   2. Рассчитайте ширину и высоту нового набора, используя текущую позицию курсора и текущую позицию курсора.

   3. Создайте новый прямоугольник выделения, используя исходное положение курсора, ширину и высоту

   4. Показать этот прямоугольник на экране

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

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

Каждый объект, который можно выбрать, может быть представлен одной точкой, P (x, y).

Как проверить, находится ли P (x, y) внутри прямоугольников, я создаю самым быстрым/наиболее эффективным способом?

Вот соответствующая информация:

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

Как я могу достичь того, что мне нужно сделать как можно быстрее?

Answer 1

Проверка, находится ли точка P внутри прямоугольника R является простым и быстрым
(в системе координат с началом в верхнем левом углу)

(P.X >= R.Left) and (P.X <= R.Right) and (P.Y >= R.Top) and (P.Y <= R.Bottom) 

(предвычислять правая и нижняя координаты прямоугольника)

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

Пример: сортировать список объектов по координате Х и проверять только те объекты, которые лежат в диапазоне Left..Right

Более продвинутый подход: организовать объекты в некоторой структуре данных пространственно-секционирования как kd-tree и выполнить поиск по диапазону очень быстро

Answer 2

Вы можете перебирать каждый объект на экране и проверьте, находится ли она в прямоугольнике в декартовой системе координат, используя следующее условие:

p.x >= rect.left && p.x <= rect.right && p.y <= rect.top && p.y >= rect.bottom 

Если собираешься нет более 1000 точек на экране, просто используйте наивный метод O(n), итерируя каждую точку. Если вы полностью уверены, что вам нужно оптимизировать это дальше, читайте дальше.

В зависимости от частоты обновления точек и количества точек, обновляемых каждым фреймом, вы можете использовать другой метод, потенциально связанный с структурой данных, такой как Range Trees, или установить для наивного метода O(n).

• Если точки не будет двигаться вокруг много и редкие (т.е. далеко друг от друга), вы можете использовать Range Tree или аналогичный для O(log n) проверок. Имейте в виду, что обновление такой структуры пространственного разбиения является ресурсоемкой, и если у вас будет много точек, которые будут перемещаться совсем немного, вам может понадобиться посмотреть на что-то еще.

• Если через несколько точек будут передвигаться на большие расстояния, вы можете захотеть взглянуть на разбиении экрана в сетку «ведра», и проверять только те ведра, которые содержатся в прямоугольнике. Всякий раз, когда точка перемещается из одного ведра в другой, сетка должна обновлять поврежденные ведра.

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

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