|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
26.11.2013, 10:40 | #1 |
Новичок
Джуниор
Регистрация: 26.11.2013
Сообщений: 3
|
написать программу для нахождения самого короткого пути от кординаты X1 Y1 до X2 Y2 если на пути встречается яма радиусом R
Нужно написать программу для нахождения самого короткого пути от кординаты X1 Y1 до X2 Y2 если на пути встречается яма радиусом R
|
26.11.2013, 12:56 | #2 |
Участник клуба
Регистрация: 05.11.2013
Сообщений: 1,601
|
Длина отрезка от x1, y1 до точки пересечения с окружностью + длина дуги + длина отрезка от точки пересечения с окружностью (с другой стороны) до точки x2,y2.
|
26.11.2013, 21:21 | #3 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,330
|
Так думаю, что координаты ямы радиуса R заданы.
Если таких данных нет, то вероятно, что центр ямы на линии между точками A и B. Следует рассмотреть вариант с касательными к окружности. Эти касательные проходят через заданные точки и касаются окружности в двух точках, пусть C и D. Кратчайшее расстояние - путь из A до C по прямой, далее из C к D по дуге окружности и затем из D к B по касательной. Доказательство: При построении чертежа будет видно, что если провести линию из A к B, то она пересечёт окружность в точках, пусть эти точки - Ca и Db. Точки A, Ca и C образуют треугольник, в котором сумма сторон ACa + CaC > AC. Но движение от Ca к C может быть только по дуге окружности, ... Как-то так, ... PS: Если известны координаты точки A, координаты центра окружности и ее радиус, вычислить координаты точки касания линии проведенной из т.A к окружности можно.
Как-то так, ...
|
26.11.2013, 22:03 | #4 |
Участник клуба
Регистрация: 05.11.2013
Сообщений: 1,601
|
Первая и третья длины находятся. В инете есть немало информации. Не смог найти длину дуги. Не пойму как найти центральный угол. И второе, можно пойти как по короткой дуге, так и по более длинной. Здесь тоже застрял.
|
27.11.2013, 19:54 | #5 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,330
|
Зная координаты точек C и D можно найти длину отрезка, соединяющего эти точки. Это хорда, размер которой выражается через стягиваемый угол и радиус окружности: Lhorda= 2*R*sin(alpha/2);
alpha = 2 * arcsin(Lhorda/(2*R); Но в Паскале нет такой функции, а есть arctan(). Поскольку угол в радианах, то длина дуги будет равна R*alpha(в радианах). Если определить доп. переменную, то можем записать: Код:
Как-то так, ...
Как-то так, ...
|
27.11.2013, 20:02 | #6 |
Участник клуба
Регистрация: 05.11.2013
Сообщений: 1,601
|
Во! Отлично. Про стягиваемый угол я не знал. Плюсик безусловный.
Задача решена. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
AI нахождения пути алгоритмом A*. | vovken1997 | Gamedev - cоздание игр: Unity, OpenGL, DirectX | 4 | 07.07.2012 19:17 |
Подпрограмма нахождения самого длинного простого пути от заданной вершины (язык Си) | Dmell | Помощь студентам | 1 | 02.05.2012 10:07 |
Поиск самого дешёвого пути. Волновой алгоритм | girlbuuuger | Помощь студентам | 16 | 13.02.2012 20:39 |
алгоритм нахождения пути | blacktener | Общие вопросы C/C++ | 3 | 03.04.2011 20:09 |
Некорректное определение короткого пути к директории | voam | Microsoft Office Excel | 7 | 12.12.2009 12:38 |