Re: и вновь прога...

From

Viktor Karev (2:5080/1003)

To

Egor Tsygvintsev

Date

2002-11-19T10:39:49Z

Area

RU.ALGORITHMS

From: Viktor Karev <termar@narod.ru>
Reply-To: termar@narod.ru

Приветствия!

Egor Tsygvintsev wrote:

>   Дана карта местности, разбитая на участки разной проходимости, причем области
> разной проходимости это непересекающиеся многоугольники заданные своими
> вершинами. Необходимо проложить маршрут из точки А в точку В требующий
> минимального времени.

Наиболее подходящий для данной задачи метод - трасировки лучей.
Выпускаешь из начальной точки во всех направлениях лучи и
фиксируешь фронт фолны через dt. Если два луча пересеклись - из
точки пересечения выпускаешь один луч по среднему направлению.
Если слишком разошлись - добавляешь еще луч, чтобы плотность
лучей оставалась в некоторых пределах.

Виктор.
--- ifmail v.2.15dev5
 * Origin: USURT's FidoNET<->Internet Gate (news://news.c (2:5080/1003@fidonet)