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