Как определить пересекаются ли окружности

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

Пусть $R_1$ и $R_2$ – радиусы окружностей $\omega_1$ и $\omega_2$ и $d$ – расстояние между их центрами. Окружности $\omega_1$ и $\omega_2$ пересекаются тогда и только тогда, когда числа $R_1$, $R_2$, $d $ являются длинами сторон некоторого треугольника, т. е. удовлетворяют всем неравенствам треугольника: $$ R_1+R_2 > d, \, R_1+d > R_2, \, R_2+d > R_1. $$

Касающиеся окружности

Говорят, что две окружности касаются, если они имеют одну общую точку. Окружности касаются внутренним образом, если одна из них расположена внутри другой. Окружности касаются внешним образом, если они расположены вне друг друга.

Пусть $R_1$ и $R_2$ – радиусы окружностей $\omega_1$ и $\omega_2$ и $d$ – расстояние между их центрами. Окружности $\omega_1$ и $\omega_2$ касаются внешним образом тогда и только тогда, когда $R_1+R_2=d$, внутренним образом – когда $\left|R_1-R_2\right|=d$.

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

Чтобы использовать калькулятор, введите координаты x и y центра и радиус каждой окружности.

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

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

Первая окружность

Вторая окружность

Точность вычисления
Знаков после запятой: 2
Рассчитать
Проверка расстояния между окружностями
Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.
Загрузить 
 Ссылка  Сохранить  Виджет

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

Сама по себе задача нахождения точек пересечения двух окружностей достаточно проста, однако предварительно надо проанализировать если ли вообще точки пересения у данных двух окружностей. Поэтому начать надо с вычисления расстояния d в декартовых координатах между центрами окружностей и сравнения его с радиусами окружностей r1 и r2.

При этом возможно следующие случаи (расстояние между центрами показано красным отрезком):

Если окружности действительно пересекаются, калькулятор использует следующие формулы (в-основном выведенные из теоремы Пифагора), проиллюстрированные рисунком ниже:

Two intersection points

Сначала калькулятор находит отрезок a

Чтобы найти точку P3, калькулятор использует следующую формулу (в векторном виде):

И наконец, чтобы найти точки пересечения, калькулятор использует следующие уравнения:
Первая точка:

Обратите внимание на разные знаки перед вторым слагаемым

По теме также можно посмотреть следующие ссылки (на английском языке): Circle-Circle Intersection и Circles and spheres

Определить класс Окружность. Реализовать проверку пересечения с другой окружностью в виде метода. Переопределить метод сравнения с учетом радиуса

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

Отслеживать
48.6k 17 17 золотых знаков 56 56 серебряных знаков 100 100 бронзовых знаков
задан 12 фев 2020 в 17:37
75 8 8 бронзовых знаков
Так, стоп, вам надо чтобы все то, что вы понаписали было в одном классе? Или я вас не так понял?
13 фев 2020 в 5:19

Мне нужно чтобы моя проверка на пересечение , шла как метод в классе , но чтобы сравнение шло не через два а один объект. А насчет переопределения метода честно я сам не могу разобраться. По большей части изза этого зашел сюда. Знаю что такое переопределение, но не могу понять как его связать с моей программой

14 фев 2020 в 6:04
Спасибо , за помощь , использую второй вариант.
14 фев 2020 в 19:47
отметьте ответ галочкой, если он вам подошёл.
15 фев 2020 в 0:52

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

import math class Circle: def __init__(self, x, y, radius): self.x = x self.y = y self.radius = radius def persechenie(self,cir): if self.x == cir.x: if self.radius + cir.radius > abs(self.y - cir.y): print('Окружности пересекаются') else: print('Окружности не пересекаются') elif self.y == cir.y: if self.radius + cir.radius > abs(self.x - cir.x): print('Окружности пересекаются') else: print('Окружности не пересекаются') else: if (self.radius + cir.radius) ** 2 > abs((self.x - cir.x) ** 2 - (self.y - cir.y) ** 2): print('Окружности пересекаются') else: print('Окружности не пересекаются') cir1 = Circle(3, 5, 2) cir = Circle(7, 8, 2) cir1.persechenie(cir)

Отслеживать
ответ дан 14 фев 2020 в 7:11
Zeka Farzali Zeka Farzali
36 3 3 бронзовых знака
Если я правильно понял желание делать проверку через один обьект
14 фев 2020 в 7:12

Вот рабочий пример:

import math class Circle: def __init__(self,x,y,radius): self.x = x self.y = y self.radius = radius def persechenie(cir1,cir2): if cir1.x == cir2.x: if cir1.radius + cir2.radius > abs(cir1.y - cir2.y): print('Окружности пересекаются') else: print('Окружности не пересекаются') elif cir1.y == cir2.y: if cir1.radius + cir2.radius > abs(cir1.x - cir2.x): print('Окружности пересекаются') else: print('Окружности не пересекаются') else: if (cir1.radius + cir2.radius)**2 > abs((cir1.x - cir2.x)**2 - (cir1.y - cir2.y)**2): print('Окружности пересекаются') else: print('Окружности не пересекаются') cir1 = Circle(3,5,2) cir2 = Circle(7,8,2) Circle.persechenie(cir1,cir2)

