|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vovanius Uryvaeff 2:5020/175.2 19 Nov 2002 18:33:57
To : Viktor Karev
Subject : Re: и вновь прога...
--------------------------------------------------------------------------------
Tue Nov 19 2002 10:39, Viktor Karev wrote to Egor Tsygvintsev:
>> Дана карта местности, разбитая на участки разной проходимости, причем
>> области разной проходимости это непересекающиеся многоугольники заданные
>> своими вершинами. Hеобходимо проложить маршрут из точки А в точку В
>> требующий минимального времени.
VK> Hаиболее подходящий для данной задачи метод - трасировки лучей.
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: и вновь прога... 
