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

Относительно быстрые способы проверки на пересечение без нахождения точек пересечения.

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

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

Определим условие пересечения двух отрезков.

Общее уравнение прямой

Ax + By + C = 0

где A, B, C - произвольные постоянные, причем A и B не равны нулю одновременно. Вектор с координатами (А, В) называют нормальным вектором и он перпендикулярен прямой. Вектор с координатами (B, -A) называют направляющим вектором.

Координаты направляющего вектора можно определить как

X = vertex2.x – vertex1.x;
Y = vertex2.y – vertex1.y;

Тогда произвольные постоянные будут равны

A = -Y = - (vertex2.y – vertex1.y);
B = X = vertex2.x – vertex1.x;
C = - Ax – By; - из общего уравнения прямой.

Таким образом находим уравнения обеих отрезков.

Теперь подставляем концы одного отрезка в уравнение другого.

Если для двух концов результат вычисления будет с одним знаком, то они лежат по одну сторону от прямой, следовательно пересечения нет. Если результаты вычислений с разными знаками для обеих прямых, то точки лежат по разным сторонам прямой - пересечение есть (т.е. если Ax + By + C < 0 то точка «слева», если Ax + By + C > 0, то точка «справа»).

public static function segmentBySegment(segmentA:Segment, segmentB:Segment):Boolean
{
 /*уравнение прямой в общем виде Ax + By + C = 0;
 определяем постоянные уравнений прямых, проходящих через отрезки (направляющий
 вектор)*/
 var a1:Number = -(segmentA.vertexB.y - segmentA.vertexA.y);
 var b1:Number = +(segmentA.vertexB.x - segmentA.vertexA.x);
 var c1:Number = -(a1 * segmentA.vertexA.x + b1 * segmentA.vertexA.y);
   
 var a2:Number = -(segmentB.vertexB.y - segmentB.vertexA.y);
 var b2:Number = +(segmentB.vertexB.x - segmentB.vertexA.x);
 var c2:Number = -(a2 * segmentB.vertexA.x + b2 * segmentB.vertexA.y);
   
 //подставляем концы отрезков для выяснения в каких полуплоскостях они находятся
 var segmentA_vertexA_InSegmentB:Number = a2 * segmentA.vertexA.x + b2 * segmentA.vertexA.y + c2;
 var segmentA_vertexB_InSegmentB:Number = a2 * segmentA.vertexB.x + b2 * segmentA.vertexB.y + c2;
   
 var segmentB_vertexA_InSegmentA:Number = a1 * segmentB.vertexA.x + b1 * segmentB.vertexA.y + c1;
 var segment_vertexB_InSegmentA:Number = a1 * segmentB.vertexB.x + b1 * segmentB.vertexB.y + c1;
   
 if (segmentA_vertexA_InSegmentB * segmentA_vertexB_InSegmentB >= 0 || segmentB_vertexA_InSegmentA * segmentB_vertexB_InSegmentA >= 0)
 {
  return false;
 }
   
 return true;
}

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

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

x1, y1 – первая точка отрезка;
x2, y2 – вторая точка отрезка;
x3, y3 – центр окружности;
radius – радиус окружности.

параметрическое уравнение прямой

 x = x1 + u * (x2 - x1)
 y = y1 + u * (y2 - y1)

уравнение окружности

(x - x3) * (x - x3) + (y - y3) * (y - y3) = radius * radius

подставляя x и y из уравнения прямой в уравнение окружности, получим квадратное уравнение

 a * u * u + b * u + c = 0, где
a = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
b = 2 * ((x2 - x1) * (x1 - x3) + (y2 - y1) * (y1 - y3));
c = x3 * x3  + y3 * y3 + x1 * x1 + y1 * y1 - 2 * (x3 * x1 + y3 * y1) - radius * radius

корни уравнения определяются как (- b +- Math.sqrt(b * b – 4 * a * c)) / (2 * a);

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

function circleBySegment(x1:Number, y1:Number, x2:Number, y2:Number, x3:Number, y3:Number, radius:Number):Boolean
{
 var a:Number = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
 var b:Number = 2 * ((x2 - x1) * (x1 - x3) + (y2 - y1) * (y1 - y3));
 var c:Number = x3 * x3  + y3 * y3 + x1 * x1 + y1 * y1 - 2 * (x3 * x1 + y3 * y1) - radius * radius;
 
 //т.е. если если есть отрицательные корни, то пересечение есть. анализируем теорему виета и формулу корней
 //на предмет отрицательных корней
 if ( - b < 0)
 {
  return (c < 0);
 }

 if ( - b < (2 * a))
 {
  return (4 * a * c - b * b < 0);
 }

 return (a + b + c < 0);
}

ссылки:
Геометрические Алгоритмы. Пересечение двух отрезков на плоскости.
Intersection of a Line and a Sphere (or circle)
Пересечение отрезка с окружностью
Формулы Виета