Самолёт летит, летит...

[manu]

Добрый день.
Помогите решить прикладную задачку.
Есть самолёт (ЛА), координаты которого заданы стандартными градусами широты и долготы, а также высотой. 1 угловая минута равна 1 миле = 1800м. Будем рассматривать самолёт и точку в пределе квадрата со стороной = 1 миле, в этом случае можно принять землю плоской и работать в прямоугольном пространстве. Высоту зададим в диапазоне 0..5000м.
Вот в этой области есть точка m с известными координатами и произвольно расположеный относительно неё отрезок, заданный точками n и n-1 (текущая и предыдущая координата ЛА).
Нужно определить кратчайшее расстояние до точки, а именно, как близко самолёт пролетел от точки в этот период. Дальше программа будет оценивать это рсстояние и если оно, например, меньше 50м, то считаем точку пройденой.
То есть, в общем то, то же задача определения кратчайшего расстояния от отрезка до точки, но в реальном приложении.
Проблему усугубляет то, что относительное положение точки и отрезка произвольно и всякие геометрические построения вроде определения высоты треугольника не годятся... Да и работа уже идёт в пространстве. Считать это расстояние будет программа, по этому метод должен быть универсальный, выдающий одинаково верное решение не зависимо от относительного положения отрезка и точки. Считать будет восьмибитный микроконтроллер, 16 МГц частота ядра :) , так что хочется нечто попроще, почисленней.
Как проще провести рассчёт в данных условиях?

-- Сб апр 03, 2010 22:43:38 --

Stolen в сообщении #206062 писал(а):

vvvv писал(а):

Проще сделать так:

Ответ верный, но как получен непонятно.

Вот тут объяснено: http://algolist.manual.ru/maths/geom/di ... ntline.php

"И в двумерном и трехмерном случаях мы можем использовать векторное произведение для вычисления дистанции от точки P до прямой L, заданной точками P1 и P2.
Двумерный случай сводится к трехмерному подстановкой z=0.
Основное наблюдение, которое мы должны сделать - это заметить факт, что величина векторного произведения двух 3-мерных векторов равна площади параллелограма, построенного на них.
Однако эта площадь также равна произведению основания на высоту параллелограмма, а длина высоты - искомая дистанция d(P,L). "

-- Сб апр 03, 2010 22:45:39 --

Но это будет работать только если точка в пределах этого параллелограмма.

АКМ: отделено от post206139.html#p206139

[manu]

Ну а таки если вернуться к вопросу.
Вот есть вполне себе параллелограмм:

По определению, высотой параллелограмма, проведенной к данной его стороне, называется перпендикуляр, опущенный из произвольной точки противолежащей стороны к прямой, содержащей данную сторону.
Как высота будет выглядеть в данном случае?
Я предполагаю, что это будет линия между точками b и d, но она уже не является перпендикуляром... Будет ли площадь данного параллелограмма S=(ad)*(bd)?

[TOTAL]

manu в сообщении #309701 писал(а):

Я предполагаю, что это будет линия между точками b и d, но она уже не является перпендикуляром...

Проведите линию, которая ЯВЛЯЕТСЯ препендикуляром.

[manu]

Хорошо. Провёл.

Правильно ли я понимаю, что значение высоты h, как она проведена на рисунке, по прежнему может быть вычислена через векторное произведение:
$|ab*ad|/|ad|$?

[TOTAL]

manu в сообщении #310140 писал(а):

по прежнему может быть

Я не знаю, что было прежде.

[manu]

TOTAL в сообщении #310188 писал(а):

manu в сообщении #310140 писал(а):

по прежнему может быть

Я не знаю, что было прежде.

Дабы не утруждать Вас поиском, что, несомненно, очень тяжело, приведу цитату из первого сообщения темы:
"Основное наблюдение, которое мы должны сделать - это заметить факт, что величина векторного произведения двух 3-мерных векторов равна площади параллелограмма, построенного на них.
Однако эта площадь также равна произведению основания на высоту параллелограмма"
Там ещё и картинка с формулкой есть. Могу и её процитировать.

-- Пт апр 16, 2010 23:48:56 --

Попробую объяснить ещё раз и проще.
Изначально задача была определить кратчайшее расстояние, на котором ЛА пролетел от точки, т.к. координаты обновляются раз в секунду, а это порядка 30м пролёта. Задачу я решил, спасибо ссылочке http://algolist.manual.ru/maths/geom/di ... ntline.php , причём как и хотел - без тригонометрии, одними умножениями и сложениями.
Теперь задача немного иная (но, спасибо модератору, под название темы ещё и не то подходит).
Надо определить угол на точку и расстояние до неё. Смотрим на рисунок:

d - текущая координата, а - предыдущая координата. с - точка, куда надо попасть. Угол cde - искомый угол доворота.
Т.к. точки d, a, c заданы трёхмерными координатами (значение которых я могу перевести в систему Си), то длину вектора dc найти не проблема. Но чтобы получить угол cde нужно либо проекцией вычислить координату точки e и длину de, либо получить длину ce, равную (как я предполагаю) высоте параллелограмма abcd. Которую можно получить по формуле $|ad*dc|/|ad|$. Ну а дальше арксинус или арккосинус отношения сторон прямоугольного треугольника dce.
От сюда два вопроса:
1) будет ли ce равен высоте h параллелограмма?
2) Есть ли другой способ получения угла cde, без тригонометрических функций? Ибо с точки зрения ассемблера, лучше я сделаю сотню сложений и сдвигов, чем вычислю один арккосинус (кроме, разьве что, табличного метода, что не точно и громоздко в памяти).
Надеюсь, задачу обрисовал понятно.

