Нехай дано два відрізки. Перший заданий крапками 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, Які називаються формулами Крамера | Невеликий нагадування, як обчислюється визначник другого порядку. У визначнику розрізняють дві діагоналі: головну та побічну. Головна діагональ складається з елементів, взятих у напрямку верхнього лівого кута визначника в нижній правий кут. Побічна діагональ – з правого верхнього до нижнього лівого. Визначник другого порядку дорівнює добутку елементів головної діагоналі мінус добуток елементів побічної діагоналі.
Крапка перетину прямих
Нехай нам дані дві прямі, задані своїми коефіцієнтами і . Потрібно знайти їх точку перетину, або з'ясувати, що прямі паралельні.
Рішення
Якщо дві прямі не паралельні, всі вони перетинаються. Щоб знайти точку перетину, достатньо скласти із двох рівнянь прямих систему та розв'язати її:
Користуючись формулою Крамера, одразу знаходимо рішення системи, яке і буде шукане точкою перетину:
Якщо знаменник нульовий, тобто.
то система рішень не має (прямі паралельніі не збігаються) або має нескінченно багато (прямі збігаються). Якщо необхідно розрізнити ці два випадки, треба перевірити, що коефіцієнти прямих пропорційні з тим самим коефіцієнтом пропорційності, що і коефіцієнти і , для чого досить порахувати два визначники, якщо вони обидва рівні нулю, то прямі збігаються:
Реалізація
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 (ma, mb, na , nb); 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: реальна;функція 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) та 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, Які називаються формулами Крамера | Невеликий нагадування, як обчислюється визначник другого порядку. У визначнику розрізняють дві діагоналі: головну та побічну. Головна діагональ складається з елементів, взятих у напрямку верхнього лівого кута визначника в нижній правий кут. Побічна діагональ – з правого верхнього до нижнього лівого. Визначник другого порядку дорівнює добутку елементів головної діагоналі мінус добуток елементів побічної діагоналі.