Надеюсь я правильно понял ваш вопрос

Вот ещё один вариант, но тут надо вписывать все данные в один вызов класса:

import math class Circle: def __init__(self,x1,y1,radius1,x2,y2,radius2): self.x1 = x1 self.y1 = y1 self.radius1 = radius1 self.x2 = x2 self.y2 = y2 self.radius2 = radius2 if self.x1 == self.x2: if self.radius1 + self.radius2 > abs(self.y1 - self.y2): print('Окружности пересекаются') else: print('Окружности не пересекаются') elif self.y1 == self.y2: if self.radius1 + self.radius2 > abs(self.x1 - self.x2): print('Окружности пересекаются') else: print('Окружности не пересекаются') else: if (self.radius1 + self.radius2)**2 > abs((self.x1 - self.x2)**2 - (self.y1 - self.y2)**2): print('Окружности пересекаются') else: print('Окружности не пересекаются') Circle(3,4,2,7,8,2)

Вот ещё один пример:

import math class Circle: def __init__(self, x, y, radius): self.x = x self.y = y self.radius = radius def persechenie(self,cir): if self.x == cir.x: if self.radius + cir.radius > abs(self.y - cir.y): print('Окружности пересекаются') else: print('Окружности не пересекаются') elif self.y == cir.y: if self.radius + cir.radius > abs(self.x - cir.x): print('Окружности пересекаются') else: print('Окружности не пересекаются') else: if (self.radius + cir.radius) ** 2 > abs((self.x - cir.x) ** 2 - (self.y - cir.y) ** 2): print('Окружности пересекаются') else: print('Окружности не пересекаются') cir1 = Circle(3, 5, 2) cir2 = Circle(7, 8, 2) cir1.persechenie(cir2)

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

Помогите с алгоритмом. Есть отрезок, координаты концов которого извесни и окружность с извесными координатами центра и радиусом. как определить пренадлежит ли хоть одна точка отрезка данной окружности?

18 ответов

27 января 2010 года
380 / / 02.01.2008

Самый очевидный способ. Открываем учебник по линейной алгебре и аналитической геометрии, смотрим там уравнения.
Записываем уравнение в общем виде для окружности и отрезка (уравнение прямой и два двойных неравенства, ограничивающих прямую до отрезка). Решаем систему из этих двух уравнений и четырех неравенств относительно (х,у). Если решение существует — пересечение или касание есть. В программе надо подставить коэффициенты (рассчитать их по исходным данным возможно) и попытаться найти корни.
К слову, если корень единствнный, то отрезок касается окружности, если корня два — является хордой.

27 января 2010 года
874 / / 21.12.2007

Вот код на C# 3, умеющий пересекать явно заданные линии и окружности и даже определять принадлежность точки таким линиям. Это ~97% решения.

static class Doubles
public static double Square(this double x)
return x * x;
>

public static double Sqrt(this double x)
return Math.Sqrt(x);
>

public static bool SafeEquals(this double left, double rigth)
const double epsilon = 1e-7;
return Math.Abs(left — rigth) >
>

struct Vector
public Vector(double x, double y)
: this()
X = x;
Y = y;
>

public double X < get; private set; >
public double Y

public static Vector operator+(Vector left, Vector right)
return new Vector(left.X + right.X, left.Y + right.Y);
>

public static Vector operator-(Vector minuend, Vector substrahend)
return new Vector(minuend.X — substrahend.X, minuend.Y — substrahend.Y);
>

public static double operator*(Vector left, Vector right)
return left.X*right.X + left.Y*right.Y;
>

public static Vector operator *(double ratio, Vector v)
return new Vector(v.X*ratio, v.Y*ratio);
>

public static Vector operator * (Vector v, double ratio)
return ratio * v;
>

public Vector Normalize()
double length = Length;
if (length.SafeEquals(0.0))
throw new InvalidOperationException(«Attempt to normalize zero-length vector»);

return new Vector(X / length, Y / length);
>
>

struct Pair
public Pair(T first, T second)
: this()
First = first;
Second = second;
>

class Circle
public Circle(Vector center, double radius)
Center = center;
Radius = radius;
>

struct Line
public Line(Vector pivot, Vector direction)
: this()
U = pivot;
V = direction;
>

public static Line FromPoints(Vector p1, Vector p2)
return new Line(p1, p2 — p1);
>

public Vector U < get; private set; >
public Vector V

