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

From

Vovanius Uryvaeff (2:5020/175.2)

To

Viktor Karev

Date

2002-11-19T17:33:57Z

Area

RU.ALGORITHMS

From: "Vovanius Uryvaeff" <micro-s@vniiofi.ru>

Tue Nov 19 2002 10:39, Viktor Karev wrote to Egor Tsygvintsev:

 >>   Дана карта местности, разбитая на участки разной проходимости, причем
 >> области  разной проходимости это непересекающиеся многоугольники заданные
 >> своими  вершинами. Необходимо проложить маршрут из точки А в точку В
 >> требующий  минимального времени.
 VK> Наиболее подходящий для данной задачи метод - трасировки лучей.
 VK> Выпускаешь из начальной точки во всех направлениях лучи и
 VK> фиксируешь фронт фолны через dt. 
dt можно посчитать как min(S/v) - где S- расстояние до ближайшего препятствия.
 VK> Если два луча пересеклись - из
 VK> точки пересечения выпускаешь один луч по среднему направлению.
Если они столкнулись - оба луча удалим.
 VK> Если слишком разошлись - добавляешь еще луч, чтобы плотность
 VK> лучей оставалась в некоторых пределах.

В прошлом своем письме я вроде начал эту мысль. Теперь продолжу:
Имеет смысл считать сразу весь фронт волны.
Вокруг точки, пока поблизости нет границ, фронт имеет форму окружности:
xx+yy=vt
Когда эта окружность коснется вершины, из вершины пойдет еще один круговой
фронт.
А фронт после преломления будет иметь вид, описываемый уравнениями
неизвестного порядка.

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

2ET: И вообще может считать расстояния как S=|x|+|y| ? Проще значительно
получится.
Задача для чего?

Send Email to vovanius2000<yxo>mail. ru

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)