Я создаю простую игру и придумываю эту проблему при разработке AI для моей игры: Учитывая набор из N точек внутри прямоугольника в декартовой координате, мне нужно найти самый широкий прямой путь через этот прямоугольник. Путь должен быть пустым (т.е. не содержать точки).
Интересно, есть ли какой-нибудь эффективный алгоритм для решения этой проблемы? Можете ли вы предложить какое-либо ключевое слово / статью / что-нибудь, связанное с этой проблемой?
РЕДАКТИРОВАТЬ: прямоугольник всегда определяется 4 точками в его углу. Я добавил изображение для иллюстрации. путь на рисунках выше определяется двумя красными линиями