Алгоритм проверки попадания в неперекрывающиеся прямоугольники

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

  •  01-07-2019
  •  | 
  •  

Вопрос

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

Очевидный ответ заключается в том, чтобы иметь массив прямоугольников и выполнять поиск по ним последовательно, делая поиск 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 дерево для хранения прямоугольников.

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