|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Polubasoff 2:5020/400 08 Nov 2001 18:32:50
To : All
Subject : [* - гео] - середина дуги
--------------------------------------------------------------------------------
Hi All!
Прошу прощения, что внезапно исчез. Друг защитил докторскую, так что
некоторое время я не был способен писать что-либо серьёзное. :)
Hа случай, если у кого-нибудь ещё остался интерес к этой теме, напоминаю
условие и привожу некоторые решения.
Дано: Центр окружности C, точки начала и конца дуги A и B.
Можно считать, что С = (0,0).
Дуга от A до B подразумевается против часовой стрелки.
Hайти: Середину дуги.
Сразу скажу, подвох в том, что координаты точек даются не абсолютно
точно, а с погрешностью. Пусть координаты округлены до целых.
Hапример, точки (100.2, 10) и (100, 12)
могут быть даны как A = (100, 10) и B = (100, 12),
а точки (100.4999, -0.2) и (100.5001, 0) -
как A = (100, 0) и B = (101, 0).
Можно считать, что A и B расположены достаточно далеко от C.
При любых данных нужно бы выдать правдоподобный результат.
Линейного решения (без ветвлений) быть не может, так как функция
разрывна, когда угол ACB равен 0. Будем считать, что величина дуги строго
меньше 360 градусов, то есть разрешать неоднозначность в пользу 0.
--------------------------------
Решение 1 (Виталий Мусихин). Геометрическое. Лично мне нравится.
if (Xa*Xb+Ya*Yb <= 0) // если cos(ACB) <= 0
{ // т.е. 90 <= ACB <= 270
Xd = Yb-Ya; // CD = (AB, повёрнутый на 90)
Yd = Xa-Xb;
}
else if (Xa*Yb-Xb*Ya >= 0) // если sin(ACB) >= 0
{ // т.е. 0 <= ACB < 90
Xd = Xa+Xb; // CD = CA+CB
Yd = Ya+Yb;
}
else // если sin(ACB) < 0
{ // т.е. 270 < ACB < 360
Xd = -Xa-Xb; // CD = -(CA+CB)
Yd = -Ya-Yb;
}
// коэффициент нормирования 0.5 <= k <= 0.7
k = sqrt((Xa*Xa+Ya*Ya+Xb*Xb+Yb*Yb)/(2*(Xd*Xd+Yd*Yd)));
Xd *= k; // нормировать результат
Yd *= k;
В этом решении нет потери точности.
Есть один корень, одно деление и две (полторы) проверки.
--------------------------------
Решение 2 (Yurij Zabelyshynskij). Тригонометрическое.
|x| = 0.5*sqrt((x1+x2)^2 + (y1-y2)^2);
|y| = 0.5*sqrt((x1-x2)^2 + (y1+y2)^2);
Очень интересные формулы. Совсем нет делений. Если потребуется, это даже
можно посчитать в целых числах. Ответ будет верным, даже если A, B и С
совпадут.
Правда, есть два корня и сколько-то проверок. Сколько точно, я не понял, даю
слово самому Юрию:
YZ> заметим, что даже радиус считать не надо. Погрешность, очевидно, не
YZ> растет, вылета ни при каких данных не будет. Осталось только выбрать
YZ> знаки, т.е. координатную четверть. Сначала считаем знак синуса t1+t2
YZ> (он равен знаку x1y2+x2y1); зная, в верхней или нижней полуплоскости
YZ> t1+t2 , узнаем четверть (t1+t2)/2 с точностью до диагонали (т.е. знак
YZ> тангенса). А дальше считаем ориентацию тр-ка AХB (Х - искомая) она
YZ> должна быть неотрицательной. Если 0, то X=A=B.
--------------------------------
Решение 3 (Serge Kanilo).
if (abs(Ax-Bx) > abs(Ay-By))
{
y = (Ax-Bx) * sqrt((Ax*Ax+Ay*Ay+Bx*Bx+By*By)/(2*abs(Ax-Bx));
x = (Ax*Ax-Bx*Bx+Ay*Ay-By*By-2*y*(Ay -By))/(2*(Ax-Bx));
}
else
{
x = (Ay-By) * sqrt((Ax*Ax+Ay*Ay+Bx*Bx+By*By)/(2*abs(Ay-By));
y = (Ax*Ax-Bx*Bx+Ay*Ay-By*By-2*x*(Ax -Bx))/(2*(Ay-By));
}
Увы, при A близком к B вместо результата получаем лажу.
--------------------------------
Решение 4 (Serg Belyaev). Комплексно-алгебраическое (z=sqrt(z1*z2)).
SB>> x2:=Bx-Cx;x1:=Ax-Cx;
SB>> y2:=By-Cy;y1:=Ay-Cy;
SB>> a:=x1*x1+y1*y1;b:=x1*x2-y1*y2;
SB>> x:=sqrt((a+b)/2);
SB>> y:=sqrt((a-b)/2);
if (x1*y2+x2*y1)<=0 then y:=-y;
if <???> then begin x:=-x;y:=-y end;
x:=x+Cx;y:=y+Cy;
Программа вылетает по взятию корня из отрицательного числа.
--------------------------------
Решение 5 (Serg Belyaev). Комплексно-алгебраическое (z=z1*sqrt(z2/z1)).
x2:=Bx-Cx;x1:=Ax-Cx;
y2:=By-Cy;y1:=Ay-Cy;
a:=(x1*x2+y1*y2)/(x1*x1+y1*y1);
x:=sqrt((1+a)/2);y:=sqrt((1-a)/2);
if (x1*y2-x2*y1)=0 then begin
writeln('Точки совпадают - решения нет');exit
end else
if (x1*y2-x2*y1)<0 then x:=-x;
x2:=x1*x-y1*y+Cx;y2:=x1*y+y1*x+Cy;
Программа вылетает по взятию корня из отрицательного числа.
С уважением, Олег Полубасов.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
