Как я могу нарисовать прямой маршрут между двумя точками и избежать препятствий?

Question

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

Answer 1

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

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

См .: https://en.wikipedia.org/wiki/A*_search_algorithm

Answer 2

Просто идея:

1. Нарисуйте прямую линию в качестве первого отрезка.
2. Проверьте, попадает ли какой-либо отрезок в прямоугольник.(Если нет, значит, все готово.)
3. Если это так, замените отрезок линии двумя отрезками, которые идут ближе к двум углам прямоугольника, что означает обход вокруг него.
4. Повторите с шагом 2.

Здесь вы можете увидеть три итерации (красный → зеленый → синий) этого процесса.

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

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