Форум программистов, компьютерный форум, киберфорум
Наши страницы
letete
Войти
Регистрация
Восстановить пароль
Несколько сообщений о МАТЛАБ и о том, как им пользоваться.

Комментарии, критика и восторженное рукоплескание приветствуются в самой категоричной форме.
Оценить эту запись

Пересечение окружностей

Запись от letete размещена 29.01.2018 в 19:00

Понадобилось тут намедни пересечь окружности (на плоскости, понятное дело) и потратив изрядное количество времени на поиски готового решения в интернетах, я оказался несколько обескуражен. В большинстве случаев предлагается решение школьных задачек с конкретными данными, либо разбор полета начинается со слов "Для простоты предположим, что центр первой окружности совпадает с началом координат...". Такое предположение конечно можно сделать, и даже сместить систему координат не так уж и сложно, но это до тех пор пока окружности две и пока мы на плоскости. С усложнением задачи становится сложнее двигать и поворачивать систему координат, что меня лично не очень-то радует.
По сему я решил, что было бы весьма недурственно посчитать задачу в общем виде. Может, кому и пригодится.

Итак, две окружности:
http://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}<br />
(x-a_1)^2 + (y-b_1)^2=r_1^2\\ <br />
(x-a_2)^2 + (y-b_2)^2=r_2^2<br />
\end{matrix}\right.
После раскрытия скобок, получим:
http://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}<br />
x^2+a_1^2-2a_1x + y^2+b_1^2-2b_1y=r_1^2\\ <br />
x^2+a_2^2-2a_2x + y^2+b_2^2-2b_2y=r_2^2<br />
\end{matrix}\right.
Вычитаем второе из первого и причесываем (вводим сразу для упрощения http://www.cyberforum.ru/cgi-bin/latex.cgi?\alpha и http://www.cyberforum.ru/cgi-bin/latex.cgi?\delta):
http://www.cyberforum.ru/cgi-bin/latex.cgi?a_1^2 - a_2^2 - 2a_1x + 2a_2x + b_1^2 - b_2^2 - 2b_1y +2b_2y = r_1^2 - r_2^2<br />
x(2a_2-2a_1) + y(2b_2-2b_1) = r_1^2-r_2^2-a_1^2+a_2^2-b_1^2+b_2^2<br />
y = \frac{r_1^2-r_2^2-a_1^2+a_2^2-b_1^2+b_2^2}{2(b_2-b_1)} - x\frac{a_2-a_1}{b_2-b_1} = \delta - \alpha x
По сути http://www.cyberforum.ru/cgi-bin/latex.cgi?y = \delta - \alpha x - это уравнение линии пересечения окружностей (имеется ввиду прямой, содержащей точки пересечения), кроме того достаточно очевидно, что http://www.cyberforum.ru/cgi-bin/latex.cgi?1/\alpha - коэффициент наклона прямой, содержащей центры окружностей (естественно, ведь эти прямые перпендикулярны).
Возможно, стоит оговорить отдельно случай, когда http://www.cyberforum.ru/cgi-bin/latex.cgi?b_1 = b_2 (вертикальная прямая), но я искренне не верю что такой случай может произойти в моей задаче, а потому специально не рассматриваю (если потребуется - сделаю правку).
Теперь можно подставить соотношение в любое из исходных уравнений:
http://www.cyberforum.ru/cgi-bin/latex.cgi?(x-a_1)^2 + (\delta - \alpha x - b_1)^2 = r_1^2
Раскрываем скобки, группируем и введем привычные http://www.cyberforum.ru/cgi-bin/latex.cgi?a, http://www.cyberforum.ru/cgi-bin/latex.cgi?b и http://www.cyberforum.ru/cgi-bin/latex.cgi?c:
http://www.cyberforum.ru/cgi-bin/latex.cgi?x^2+a_1^2-2a_1x + (\delta - b_1)^2 + \alpha ^2x^2 - 2\alpha (\delta - b_1)x = r_1^2<br />
x^2(1+\alpha ^2) - 2x(a_1 + \alpha (\delta - b_1)) + (a_1^2 + (\delta - b_1)^2 - r_1^2) = 0<br />
\begin{matrix}<br />
ax^2 -2bx + c = 0, & [a = 1+\alpha ^2, & b = a_1 + \alpha (\delta - b_1), & c = a_1^2 + (\delta - b_1)^2 - r_1^2]<br />
\end{matrix}
Дальше все слишком просто - четверть дискриминанта и получение корней:
http://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{matrix}<br />
D/4 = b^2 - ac \Rightarrow  & x_{1,2} = \frac{+b\pm\sqrt{D/4}}{a}\\ <br />
 & y_{1,2} = \delta - \alpha x_{1,2}<br />
\end{matrix}

Ну и напоследок запишем это все на C++ (Qt) с учетом погрешностей:
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
QList<QPointF> circleIntersection(double x1, double y1, double r1,
                                  double x2, double y2, double r2, float tolerance) {
    // пустой список результирующих точек
    QList<QPointF> res;                 
 
    // расстояние между центрами
    double d = qSqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
    if (d < tolerance) {                // для совпадающих центров либо пересечений нет,
        if (qAbs(r1-r2) < tolerance)    // либо их бесконечно много - тогда возвращены
            return res;                 // будут три пустые точки
        else return (res << QPointF() << QPointF() << QPointF());
        }
    // случай когда точек пересечения нет (при разных центрах) - возвращаем пустой список
    if (d - tolerance > r1+r2 || d + tolerance < qAbs(r1-r2)) return res;
 
    double alpha = (x2-x1)/(y2-y1);
    double delta = 0.5*(r1*r1 - r2*r2 - x1*x1 + x2*x2 - y1*y1 + y2*y2)/(y2-y1);
 
    double a = 1 + alpha*alpha;
    double b = x1 + alpha*(delta - y1);
    double c = x1*x1 + (delta - y1)*(delta - y1) - r1*r1;
 
    double d_4 = b*b - a*c;
    //if (d_4 < 0) return res;            
    
    // случай с одной точкой пересечения (касания)
    if (d_4 < tolerance*tolerance) return (res << QPointF(b/a, delta - alpha*b/a));
 
    double xx1 = (b + qSqrt(d_4))/a;
    double xx2 = (b - qSqrt(d_4))/a;
 
    return (res << QPointF(xx1, delta - alpha*xx1) << QPointF(xx2, delta - alpha*xx2));
}
Небольшой комментарий:
- предварительная проверка нужна для того, чтобы не производить лишние вычисления, а также чтобы учитывать погрешность измерений; по идее достаточно проверки на неотрицательность дискриминанта при точном расчете, но поскольку предварительную проверку я все же сделал - дискриминант не должен получаться отрицательным (при условии, конечно, что значение погрешности tolerance адекватное), либо может быть отрицательным, но не очень большим по модулю - это будет соответствовать случаю касания.
- строку 24 заблокировал по следующей причине: получается, что когда окружности рядом, почти касаются, алгоритм дает отрицательный дискриминант, но в силу погрешности мне все же надо считать что точка пересечения есть (с уверенностью утверждать, что дискриминант "не сильно" отрицательный меня заставляет предварительная проверка)
- в случае с касанием (строка 27) мне так было сделать удобнее, хотя это несколько не правильно (еще более не правильно сравнивать без извлечения корня - размерности разные, d_4 < tolerance*tolerance то же самое, что qSqrt(d_4) < tolerance, но без извлечения корня из возможно отрицательного числа); в этом месте лучше сделать так, как того требует конкретная задача
Размещено в Qt
Просмотров 344 Комментарии 0
Всего комментариев 0
Комментарии
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru