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

Question

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

Очевидный ответ - иметь массив прямоугольников и искать их последовательно, выполняя поиск O (n). Есть ли способ упорядочить их по позициям, чтобы алгоритм был меньше O (n), скажем, O (log n) или O (sqrt (n))?

Answer 1

Вы можете организовать свои прямоугольники в четырехугольном или kd-дереве. Это дает вам O (журнал N). Это основной метод.

Другой интересной структурой данных для этой проблемы являются R-деревья. Они могут быть очень эффективными, если вам приходится иметь дело с множеством прямоугольников.

http://en.wikipedia.org/wiki/R-tree

И затем есть метод O (1), который просто генерирует растровое изображение того же размера, что и ваш экран, заполняет его заполнителем для «no rectangle» и рисует индексы попадания в этот растровый рисунок. Поиск становится таким простым, как:

  int id = bitmap_getpixel (mouse.x, mouse.y)
  if (id != -1)
  {
    hit_rectange (id);
  }
  else
  {
    no_hit();
  }

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

Answer 2

Создание дерева интервалов. Запросите интервальное дерево. Обратитесь к «Алгоритмы» из прессы MIT.

Дерево интервалов лучше всего реализовывать как красно-черное дерево.

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

Вы должны иметь в виду, что вы строили свои индексы отдельно для разных осей. Например, вы должны увидеть, перекрываете ли вы интервал для X и Y. Одна из очевидных оптимизаций состоит в том, чтобы проверять только перекрытие в любом интервале X, а затем сразу проверять перекрытие в Y.

Кроме того, большинство деревьев интервалов акций или «учебников» проверяют только один интервал и возвращают только один интервал (но вы сказали, что «не перекрывается», не так ли?)

Answer 3

Используйте дерево BSP для хранения прямоугольников.

Answer 4

Запихните их в квадри .