[Maslov]

manu в сообщении #306150 писал(а):

1 угловая минута равна 1 миле = 1800м.

Это минута по широте равна 1852 м. А минута по долготе меняется от 1852 м на экваторе до 0 м на полюсе. И, как Вы понимаете, при расчете расстояния от точки до отрезка этот факт необходимо учитывать.

[manu]

Разумеется, но я пока не собираюсь летать до Америки через полюс. Меня интересуют полёты в радиусе 10-100км от места взлёта. На таких участках землю вообще можно считать плоской. На чём и игра - это позволяет использовать геометрию на плоскости, избавляясь от тригонометрии.

[Maslov]

manu в сообщении #310404 писал(а):

Разумеется, но я пока не собираюсь летать до Америки через полюс. Меня интересуют полёты в радиусе 10-100км от места взлёта. На таких участках землю вообще можно считать плоской.

До это-то ради бога. Но только Вы что-то писали по поводу того, что координаты заданы стандартными долготой и широтой. И по каким формулам Вы собираетесь считать в этом случае расстояние между точками с координатами $(\varphi_1, \lambda_1)$ и $(\varphi_2, \lambda_2)$?
По теореме Пифагора?

Это я всё к тому, что если Вы хотите работать в локальной прямоугольной системе координат с центром в месте взлёта $(\varphi_0, \lambda_0)$, то эти самые прямоугольные координаты надо вычислять как
$x = (\lambda - \lambda_0) \cos \varphi$
$y = \varphi - \varphi_0$

[AKM]

Я не очень вчитывался в полёт самолёта и в параллелограммы, но коли уж речь зашла об расстояниях на сфере --- припоминаю тему topic13182.html.
Сами, пардон, решите, интопик случился, или офф.

[manu]

Maslov в сообщении #310408 писал(а):

то эти самые прямоугольные координаты надо вычислять как

Опять тригонометрия. А зачем она нужна?
Я вижу задачу таким образом. Например, GPS приёмник выдаёт значение широты 55гр. 32,849'. и долготы 37гр. 29,098'.
Переводим в минуты и умножаем на 1000, чтобы получить целое число:
(55*60+32,849)*1000= 3332849. Долгота = 2249098. Знаки задаём согласно полушарию, пока примем везьде +.
Это и есть нулевые долгота и широта.
Пусть текущие координаты 3332851 и 2249100.
Вычитаем из текущих исходные, получаем по 2 минуты в каждую сторону. Зная значение минуты (в метрах) для широты и долготы данного региона и принимая в радиусе действия ЛА (100 км max) эти значения постоянными, что в общем то верно, получаем относительные координаты от точки взлёта 3704м в плоской прямоугольной системе координат района экватора (метры выбраны для увязки с третьей координатой - высотой - которая в метрах). Это уже вполне удобоваримые числа, которые умещаются в 16 бит и которые можно быстро считать. А если ещё обнулять систему координат каждую контрольную точку, то улететь можно очень далеко без переполнения переменных.
Вот и получается, что от тригонометрической геометрии в масштабе планеты мы ушли в аналитическую в масштабе плоского параллелепипеда со стороной основания 100км.
Вот в этом пипеде я и пытаюсь вычислять угол на следующую точку и расстояние до неё, желательно, убрав тригонометрию или снизив её наличие.

[Maslov]

manu в сообщении #310427 писал(а):

Зная значение минуты (в метрах) для широты и долготы данного региона и принимая в радиусе действия ЛА (100 км max) эти значения постоянными, что в общем то верно, получаем относительные координаты от точки взлёта 3704м в плоской прямоугольной системе координат района экватора

Ну значит мы говорим об одном и том же. Просто для данного региона "минута в метрах" по широте -- всегда $1852$ м, а по долготе -- $1852 \cdot \cos \varphi$, где $\varphi$ -- широта региона.

[manu]

А, ну если в этом плане, то да. Один раз вычислить косинус на старте я не против :)
А вот постоянно их считать - некошерно совсем...

[ewert]

manu в сообщении #310404 писал(а):

Меня интересуют полёты в радиусе 10-100км от места взлёта. На таких участках землю вообще можно считать плоской.

Это ещё как сказать. Сотня километров -- это порядка градуса, это довольно много. Т.е. плоской-то её с некоторой натяжкой ещё можно считать -- погрешность там порядка десятка метров. Но вот просто линеаризация сферических координат даст уже ошибку порядка процента.

Maslov в сообщении #310401 писал(а):

Это минута по широте равна 1852 м. А минута по долготе меняется от 1852 м на экваторе до 0 м на полюсе.

Тогда уж лучше 1850, ибо двойка довольно бессмысленна (она сильно плавает).