Пусть даны два отрезка. Первый задан точками P 1 (x 1 ;y 1)
и P 2 (x 2 ;y 2)
. Второй задан точками P 3 (x 3 ;y 3)
и P 4 (x 4 ;y 4)
.
Взаимное расположение отрезков можно проверить с помощью векторных произведений:
Рассмотрим отрезок P 3 P 4
и точки P 1
и P 2
.
Точка P 1
лежит слева от прямой P 3 P 4
, для нее векторное произведение v 1 > 0
, так как векторы положительно ориентированы.
Точка P 2
расположена справа от прямой, для нее векторное произведение v 2 < 0
, так как векторы отрицательно ориентированы.
Для того чтобы точки P 1 и P 2 лежали по разные стороны от прямой P 3 P 4 , достаточно, чтобы выполнялось условие v 1 v 2 < 0 (векторные произведения имели противоположные знаки).
Аналогичные рассуждения можно провести для отрезка P 1 P 2 и точек P 3 и P 4 .
Итак, если v 1 v 2 < 0 и v 3 v 4 < 0 , то отрезки пересекаются.
Векторное произведение двух векторов вычисляется по формуле:
где:
ax
, ay
- координаты первого вектора,
bx
, by
- координаты второго вектора.
Уравнение прямой, проходящей через две различные точки, заданные своими координатами.
Пусть на прямой заданы две не совпадающие точки:P 1 с координатами (x 1 ;y 1) и P 2 с координатами (x 2 ; y 2) . Соответственно вектор с началом в точке P 1 и концом в точке P 2 имеет координаты (x 2 -x 1 , y 2 -y 1) . Если P(x, y) – произвольная точка на прямой, то координаты вектора P 1 P равны (x - x 1 , y – y 1).
С помощью векторного произведения условие коллинеарности векторов P 1 P
и P 1 P 2
можно записать так:
|P 1 P
,P 1 P 2
|=0
, т.е. (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
или
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0
Последнее уравнение переписывается следующим образом:
ax + by + c = 0,
(1)
где
a = (y 2 -y 1),
b = (x 1 -x 2),
c = x 1 (y 1 -y 2) + y 1 (x 2 -x 1)
Итак, прямую можно задать уравнением вида (1).
Как найти точку пересечения прямых?
Очевидное решение состоит в том, чтобы решить систему уравнений прямых:
ax 1 +by 1 =-c 1
ax 2 +by 2 =-c 2
(2)
Ввести обозначения:
Здесь D – определитель системы, а D x ,D y - определители, получающиеся в результате замены столбца коэффициентов при соответствующем неизвестном столбцом свободных членов. Если D ≠ 0 , то система (2) является определенной, то есть имеет единственное решение. Это решение можно найти по следующим формулам: x 1 =D x /D, y 1 =D y /D , которые называются формулами Крамера. Небольшое напоминание, как вычисляется определитель второго порядка. В определителе различают две диагонали: главную и побочную. Главная диагональ состоит из элементов, взятых по направлению от верхнего левого угла определителя в нижний правый угол. Побочная диагональ – из правого верхнего в нижний левый. Определитель второго порядка равен произведению элементов главной диагонали минус произведение элементов побочной диагонали.
Пересечение отрезков
Пересечение отрезков
Алгоритм Пересечение отрезков (Бентли, Оттманн 1979) позволяет найти все точки пересечений прямолинейных отрезков на плоскости . В нем применяется метод выметающей прямой (= заметающей прямой, движущейся прямой, сканирующей линии; англ. sweeping line). В методе используется вертикальная выметающая прямая движущаяся слева направо, при этом отрезки, которые она пересекает при данной координате x , можно упорядочить по координате y , тем самым их можно сравнивать между собой (какой выше, какой ниже). Это сравнение можно осуществить, например, используя уравнение прямой, проходящей через две точки (отрезки заданы двумя своими конечными точками): , где x 1 , y 1 и x 2 , y 2 - координаты, соответственно, первой и второй точек отрезка. Выметающая прямая перемещается по так называемым точкам событиям (левым и правым концам отрезков, а также точкам пересечения отрезков). После точки пересечения отрезки следует менять местами, так как, например, самый верхний из пересекающихся отрезков после точки пересечения становится самым нижним. Приведенный ниже алгоритм не рассчитан на случай, когда два отрезка пересекаются больше, чем в одной точке.
NB Выметающую прямую можно также представить как горизонтальную, движущуюся сверху вниз по координате y , и сравнивать пересекающие ее отрезки по координате x .
Пересечение отрезков
Обработка вертикальных отрезков
Возникает проблема с вертикальным отрезком в том смысле как его сравнивать на выше/ниже с пересекающими отрезками. Для этого можно, например, считать, что если точка пересечения вертикального с не вертикальным отрезков находится ниже текущей координаты y точки события, то вертикальный отрезок находится выше, если точка пересечения выше текущей координаты y точки события, то вертикальный отрезок считается ниже пересекающего его. Если текущая координата y равна координате y точки события, то при удалении отрезка считать, что вертикальный отрезок ниже, при вставке же считать, что он выше.
Квадрат памяти
В худшем случае, когда, например, все отрезки, пересекаясь между собой, образуют прямоугольную сетку, будет точек пересечений, которые надо будет хранить. Чтобы избежать использования квадрата памяти в алгоритме, можно удалять точку пересечения отрезков, которые временно перестают быть соседними при данном положении выметающей прямой. Эти точки все равно будут снова найдены при последующих шагах алгоритма, когда данные отрезки снова станут соседними (Печ, Шерир 1991).
Алгоритм segmentsIntersections
В приведенном ниже псевдокоде используются:
- Q - динамические структура данных без повторений с логарифмическим временем поиска, вставки, удаления точек событий и поиска минимального элемента (например, красно-чёрное дерево , 2-3 дерево).
- T - динамические структура данных без повторений с логарифмическим временем поиска, вставки, удаления отрезков. В ней хранятся все отрезки, пересекающие выметающую прямую (например, красно-чёрное дерево, 2-3 дерево).
- q - точка события.
- newq - только что найденная точка пекресечения отрезков, точка события.
- L(q) - множество отрезков, левый конец которых - q (для вертикальных отрезков левым считается нижний конец).
- R(q) - множество отрезков, правым концом которых является q.
- I(q) - множество отрезков, пересекающихся в q.
Анализ
Пусть n
- число отрезков, - число отрезков, пересекающих точку q
. Тогда время на инициализацию Q равно , на инициализацию T - . На поиск всех отрезков, проходящих через точку q
и обновление Q, требуется 
времени. На обновление T также времени. Суммарно: , где k
- число точек пересечения . .
Память , благодаря тому, что удаляются точки пересечения отрезков, которые перестали быть соседними, иначе было бы , где .
Литература
- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. - Springer, 2000. - С. 368.
- Прапарата Ф., Шеймос М. Вычислительная геометрия: Введение = Computational Geometry An introduction. - М.: Мир, 1989. - С. 478.
- Ласло М. Вычислительная геометрия и компьютерная графика на C++. - М.: БИНОМ, 1997. - С. 304.
- Т. Кормен, Ч. Лейзерсон, Р.Ривест, К.Штайн Алгоритмы. Построение и анализ. = Introduction to Algorithms. - 2-e изд. - “Вильямс”, 2005. - С. 1296.
Ссылки
- Визуализатор - частный случай (алгоритм Шеймоса - Гоя, 1976 (определение наличия пересекающихся отрезков)).
Wikimedia Foundation . 2010 .
- Переславец
- Переславль-Залесский (значения)
Смотреть что такое "Пересечение отрезков" в других словарях:
Программируемые алгоритмы - Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия
Непрерывность множества действительных чисел - Непрерывность действительных чисел свойство системы действительных чисел, которым не обладает множество рациональных чисел. Иногда вместо непрерывности говорят о полноте системы действительных чисел. Существует несколько различных… … Википедия
Список алгоритмов - Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Алгоритм Бентли - Оттмана - (1979) позволяет найти все точки пересечений прямолинейных отрезков на плоскости. В нем применяется метод выметающей прямой (= заметающей прямой, движущейся прямой, сканирующей линии; англ. sweeping line). В методе используется вертикальная… … Википедия
Алгоритм Бентли - Оттмана (1979) позволяет найти все точки пересечений прямолинейных отрезков на плоскости. В нем применяется метод выметающей прямой (заметающей прямой, движущейся прямой, сканирующей линии; англ. sweeping line). В методе… … Википедия
Вычислительная геометрия - раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного объекта другому, поиск их… … Википедия
Компьютерная геометрия - Вычислительная геометрия раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного… … Википедия
ЛИНИЯ - кривая, геометрическое понятие, точное и в то же время достаточно общее определение к рого представляет значитю трудности и осуществляется в разных разделах геометрии различно. В рамках элементарной геометрии понятие Л. не получает отчетливой… … Математическая энциклопедия
БИКОМПАКТНОЕ ПРОСТРАНСТВО - топологическое пространство, в каждом открытом покрытии к рого содержится конечное подпокрытие того же пространства. Следующие утверждения равносильны: 1) пространство Xбикомпактно; 2) пересечение любой центрированной системы замкнутых в… … Математическая энциклопедия
Точка пересечения прямых
Пусть нам даны две прямые, заданные своими коэффициентами и . Требуется найти их точку пересечения, или выяснить, что прямые параллельны.
Решение
Если две прямые не параллельны, то они пересекаются. Чтобы найти точку пересечения, достаточно составить из двух уравнений прямых систему и решить её:
Пользуясь формулой Крамера, сразу находим решение системы, которое и будет искомой точкой пересечения :
Если знаменатель нулевой, т.е.
то система решений не имеет (прямые параллельны и не совпадают) или имеет бесконечно много (прямые совпадают ). Если необходимо различить эти два случая, надо проверить, что коэффициенты прямых пропорциональны с тем же коэффициентом пропорциональности, что и коэффициенты и , для чего достаточно посчитать два определителя, если они оба равны нулю, то прямые совпадают:
Реализация
struct pt {double x, y;}; struct line {double a, b, c;}; constdouble EPS =1e-9; double det (double a, double b, double c, double d){return a * d — b * c;} bool intersect (line m, line n, pt & res){double zn = det (m.a, m.b, n.a, n.b);if(abs(zn)< EPS)returnfalse; res.x=- det (m.c, m.b, n.c, n.b)/ zn; res.y=- det (m.a, m.c, n.a, n.c)/ zn;returntrue;} bool parallel (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS;} bool equivalent (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS &&abs(det (m.a, m.c, n.a, n.c))< EPS &&abs(det (m.b, m.c, n.b, n.c))< EPS;}
Урок из серии «Геометрические алгоритмы »
Здравствуйте, дорогой читатель.
Совет 1: Как найти координаты точки пересечения двух прямых
Напишем еще три новые функции.
Функция LinesCross() будет определять, пересекаются ли два отрезка . В ней взаимное расположение отрезков определяется с помощью векторных произведений. Для вычисления векторных произведений напишем функцию – VektorMulti().
Функция RealLess() будет использоваться для реализации операции сравнения “<” (строго меньше) для вещественных чисел.
Задача1. Два отрезка заданы своими координатами. Составить программу, которая определяет, пересекаются ли эти отрезки , не находя точку пересечения.
Решение
. Второй задан точками .
Рассмотрим отрезок и точки и .
Точка лежит слева от прямой , для нее векторное произведение 
> 0, так как векторы положительно ориентированы.
Точка расположена справа от прямой, для нее векторное произведение 
< 0, так как векторы отрицательно ориентированы.
Для того чтобы точки и , лежали по разные стороны от прямой , достаточно, чтобы выполнялось условие < 0 (векторные произведения имели противоположные знаки).
Аналогичные рассуждения можно провести для отрезка и точек и .
Итак, если 
, то отрезки пересекаются.
Для проверки этого условия используется функцию LinesCross(), а для вычисления векторных произведений – функция VektorMulti().
ax, ay – координаты первого вектора,
bx, by – координаты второго вектора.
Program geometr4; {Пересекаются ли 2 отрезка?} Const _Eps: Real=1e-4; {точность вычслений} var x1,y1,x2,y2,x3,y3,x4,y4: real; var v1,v2,v3,v4: real;function RealLess(Const a, b: Real): Boolean; {Строго меньше} begin RealLess:= b-a> _Eps end; {RealLess}function VektorMulti(ax,ay,bx,by:real): real; {ax,ay — координаты a bx,by — координаты b } begin vektormulti:= ax*by-bx*ay; end;Function LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real): boolean; {Пересекаются ли отрезки?} begin v1:=vektormulti(x4-x3,y4-y3,x1-x3,y1-y3); v2:=vektormulti(x4-x3,y4-y3,x2-x3,y2-y3); v3:=vektormulti(x2-x1,y2-y1,x3-x1,y3-y1); v4:=vektormulti(x2-x1,y2-y1,x4-x1,y4-y1); if RealLess(v1*v2,0) and RealLess(v3*v4,0) {v1v2<0 и v3v4<0, отрезки пересекаются} then LinesCross:= true else LinesCross:= false end; {LinesCross}begin {main} writeln(‘Введите координаты отрезков: x1,y1,x2,y2,x3,y3,x4,y4’); readln(x1,y1,x2,y2,x3,y3,x4,y4); if LinesCross(x1,y1,x2,y2,x3,y3,x4,y4) then writeln (‘Да’) else writeln (‘Нет’) end.
Результаты выполнения программы:
Введите координаты отрезков: -1 1 2 2.52 2 1 -1 3
Да.
Мы написали программу, определяющую, пересекаются ли отрезки, заданные своими координатами.
На следующем уроке мы составим алгоритм, с помощью которого можно будет определить, лежит ли точка внутри треугольника.
Уважаемый читатель.
Вы уже познакомились с несколькими уроками из серии «Геометрические алгоритмы». Все ли доступно написано? Я буду Вам очень признательна, если Вы оставите отзыв об этих уроках. Возможно, что-то нужно еще доработать.
С уважением, Вера Господарец.
Пусть даны два отрезка. Первый задан точками P 1 (x 1 ;y 1)
и P 2 (x 2 ;y 2)
. Второй задан точками P 3 (x 3 ;y 3)
и P 4 (x 4 ;y 4)
.
Взаимное расположение отрезков можно проверить с помощью векторных произведений:
Рассмотрим отрезок P 3 P 4
и точки P 1
и P 2
.
Точка P 1
лежит слева от прямой P 3 P 4
, для нее векторное произведение v 1 > 0
, так как векторы положительно ориентированы.
Точка P 2
расположена справа от прямой, для нее векторное произведение v 2 < 0
, так как векторы отрицательно ориентированы.
Для того чтобы точки P 1 и P 2 лежали по разные стороны от прямой P 3 P 4 , достаточно, чтобы выполнялось условие v 1 v 2 < 0 (векторные произведения имели противоположные знаки).
Аналогичные рассуждения можно провести для отрезка P 1 P 2 и точек P 3 и P 4 .
Итак, если v 1 v 2 < 0 и v 3 v 4 < 0 , то отрезки пересекаются.
Векторное произведение двух векторов вычисляется по формуле:
где:
ax
, ay
— координаты первого вектора,
bx
, by
— координаты второго вектора.
Уравнение прямой, проходящей через две различные точки, заданные своими координатами.
Пусть на прямой заданы две не совпадающие точки:P 1 с координатами (x 1 ;y 1) и P 2 с координатами (x 2 ; y 2) .
Пересечение прямых
Соответственно вектор с началом в точке P 1 и концом в точке P 2 имеет координаты (x 2 -x 1 , y 2 -y 1) . Если P(x, y) – произвольная точка на прямой, то координаты вектора P 1 P равны (x — x 1 , y – y 1).
С помощью векторного произведения условие коллинеарности векторов P 1 P
и P 1 P 2
можно записать так:
|P 1 P,P 1 P 2 |=0
, т.е. (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
или
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0
Последнее уравнение переписывается следующим образом:
ax + by + c = 0,
(1)
где
a = (y 2 -y 1),
b = (x 1 -x 2),
c = x 1 (y 1 -y 2) + y 1 (x 2 -x 1)
Итак, прямую можно задать уравнением вида (1).
Как найти точку пересечения прямых?
Очевидное решение состоит в том, чтобы решить систему уравнений прямых:
ax 1 +by 1 =-c 1
ax 2 +by 2 =-c 2
(2)
Ввести обозначения:
Здесь D – определитель системы, а D x ,D y — определители, получающиеся в результате замены столбца коэффициентов при соответствующем неизвестном столбцом свободных членов. Если D ≠ 0 , то система (2) является определенной, то есть имеет единственное решение. Это решение можно найти по следующим формулам: x 1 =D x /D, y 1 =D y /D , которые называются формулами Крамера. Небольшое напоминание, как вычисляется определитель второго порядка. В определителе различают две диагонали: главную и побочную. Главная диагональ состоит из элементов, взятых по направлению от верхнего левого угла определителя в нижний правый угол. Побочная диагональ – из правого верхнего в нижний левый. Определитель второго порядка равен произведению элементов главной диагонали минус произведение элементов побочной диагонали.
В былые времена я увлекался компьютерной графикой, как 2х так и 3х мерной, в том числе математическими визуализациями. Что называется just for fun, будучи студентом, написал программу визуализирующую N-мерные фигуры, вращающиеся в любых измерениях, хотя практически меня хватило только на определение точек для 4-D гиперкуба. Но это только присказка. Любовь к геометрии осталась у меня с тех пор и по сей день, и я до сих пор люблю решать интересные задачи интересными способами.Одна из таких задач попалась мне в 2010 году. Сама задача достаточно тривиальна: необходимо найти, пересекаются ли два 2-D отрезка, и если пересекаются - найти точку их пересечения. Более интересно решение, которое, я считаю, получилось достаточно элегантным, и которое я хочу предложить на суд читателя. На оригинальность алгоритма не претендую (хотя и хотелось бы), но в сети подобных решений я найти не смог.
Задача
Даны два отрезка, каждый из которых задан двумя точками: (v11, v12), (v21, v22). Необходимо определить, пересекаются ли они, и если пересекаются, найти точку их пересечения.Решение
Для начала необходимо определить, пересекаются ли отрезки. Необходимое и достаточное условие пересечения, которое должно быть соблюдено для обоих отрезков следующее: конечные точки одного из отрезков должны лежать в разных полуплоскостях, если разделить плоскость линией, на которой лежит второй из отрезков. Продемонстрируем это рисунком.На левом рисунке (1) показаны два отрезка, для обоих из которых условие соблюдено, и отрезки пересекаются. На правом (2) рисунке условие соблюдено для отрезка b, но для отрезка a оно не соблюдается, соответственно отрезки не пересекаются.
Может показаться, что определить, с какой стороны от линии лежит точка - нетривиальная задача, но у страха глаза велики, и всё не так сложно. Мы знаем, что векторное умножение двух векторов даёт нам третий вектор, направление которого зависит от того, положительный или отрицательный угол между первым и вторым вектором, соответственно такая операция антикоммутативна. А так как все вектора лежат на плоскости X-Y, то их векторное произведение (которое обязано быть перпендикулярным перемножаемым векторам) будет иметь ненулевой только компоненту Z, соответственно и отличие произведений векторов будет только в этой компоненте. Причем при изменении порядка перемножения векторов (читай: угла между перемножаемыми векторами) состоять оно будет исключительно в изменении знака этой компоненты.
Поэтому мы можем умножить попарно-векторно вектор разделяющего отрезка на векторы направленные от начала разделяющего отрезка к обеим точкам проверяемого отрезка. 
Если компоненты Z обоих произведений будет иметь различный знак, значит один из углов меньше 0 но больше -180, а второй больше 0 и меньше 180, соответственно точки лежат по разные стороны от прямой. Если компоненты Z обоих произведений имеют одинаковый знак, следовательно и лежат они по одну сторону от прямой.
Если один из компонент Z является нулём, значит мы имеем пограничный случай, когда точка лежит аккурат на проверяемой прямой. Оставим пользователю определять, хочет ли он считать это пересечением.
Затем нам необходимо повторить операцию для другого отрезка и прямой, и убедиться в том, что расположение его конечных точек также удовлетворяет условию.
Итак, если всё хорошо и оба отрезка удовлетворяют условию, значит пересечение существует. Давайте найдём его, и в этом нам также поможет векторное произведение.
Так как в векторном произведении мы имеем ненулевой лишь компоненту Z, то его модуль (длина вектора) будет численно равен именно этой компоненте. Давайте посмотрим, как найти точку пересечения.
Длина векторного произведения векторов a и b (как мы выяснили, численно равная его компоненте Z) равна произведению модулей этих векторов на синус угла между ними (|a| |b| sin(ab)). Соответственно, для конфигурации на рисунке мы имеем следующее: |AB x AC| = |AB||AC|sin(α), и |AB x AD| = |AB||AD| sin(β). |AC|sin(α) является перпендикуляром, опущенным из точки C на отрезок AB, а |AD|sin(β) является перпендикуляром, опущенным из точки D на отрезок AB (катетом ADD"). Так как углы γ и δ - вертикальные углы, то они равны, а значит треугольники PCC" и PDD" подобны, а соответственно и длины всех их сторон пропорциональны в равном отношении.
Имея Z1 (AB x AC, а значит |AB||AC|sin(α)) и Z2 (AB x AD, а значит |AB||AD|sin(β)), мы можем рассчитать CC"/DD" (которая будет равна Z1/Z2), а также зная что CC"/DD" = CP/DP легко можно высчитать местоположение точки P. Лично я делаю это следующим образом:
Px = Cx + (Dx-Cx)*|Z1|/|Z2-Z1|;
Py = Cy + (Dy-Cy)*|Z1|/|Z2-Z1|;
Вот и все. Мне кажется что это действительно очень просто, и элегантно. В заключение хочу привести код функции, реализующий данный алгоритм. В функции использован самодельный шаблон vector
1 template
Одна из таких задач попалась мне в 2010 году. Сама задача достаточно тривиальна: необходимо найти, пересекаются ли два 2-D отрезка, и если пересекаются - найти точку их пересечения. Более интересно решение, которое, я считаю, получилось достаточно элегантным, и которое я хочу предложить на суд читателя. На оригинальность алгоритма не претендую (хотя и хотелось бы), но в сети подобных решений я найти не смог.
Задача
Даны два отрезка, каждый из которых задан двумя точками: (v11, v12), (v21, v22). Необходимо определить, пересекаются ли они, и если пересекаются, найти точку их пересечения.Решение
Для начала необходимо определить, пересекаются ли отрезки. Необходимое и достаточное условие пересечения, которое должно быть соблюдено для обоих отрезков следующее: конечные точки одного из отрезков должны лежать в разных полуплоскостях, если разделить плоскость линией, на которой лежит второй из отрезков. Продемонстрируем это рисунком.На левом рисунке (1) показаны два отрезка, для обоих из которых условие соблюдено, и отрезки пересекаются. На правом (2) рисунке условие соблюдено для отрезка b, но для отрезка a оно не соблюдается, соответственно отрезки не пересекаются.
Может показаться, что определить, с какой стороны от линии лежит точка - нетривиальная задача, но у страха глаза велики, и всё не так сложно. Мы знаем, что векторное умножение двух векторов даёт нам третий вектор, направление которого зависит от того, положительный или отрицательный угол между первым и вторым вектором, соответственно такая операция антикоммутативна. А так как все вектора лежат на плоскости X-Y, то их векторное произведение (которое обязано быть перпендикулярным перемножаемым векторам) будет иметь ненулевой только компоненту Z, соответственно и отличие произведений векторов будет только в этой компоненте. Причем при изменении порядка перемножения векторов (читай: угла между перемножаемыми векторами) состоять оно будет исключительно в изменении знака этой компоненты.
Поэтому мы можем умножить попарно-векторно вектор разделяющего отрезка на векторы направленные от начала разделяющего отрезка к обеим точкам проверяемого отрезка.
Если компоненты Z обоих произведений будет иметь различный знак, значит один из углов меньше 0 но больше -180, а второй больше 0 и меньше 180, соответственно точки лежат по разные стороны от прямой. Если компоненты Z обоих произведений имеют одинаковый знак, следовательно и лежат они по одну сторону от прямой.
Если один из компонент Z является нулём, значит мы имеем пограничный случай, когда точка лежит аккурат на проверяемой прямой. Оставим пользователю определять, хочет ли он считать это пересечением.
Затем нам необходимо повторить операцию для другого отрезка и прямой, и убедиться в том, что расположение его конечных точек также удовлетворяет условию.
Итак, если всё хорошо и оба отрезка удовлетворяют условию, значит пересечение существует. Давайте найдём его, и в этом нам также поможет векторное произведение.
Так как в векторном произведении мы имеем ненулевой лишь компоненту Z, то его модуль (длина вектора) будет численно равен именно этой компоненте. Давайте посмотрим, как найти точку пересечения.
Длина векторного произведения векторов a и b (как мы выяснили, численно равная его компоненте Z) равна произведению модулей этих векторов на синус угла между ними (|a| |b| sin(ab)). Соответственно, для конфигурации на рисунке мы имеем следующее: |AB x AC| = |AB||AC|sin(α), и |AB x AD| = |AB||AD| sin(β). |AC|sin(α) является перпендикуляром, опущенным из точки C на отрезок AB, а |AD|sin(β) является перпендикуляром, опущенным из точки D на отрезок AB (катетом ADD"). Так как углы γ и δ - вертикальные углы, то они равны, а значит треугольники PCC" и PDD" подобны, а соответственно и длины всех их сторон пропорциональны в равном отношении.
Имея Z1 (AB x AC, а значит |AB||AC|sin(α)) и Z2 (AB x AD, а значит |AB||AD|sin(β)), мы можем рассчитать CC"/DD" (которая будет равна Z1/Z2), а также зная что CC"/DD" = CP/DP легко можно высчитать местоположение точки P. Лично я делаю это следующим образом:
Px = Cx + (Dx-Cx)*|Z1|/|Z2-Z1|;
Py = Cy + (Dy-Cy)*|Z1|/|Z2-Z1|;
Вот и все. Мне кажется что это действительно очень просто, и элегантно. В заключение хочу привести код функции, реализующий данный алгоритм. В функции использован самодельный шаблон vector
1 template