Нахождение самого широкого пустого прямого пути через набор точек

Question

Я создаю простую игру и сталкиваюсь с этой проблемой при разработке AI для своей игры: Учитывая набор из N точек внутри прямоугольника в декартовой координате, мне нужно найти самый широкий прямой путь через этот прямоугольник. Путь должен быть пустым (т. Е. Не содержать никакой точки).

Интересно, есть ли эффективный алгоритм для решения этой проблемы? Можете ли вы предложить какое-либо ключевое слово / бумагу / что-нибудь, связанное с этой проблемой?

РЕДАКТИРОВАТЬ: прямоугольник всегда определяется 4 точками в его углу. Я добавил изображение для иллюстрации. Путь на рисунках выше определяется двумя красными линиями

Answer 1

Это самая широкая проблема пустого коридора. Хоул и Масиэль дали алгоритм O (n ² ) - времени, O (n) -пространства в техническом отчете 1988 года, озаглавленном «Нахождение самого широкого пустого коридора через набор точек», который, похоже, не является доступно онлайн. К счастью, Джанардан и Препарата описывают этот алгоритм в Разделе 4 своей статьи Проблемы самого широкого коридора , которая доступна.

Answer 2

Переберите все пары точек. Построить линию l через пару. (^ 1) На каждой стороне l либо есть другие точки, либо нет. Если нет, то на этой стороне пути l нет пути. Если есть другие точки, выполните обход точек, вычисляя перпендикулярное расстояние d от l до каждой такой точки. Запишите минимум d . Это самый широкий путь на этой стороне l . Продолжите цикл по всем парам, сравнивая самый широкий путь для этой пары с предыдущим самым широким путем.

Этот алгоритм можно считать наивным и работает за O(n^3) время.

Редактировать: Приведенный выше алгоритм пропускает регистр. В пункте ^ 1 выше вставить: «Постройте две линии, перпендикулярные l через каждую точку пары. Если между линиями нет третьей точки, запишите расстояние d между точками Это путь. " Продолжите алгоритм на ^ 1. В дополнительном случае алгоритм по-прежнему O(n^3)

Answer 3

Сам я бы начал с рассмотрения триангуляции Делоне для набора точек: http://en.wikipedia.org/wiki/Delaunay_triangulation

Похоже, что существует множество ресурсов по эффективным алгоритмам для построения этого - алгоритм Fortune, в O (nlog n), для начала.

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

РЕДАКТИРОВАТЬ 1: моя интуиция подводит меня!Простой равносторонний треугольник является контрпримером: самый широкий путь короче любого из ребер в триангуляции.Все еще размышляя ...

РЕДАКТИРОВАТЬ 2: Итак, нам нужен алгоритм черного ящика, который, учитывая две точки в наборе, находит самый широкий путь через множество точек, ограниченный этими двумя точками.(Визуализируйте две параллельные линии, проходящие через две точки; вращайте их в гармонии друг с другом, пока между ними нет точек).Давайте назовем время выполнения этого алгоритма «R».

Учитывая такой алгоритм, мы можем сделать следующее:

1. Построить триангуляцию Делоне из набора точек: O (n logn)
2. Сортировка ребер по ширине: O (n log n)
3. Начиная с наибольшего ребра и спускаясь вниз, используйте алгоритм черного ящика, чтобы определить самый широкий путь, включающий эти две точки;сохраняя его как X: O (nR))
4. Остановитесь, когда исследуемый край короче ширины X.

Шаги 1 и 2 хороши, но O (nR) это немного страшно.Если R оказывается O (n), это уже O (n ^ 2) для всего алгоритма.Приятно то, что для общего набора случайных точек мы ожидаем, что нам не придется проходить все грани.