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

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

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

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

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

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

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

public Pair<double>? Intersect(Circle circle) >

struct Segment

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

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

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

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

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

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

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

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

bool EqualDoubles ( double n1, double n2, double precision_ ) < return ( fabs ( n1 - n2 ) <= precision_ ) ; >

// пересечение линии, проходящей через отрезок, с окружностью; // возвращает число точек пересечения: 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 ) ;

if ( xa_ >= xmin && xa_ <= xmax && ya_ >= ymin && ya_ <= ymax ) < xa = xa_ ; ya = ya_ ;

if ( xb_ >= xmin && xb_ <= xmax && yb_ >= ymin && yb_ <= ymax ) < xa = xb_ ; ya = yb_ ;

📎📎📎📎📎📎📎📎📎📎