Наименьшее расстояние до кеширования прямоугольника

Question

У меня есть список прямоугольников, которые не должны быть параллельны осям.У меня также есть главный прямоугольник, параллельный осям.
Мне нужен алгоритм, который может определить, какой прямоугольник является точкой, ближайшей к ней (точка должна находиться в главном прямоугольнике).список прямоугольников и мастер-прямоугольников не изменится во время алгоритма и будет вызываться со многими точками, поэтому необходимо создать некоторую структуру данных, чтобы ускорить поиск.
Чтобы быть понятным: расстояние от прямоугольника до точки являетсярасстояние между ближайшей точкой в ​​прямоугольнике и точкой.
Какой алгоритм / структуру данных можно использовать для этого?При этом память имеет более высокий приоритет, n log n в порядке, но n ^ 2 - нет.

Answer 1

Вы должны быть в состоянии сделать это за O (n) время и O (n) память.

1. Рассчитайте ближайшую точку на каждом ребре каждого прямоугольника к рассматриваемой точке. Для этого см. Мой подробный ответ в этом вопросе . Даже если вопрос касается точки внутри многоугольника (а не за ее пределами), алгоритм все еще может быть применен здесь.
2. Рассчитайте расстояние между каждой из этих ближайших точек по краям и найдите ближайшую точку на всем прямоугольнике (для каждого прямоугольника) к рассматриваемой точке. См. Ссылку выше для более подробной информации.
3. Найдите минимальное расстояние между всеми прямоугольниками. Прямоугольник, соответствующий вашему минимальному расстоянию, является победителем.

Answer 2

Вы должны быть в состоянии сделать это с диаграммой Вороного с O (n log n) временем предварительной обработки с O (log n) запросами времени.Поскольку объекты являются прямоугольниками, а не точками, ячейки могут быть изогнуты.Тем не менее, диаграмма Вороного должна хорошо работать в ваших целях.(См. http://en.wikipedia.org/wiki/Voronoi_diagram)

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

Answer 3

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

Это решение не требует дополнительной памяти, а время его выполнения составляет O (n).

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

Answer 4

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