Алгоритм проверки попадания в неперекрывающиеся прямоугольники
Вопрос
У меня есть коллекция неперекрывающихся прямоугольников, которые закрывают окружающий прямоугольник.Каков наилучший способ найти содержащий прямоугольник для щелчка мыши?
Очевидный ответ заключается в том, чтобы иметь массив прямоугольников и выполнять поиск по ним последовательно, делая поиск O (n).Есть ли какой-нибудь способ упорядочить их по позиции, чтобы алгоритм был меньше O (n), скажем, O (log n) или O (sqrt (n))?
Решение
Вы можете упорядочить свои прямоугольники в виде квадрата или kd-дерева.Это дает вам O (log n).Это общепринятый метод.
Другой интересной структурой данных для этой задачи являются R-деревья.Это может быть очень эффективно, если вам приходится иметь дело с большим количеством прямоугольников.
http://en.wikipedia.org/wiki/R-tree
И тогда есть метод O (1), позволяющий просто сгенерировать растровое изображение того же размера, что и ваш экран, заполнить его заменителем для "без прямоугольника" и нарисовать индексы попадания в прямоугольник в этом растровом изображении.Поиск становится таким же простым, как:
int id = bitmap_getpixel (mouse.x, mouse.y)
if (id != -1)
{
hit_rectange (id);
}
else
{
no_hit();
}
Очевидно, что этот метод хорошо работает только в том случае, если ваши прямоугольники меняются не так часто и если вы можете выделить память для растрового изображения.
Другие советы
Создайте дерево интервалов.Запросите дерево Интервалов.Обратитесь к "Алгоритмам" из MIT press.
Интервальное дерево лучше всего реализовать в виде красно-черного дерева.
Имейте в виду, что сортировать прямоугольники рекомендуется только в том случае, если вы собираетесь чаще нажимать на них, чем обычно меняете их положение.
Вам нужно будет иметь в виду, что вы должны создавать свои индексы для разных осей отдельно.Например, вы должны посмотреть, перекрываете ли вы интервал на X и на Y.Одна из очевидных оптимизаций заключается в проверке перекрытия только на любом интервале X, затем немедленно проверьте перекрытие на Y.
Кроме того, большинство деревьев интервалов stock или 'classbook' проверяют только один интервал и возвращают только один интервал (но вы сказали "неперекрывающийся", не так ли?)
Засуньте их в квадратное дерево.
Используйте BSP дерево для хранения прямоугольников.