обрый день.
есть след. задаза.
даны прямоугольники в произвольном порядке на экране. и есть 2 точки.
надо соединить эти 2 точки так чтоб линия соединяющая эти 2 точки не пересекала не один прямоугольник.
и путь этот должен быть кратчайшим
вот не как не могу придумать алгоритм.

помнится, была старая тема похожая: http://forum.vingrad.ru/topic-3781.html
честно говоря, не помню, чем там всё кончилось, но на всякий случай стоит почитать

Может подойти со стороны игрушек?
То есть сформулировать задачу так: найти кратчайший путь между двумя точками, где прямоугольники - препятствия.

А про алгоритмы поиска пути можна почитать тут


Это сообщение отредактировал(а) Kangaroo - 16.1.2008, 12:17

Я бы попробовал такое приближение.

Сначала условие - прямоугольники пересекать нельзя, но касаться их можно. Если и касаться нельзя - тогда на первом этапе увеличил бы каждый прямоугольник в каждую сторону на величину "запрещенного приближения к прямоугольнику" и дальше считал уже для новых прямоугольников. 

Дальше по такому алгоритму.

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

Подзадача: Проверить на то, пересекает ли прямая прямоугольник (пункт 3). 

• Можно просто проверять на пересечение ребра графа с каждой стороной прямоугольника, исключая сами вершины прямоугольника.
• Если для рассчета прямоугольники были увеличены, то можно еще проще - проверять на пересечение со сторонами исходных прямоугольников уже и углы не исключая.

Старый анекдот вспомнил. Когда водку стали продавать в бутылках по 0.8 встала задача  разлития 0.8 на троих. Ответ: разлить по 100 г и задача сводится к стандартной.  

Это сообщение отредактировал(а) _Y_ - 16.1.2008, 13:07

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

Да вы что, ребят... Задача просто сводится к волновому алгоритму. Просто между прямоугольниками надо построить еще прямоугольники, хранящие в себе уену прохода.

В примеру: По вертикали два прямоугольника на расстоянии Н. Вот тогда прямоугольник, по которому можно ходить будет размера (max(l1,l2), H). Это так, примерно.

Можно свести все прямоугольники к единичному размеру и просто обходить их- имхо это проще реализовать, чем пути по построенным доп. прямоугольникам

knut, ИМХО так. Если прямоугольников не слишком много - все должно работать быстро и приятно. Кстати - должно работать вообще с любыми многоугольниками.

 SoWa вот что-то совсем другое предлогает - может и лучше, но я совершенно не понял что именно.