Точки пересечения двух окружностей

← →
Димитрий © (2005-07-23 16:19) [0]

Подскажите быстрый алгоритм нахождения сабжа. Известны координаты и радиусы: (X1, Y1, R1), (X2, Y2, R2)

← →
Димитрий © (2005-07-23 16:21) [1]

X1, Y1; X2, Y2 - это координаты их центров, конечно

← →
jack128 © (2005-07-23 16:47) [2]

не думаю, что существует способ, быстрее чем решить пару квадратных уравнений.

(x-x1)^2 + (y-y1)^2 = R1^2
(x-x2)^2 + (y-y2)^2 = R2^2

← →
MBo © (2005-07-23 18:17) [3]

Можно побыстрее - либо аффинно преобразовать координаты так, чтобы центр одной окружности был в 0, второй на оси OX, тогда решение сильно упрощается, либо рассчитать параметрические координаты точек пересечения с использованием базисных векторов С1С2 и перпендикуляра к нему.

← →
Магнитон Борыч (2005-07-23 18:48) [4]

> MBo © (23.07.05 18:17) [3]
> Можно побыстрее - либо аффинно преобразовать координаты так, чтобы центр одной окружности был в 0, второй на оси OX,

Это как?

← →
jack128 © (2005-07-23 18:50) [5]

MBo © (23.07.05 18:17) [3]
преобразовать координаты так, чтобы центр одной окружности был в 0, второй на оси OX,

что мне кажется что подобное преобразование будет весьма медленным? там всякие синусы вылезут наверника

← →
jack128 © (2005-07-23 18:54) [6]

Магнитон Борыч (23.07.05 18:48) [4]
Это как?
стандартный прием в математике - сместить центр координат и повернуть оси на определенный угол, за счет этого можно получить значительно более простую, чем исходная, задачу.. ну после решения естественно нужно вернуться к исходной системе координат..

← →
TButton © (2005-07-23 19:27) [7]

кажисть был у меня код
бо надо было как-то...
вопсчем я по смотрю, бо
дневники поднимать надо

← →
Димитрий © (2005-07-23 19:57) [8]

> TButton © (23.07.05 19:27) [7]

Буду очень признателен

← →
Shuric © (2005-07-23 20:13) [9]

Прикольный:
Две канвы с окружностями, наложение с флагом, поиск точки по цвету:)

← →
Alx2 © (2005-07-23 21:02) [10]

>Димитрий © (23.07.05 16:19)

Можно решать в лоб систему [2].

Но кажется, проще представить точки пересечения вершинами треугольника со сторонами r1 и r2 и основанием L, где L - расстояние между центрами.

Вот что получилось (насчет быстроты вычислений не уверен):

procedure IntersectPoint(x1, y1, r1, x2, y2, r2: Double; var xa, ya, xb, yb: Double); var L, t, xc, yc, vt: Double; begin L := sqr(x1 - x2) + sqr(y1 - y2); vt := sqr(r1 + r2); if L <= vt then begin xc := 1 / (2 * l); t := (l - sqr(r2) + sqr(r1)) * xc; l := sqrt((vt - l) * (l - sqr(r1 - r2))) * xc; xc := (x2 - x1) * t + x1; yc := (y2 - y1) * t + y1; t := (y2 - y1) * l; xa := xc + t; xb := xc - t; t := (x1 - x2) * l; ya := yc + t; yb := yc - t; end else raise Exception.Create("Нет решения"); end;

бэмс
нашёл в дневнике
(готовилось для обхождения круглого препятствия)

// структура описывающая окружность TCircle = record x, y, r: real; end; // собсна, две окружности c1, c2: TCircle // калькуляем расстояние м-у центрами // (Dist возвращает расстояние вычисленое по Пифагору) dbc:=Dist(c1.x, c1.y, c2.x, c2.y); // тут нужно небольшое пояснение // дело в том, что код в дневнике сопровождается // рисунками. на одном из рисунков изображены // две пересекающиеся окружности // между точками их пересечения проведена прямая // также проведена прямая между центрами окружностей // (прямые взаимоперпендикулярны) // d1 - расстояние от центра первой окружности // до точки пересечения линии соединяющей центры // и линии соединяющей точки пересечения окр-стей // d2 - аналогично для второй окружности d1:=dbc*c1.r/(c1.r+c2.r); d2:=dbc*c2.r/(c1.r+c2.r); // a1 - угол между линией проходящей от центра // первой окружности к центру второй окружности и линией, // проходящей от центра первой окружности к точке пересечения. // треугольник, который образует центр окружности и две точки // пересечения равнобедренный. // линия, проходящая между центрами окружностей // делит этот равнобедренный треугольник // на два равных прямоугольных треугольника. a1:=acos(d1/c1.r);

дальше идёт спецефический код к твоему дела никакого отношения не имеющий =)

для тебя пишу новый код

a:=Direction(c1.x, c1.y, c2.x, c2.y); // а - направление (диррекционный угол) с центра 1й окр-ти // на центр второй окр-ти ap1:=a+a1; ap2:=a-a1; // а это направления на первую и вторую точки пересечения p1x:=c1.x+cos(ap1)*c1.r; p1y:=c1.y+sin(ap1)*c1.r; // аналогично для второй точки p2x:=c1.x+cos(ap2)*c1.r; p2y:=c1.y+sin(ap2)*c1.r;

вот. кажется всё.
единственное, что следует учесть
это
1) я не уверен, что правильно назвал функцию, возвращающую арккосинус
2) все тригонометрические функции, AFAIK на входе и на выходе имеют углы в радианах, проверь, а то можно пролететь.
3) я не отвечаю за работоспособность этого кода =) он был (большей частью) написан в коммандировке, когда компа под рукой не было.
4) если не уверен, попобуй изобразить чертёж (описаный в комментариях к коду). этот чертёж прояснит многое, возможно ты сможешь написать более компактный и эффективный код, чем мой

забыл ещё один момент
есть две ситуации, в которых окружности не пересекаются
это
когда расстояние между центрами больше суммы радиусов окружностей
и
расстояние между центрами меньше, чем радиус наименьшей окружности (т.е. маленькая окружность болтается внутри большой)

Точки пересечения двух окружностей Найти похожие ветки