public Pair? Intersect(Circle circle)
Vector g = U — circle.Center;

double a = V * V;
double b = 2 * (V * g);
double c = g*g — circle.Radius.Square();
double d = b.Square() — 4*a*c;

if (d < 0)
return null;

double sqrt_from_d = d.Sqrt();
double double_a = 2*a;

double first = (-b — sqrt_from_d)/double_a;
double second = (-b + sqrt_from_d)/double_a;

return new Pair(PointFromRatio(first), PointFromRatio(second));
>

public Line Normalize()
return new Line(U, V.Normalize());
>

public Vector PointFromRatio(double ratio)
return U + V*ratio;
>

public bool Contains(Vector p)
if (V.X.SafeEquals(0d))
return p.X.SafeEquals(U.X);

if (V.Y.SafeEquals(0d))
return p.Y.SafeEquals(U.Y);

return ((p.X — U.X) / V.X).SafeEquals((p.Y — U.Y) / V.Y);
>
>

Линию можно задавать и по-другому (неявно). Почитать об этом можно (на аглицком), набрав в гугол запрос:
Glassner A. (ed.) Graphics gems, vol.1 (AP, 1995)(T)(666s).djvu

27 января 2010 года
4 / / 27.01.2010

Впринципе эта задачя у меня сводится до того что б найти количество отрезков, в которых хотя бы одна точка лежит в кругу

Тоесть все отрезки кроме В подходят по условию.

31 января 2010 года
451 / / 20.07.2008

1. Находите расстояние от точки (центр окружности) до прямой заданной двумя точками (концы отрезков). Алгоритм например такой.
2. Если расстояние меньше, чем радиус окружности, значит с прямой пересекается.
3. Осталось проверить пересекается ли отрезок, лежащий на этой прямой — это можно сделать через проверку пересечения диапозонов по оси x, в которых лежит окружность и отрезок. Для окружности это [Cx — r, Cx + r], для отрезка [x1, x2].

31 января 2010 года
874 / / 21.12.2007

3. Осталось проверить пересекается ли отрезок, лежащий на этой прямой — это можно сделать через проверку пересечения диапозонов по оси x, в которых лежит окружность и отрезок. Для окружности это [Cx — r, Cx + r], для отрезка [x1, x2]

Прямая может проходить вертикально. Впрочем, ерунда: достаточно проверить на равенство нулю x-компоненты вектора направления прямой, и, в случае чего, проверить попадание ординат отрезка по аналогичной формуле.
Да, хорошее решение.

31 января 2010 года
451 / / 20.07.2008

Эх, к сожалению, не очень хорошее. есть случае даже не с вертикальной прямой, когда это не сработает 🙁

Тогда однозначно решать систему уравнений, как предлагает MaitreDesir.
А для случая, когда отрезок внутри окружности и не пересекает ее — проверить расстояние от центра окружности до концов отрезка, которые должны быть меньше радиуса.

02 февраля 2010 года
76 / / 27.09.2009

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

03 февраля 2010 года
874 / / 21.12.2007

Концы отрезка могут лежать за пределами окружности.
Э-э-х, ладно:

public Pair? Intersect(Circle circle)
Vector g = U — circle.Center;

double a = V * V;
double b = 2 * (V * g);
double c = g*g — circle.Radius.Square();
double d = b.Square() — 4*a*c;

if (d < 0)
return null;

double sqrt_from_d = d.Sqrt();
double double_a = 2*a;

double first = (-b — sqrt_from_d)/double_a;
double second = (-b + sqrt_from_d)/double_a;

struct Segment
public readonly Vector Start;
public readonly Vector End;

public Segment(Vector start, Vector end)
Start = start;
End = end;
>

public bool IntersectsWith(Circle circle)
Line line = Line.FromPoints(Start, End);
Pair? intersection = line.Intersect(circle);

if (!intersection.HasValue)
return false;

Pair value = intersection.Value;
double first = value.First;
double second = value.Second;

// Не пересекает в двух случаях:
// 1. first < 0 && second < 0;
// 2. first > 1 && second > 1.

03 февраля 2010 года
76 / / 27.09.2009

Вот и я о том же. В этом случае нужно проверять расстояние между центром и прямой, но только в случае, если ближайшая точка прямой в центру принадлежит отрезку.

14 февраля 2010 года
11 / / 11.02.2010

форумчане и гости форума.
Вопрос у меня такой — как построить В канве точку, которая двигалась бы по окружности? как построить точку я знаю . В общем вопрос сводится к круговому движению.
x-a2y-b2=R2 — формула окружности.

23 мая 2010 года
2 / / 23.05.2010

Попробуйте через параметрические уравнения окружности:
x = x0 + R*sin(t)
y = y0 + R*cos(t)
где t [0; 2*Pi]
, если я правильно вас понял.

24 мая 2010 года
2 / / 19.05.2010

