Предполагая, что линии не могут быть диагональными, вот один простой способ.Он основан на BFS и также найдет самую короткую линию, соединяющую точки:
Просто создайте график, содержащий одну вершину для каждой точки (x, y) и для каждой точки ребра:
((x,y),(x+1,y)) ((x,y),(x-1,y)) ((x,y),(x,y+1)) ((x,y),(x,y-1))
Но каждое из этих ребер должно присутствовать только в том случае, если оно не перекрывает прямоугольник.
Теперь просто сделайте простую BFS из точки (x1, y1) в (x2, y2)
Очень просто получить и диагональные линии таким же образом, но вам понадобится 8 ребер для каждой вершины, то есть, в дополнение к предыдущим 4:
((x,y),(x-1,y+1)) ((x,y),(x-1,y-1)) ((x,y),(x+1,y-1)) ((x,y),(x+1,y+1))
Тем не менее, каждое ребро должно присутствовать толькоесли он не перекрывает прямоугольник.
РЕДАКТИРОВАТЬ
Если вы не можете рассмотреть пространство, разделенное на сетку, вот еще одна возможность, но она не даст вам самый короткий путь, хотя.
Создайте граф, в котором каждый прямоугольник является вершиной и имеет ребро для любого другого прямоугольника, в который можно попасть без линии, перекрывающей третий прямоугольник.Теперь найдите кратчайший путь, используя dijkstra между box1 и box2, содержащий две точки.
Теперь рассмотрим каждую коробку с небольшим контуром, который не перекрывает любую другую коробку.Таким образом, вы можете связать точки входа и выхода каждой ячейки на пути, найденном через дижистру, проходящую через округ.