Относительно быстрые способы проверки на пересечение без нахождения точек пересечения.
Если нет необходимости определять координаты точки пересечения, то пересечение двух отрезков можно определять так:
Определим условие пересечения двух отрезков.
Общее уравнение прямой
где A, B, C - произвольные постоянные, причем A и B не равны нулю одновременно. Вектор с координатами (А, В) называют нормальным вектором и он перпендикулярен прямой. Вектор с координатами (B, -A) называют направляющим вектором.
Координаты направляющего вектора можно определить как
Тогда произвольные постоянные будут равны
Таким образом находим уравнения обеих отрезков.
Теперь подставляем концы одного отрезка в уравнение другого.
Если для двух концов результат вычисления будет с одним знаком, то они лежат по одну сторону от прямой, следовательно пересечения нет. Если результаты вычислений с разными знаками для обеих прямых, то точки лежат по разным сторонам прямой - пересечение есть (т.е. если Ax + By + C < 0 то точка «слева», если Ax + By + C > 0, то точка «справа»).
Аналогично, если не нужно определять координаты точки пересечения окружности и отрезка, а нужно просто знать есть ли пересечение или нет, то можно использовать следующий способ.
x1, y1 – первая точка отрезка;
x2, y2 – вторая точка отрезка;
x3, y3 – центр окружности;
radius – радиус окружности.
параметрическое уравнение прямой
уравнение окружности
подставляя x и y из уравнения прямой в уравнение окружности, получим квадратное уравнение
корни уравнения определяются как (- b +- Math.sqrt(b * b – 4 * a * c)) / (2 * a);
Если есть отрицательный корень, то пересечение есть. Определяем, при каких соотношениях коэффициентов будет отрицательный корень. Если оба корня отрицательные, то отрезок целиком в окружности.
ссылки:
Геометрические Алгоритмы. Пересечение двух отрезков на плоскости.
Intersection of a Line and a Sphere (or circle)
Пересечение отрезка с окружностью
Формулы Виета
Пересечение двух отрезков
Если нет необходимости определять координаты точки пересечения, то пересечение двух отрезков можно определять так:
Определим условие пересечения двух отрезков.
Общее уравнение прямой
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)
Пересечение отрезка с окружностью
Формулы Виета
Комментариев нет:
Отправить комментарий