|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Chernih 2:5049/151 07 Dec 2001 09:51:03
To : Andrei N. DUBIK
Subject : Hахождение кратчайшего расстояния по графику
--------------------------------------------------------------------------------
Hello Andrei!
06 Dec 01 18:02, Andrei N. DUBIK -> Andrey Chernih
>> Hужен алгоритм нахождения кратчайшего расстояния между двумя точками
>> (x1,x2,y1,y2) на графике. При условии наличия препятствия, круга
>> (x3,y3), который не должна пересекать эта траектория, с радиусом r.
AD> Может быть я неправильно понял вопрос, т.к. не представляю себе
AD> график с препятствием в виде круга (имхо, график - графическое
AD> представление функции). Hо если имеется ввиду карта (города,
AD> например),
Что-то типа карты. Две точки и окружность между ними. Точнее - задачка про винни
пуха и пятачка, вырывших ловушку между своими домиками :-)
AD> тот можно посоветовать составить топологию дорог в виде
AD> графа дорог. Т.е. повороты и перекрестки - вершины графа, сами дороги
AD> - его ребра. Имеется ввиду взвешенный граф. И тогда расстояние между
AD> двумя точками находится как кратчайшее расстояние между вершинами
AD> графа. Если искомые точки находятся не на вершинах графа, то можно
AD> попробовать методом наименьших квадратов вычислить ближайшую вершину.
Получается, нужно вычислить три расстояния - от одной точки до другой на дуге
окружности (ближайшее), от другой до дуги окружности (ближайшее) и расстояние
между двумя полученными точками (часть дуги окружности), потом все сплюсовать.
Получится наикратчайший путь. Собственно, как вычислять эти расстояния? Hужен
алгоритм.
Andrey
--- Мама Анархия, Папа стакан портвейна!
* Origin: Paradise Station (2:5049/151)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Hахождение кратчайшего расстояния по графику 