Пересечение отрезка с вертикальным отрезком.

Проблема в том, что K если принимать линию, на которой лежит отрезок как описанную уравнением y= kx b тут не рассчитаешь получается, на ноль делить надо. Вопрос: как быть? Может, кто-то сталкивался с такой проблемой?

26 мая 2010 года
2 / / 23.05.2010

Не утверждаю, что это лучшее решение, я делал так: проверял значение на равенство нулю, и если равно, то присваивал конечно малое значение, например 0.00001. После чего все нормально считалось. Потом округлял, в конце вычислений.

26 мая 2010 года
619 / / 12.09.2005

Пересечение отрезка с вертикальным отрезком.

разверните систему на 90 градусов — считайте относительно y

26 мая 2010 года
123 / / 14.12.2005

когда мне нужно было пересекать различные фигуры, я применял функции из этой библиотеки

PS но там есть заморочки со сборкой.

27 мая 2010 года
619 / / 12.09.2005

оптимизируем немного алгоритм.
1. определяем расстояние от концов отрезка до центра окружности (d1, d2)
2. если ((d1<=r) && (d2>=r)) || ((d1>=r) && (d2 <=r))— отрезок пересекает окружность в одном месте, конец
3. если (d1 — отрезок находится внутри окружности, не пересекая ее, конец
4. находим наименьшее расстояние от центра окружности до отрезка (d3)
5. если (d3 — либо касается, либо пересекает, конец
6. лежит за пределами

27 мая 2010 года
619 / / 12.09.2005
05 декабря 2012 года
1 / / 05.12.2012

Была задача найти единственное пересечение отрезка с окружностью, если таковое существует (третья функция ниже).
По теме — пригодится вторая. min2, max2 — то же, что min и max.
Магические коэффициенты образовались при решении системы уравнений: первое — уравнение окружности, второе — уравнение прямой по двум точкам.
Работает при любых отрезках.

bool EqualDoubles ( double n1, double n2, double precision_ )
<
return ( fabs ( n1 — n2 ) >

// пересечение линии, проходящей через отрезок, с окружностью;
// возвращает число точек пересечения: 0 или 1 или 2;
// если 1, результат в xa, xb
int LineCircleIntersection ( double x0, double y0, double r, // центр и рдиус окружности
double x1, double y1, // точки
double x2, double y2, // отрезка
double & xa, double & ya, // резуль-
double & xb, double & yb ) // тат
<
double q = x0 * x0 + y0 * y0 — r * r ;
double k = — 2.0 * x0 ;
double l = — 2.0 * y0 ;

double z = x1 * y2 — x2 * y1 ;
double p = y1 — y2 ;
double s = x1 — x2 ;

if ( EqualDoubles ( s, 0.0 , 0.001 ) )
<
s = 0.001 ;
>

double A = s * s + p * p ;
double B = s * s * k + 2.0 * z * p + s * l * p ;
double C = q * s * s + z * z + s * l * z ;

double D = B * B — 4.0 * A * C ;

if ( D < 0.0 )
<
return 0 ;
>
else if ( D < 0.001 )
<
xa = — B / ( 2.0 * A ) ;
ya = ( p * xa + z ) / s ;
return 1 ;
>
else
<
xa = ( — B + sqrt ( D ) ) / ( 2.0 * A ) ;
ya = ( p * xa + z ) / s ;

xb = ( — B — sqrt ( D ) ) / ( 2.0 * A ) ;
yb = ( p * xb + z ) / s ;
>

// единственное пересечение отрезка с окружностью
// результат — если единственное, то точка пересечения xa, ya
bool SegmentCircleIntersection ( double x0, double y0, double r, // центр и рдиус окружности
double x1, double y1, // точки
double x2, double y2, // отрезка
double & xa, double & ya ) // результат
<
double d1 = hypot ( x1 — x0,y1 — y0 ) ;
double d2 = hypot ( x2 — x0,y2 — y0 ) ;
if ( d1 > r && d2 > r )
<
return false ;
>
if ( d1 < r && d2 < r )
<
return false ;
>

double xa_ = 0.0 ;
double ya_ = 0.0 ;
double xb_ = 0.0 ;
double yb_ = 0.0 ;

if ( LineCircleIntersection ( x0,y0,r,x1,y1,x2,y2,xa_,ya_,xb_,yb_ ) < 1 )
<
return false ;
>

double xmin = min2 ( x1,x2 ) ;
double xmax = max2 ( x1,x2 ) ;
double ymin = min2 ( y1,y2 ) ;
double ymax = max2 ( y1,y2 ) ;

Похожие публикации:

Для чего предназначены диаграммы конечных автоматов

Как изменить межстрочный интервал в вордпресс

Как скачать музыку с телефона на флешку

Компьютер не видит покетбук что делать

Как определить пересекаются ли окружности