Какой эффективный способ найти ближайший к локации прямоугольник без столкновения

Question

Для 2D-игры, над которой я работаю, я использую сортировку по оси Y в простом обнаружении столкновений на основе прямоугольника. Это работает нормально, и теперь я хочу найти ближайший пустой прямоугольник в заданном месте с заданным размером, эффективно. Как я могу это сделать? Есть ли алгоритм?

Я мог бы подумать о простом тесте методом грубой силы (с каждой сеткой размером с пустое пространство, которое мы ищем), но, очевидно, это медленный и даже не полный тест.

Answer 1

Подумайте об использовании четырех деревьев для хранения ваших прямоугольников.См. http://en.wikipedia.org/wiki/Quadtree для получения дополнительной информации.

Answer 2

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

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