Как да разберете дали сегментите се пресичат. Определяне на пресечната точка на два сегмента. Пресечна точка

Пресечна точка

Нека са ни дадени две прави линии, определени от техните коефициенти и . Трябва да намерите тяхната пресечна точка или да разберете, че линиите са успоредни.

Решение

Ако две прави не са успоредни, тогава те се пресичат. За да намерите пресечната точка, достатъчно е да създадете система от две уравнения на права линия и да я решите:

Използвайки формулата на Крамър, веднага намираме решение на системата, което ще бъде желаното пресечна точка:

Ако знаменателят е нула, т.е.

тогава системата няма решения (директни паралелени не съвпадат) или има безкрайно много (преки съвпада). Ако е необходимо да се прави разлика между тези два случая, е необходимо да се провери дали коефициентите на правите са пропорционални със същия коефициент на пропорционалност като коефициентите и , за което е достатъчно да се изчислят двете детерминанти; ако и двете са равно на нула, тогава редовете съвпадат:

Внедряване

struct pt(double x, y;); структурна линия (двойно 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 – координатите на втория вектор.

Програма geometr4; (2 сегмента пресичат ли се?) Const _Eps: Real=1e-4; (точност на изчислението) var x1,y1,x2,y2,x3,y3,x4,y4: реален; var v1,v2,v3,v4: real;function RealLess(Const a, b: Real): Boolean; (Строго по-малко от) begin RealLess:= b-a> _Eps end; (RealLess)функция VektorMulti(ax,ay,bx,by:real): реално; (ax,ay - a координати bx,by - b координати) begin vektormulti:= ax*by-bx*ay; край; Функция LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real): boolean; (Отсечките пресичат ли се?) begin v1:=vektormulti(x4-x3,y4-y3,x1-x3,y1-y3); v2:=вектормулти(x4-x3,y4-y3,x2-x3,y2-y3); v3:=вектормулти(x2-x1,y2-y1,x3-x1,y3-y1); v4:=вектормулти(x2-x1,y2-y1,x4-x1,y4-y1); ако 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).

Относителната позиция на сегментите може да се провери с помощта на векторни продукти:

Помислете за сегмента П 3 П 4и точки П 1И P2.

Точка П 1лежи отляво на линията П 3 П 4, за нея векторният продукт v 1 > 0, тъй като векторите са положително ориентирани.
Точка P2разположен вдясно от линията, за него векторният продукт v 2< 0 , тъй като векторите са отрицателно ориентирани.

За да изясня точката П 1И P2лежат от противоположните страни на права линия П 3 П 4, е достатъчно условието да е изпълнено v 1 v 2< 0 (векторните произведения имаха противоположни знаци).

Подобно разсъждение може да се направи за сегмента П 1 П 2и точки П 3И P 4.

Така че, ако v 1 v 2< 0 И v 3 v 4< 0 , тогава отсечките се пресичат.

Векторното произведение на два вектора се изчислява по формулата:

Където:
брадва, ай— координати на първия вектор,
bx, от— координати на втория вектор.

Уравнение на права, минаваща през две различни точки, зададени от техните координати.

Нека на една права линия са дадени две несъвпадащи точки: П 1с координати ( x 1 ;y 1)И P2с координати (x 2; y 2).

Пресечна точка на линии

Съответно, вектор с начало в точката П 1и завършват в точка P2има координати (x 2 -x 1, y 2 -y 1). Ако P(x, y)е произволна точка на права, тогава координатите на вектора P 1 Pравен (x - x 1, y - y 1).

Използвайки векторното произведение, условието за колинеарност на векторите P 1 PИ П 1 П 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).

Как да намерим пресечната точка на линиите?
Очевидното решение е да се реши системата от линейни уравнения:

брадва 1 +по 1 =-c 1
брадва 2 +по 2 =-c 2 (2)

Въведете символи:

Тук де определящият фактор на системата и Dx, Dy— детерминанти, произтичащи от замяната на колоната от коефициенти със съответните неизвестни с колона от свободни членове. Ако D ≠ 0, то системата (2) е определена, т.е. има единствено решение. Това решение може да се намери с помощта на следните формули: x 1 =D x /D, y 1 =D y /D, които се наричат ​​формули на Крамър. Бързо напомняне как се изчислява детерминантата от втори ред. Детерминантата разграничава два диагонала: главния и второстепенния. Главният диагонал се състои от елементи, взети в посока от горния ляв ъгъл на определителя към долния десен ъгъл. Страничен диагонал - от горния десен ъгъл до долния ляв ъгъл. Детерминантът от втори ред е равен на произведението на елементите на главния диагонал минус произведението на елементите на второстепенния диагонал.

Нека са дадени два сегмента. Първият е даден с точки P 1 (x 1; y 1)И P 2 (x 2; y 2). Вторият се дава по точки P 3 (x 3; y 3)И P 4 (x 4; y 4).

Относителната позиция на сегментите може да се провери с помощта на векторни продукти:

Помислете за сегмента П 3 П 4и точки П 1И P2.

Точка П 1лежи отляво на линията П 3 П 4, за нея векторният продукт v 1 > 0, тъй като векторите са положително ориентирани.
Точка P2разположен вдясно от линията, за него векторният продукт v 2< 0 , тъй като векторите са отрицателно ориентирани.

За да изясня точката П 1И P2лежат от противоположните страни на права линия П 3 П 4, е достатъчно условието да е изпълнено v 1 v 2< 0 (векторните произведения имаха противоположни знаци).

Подобно разсъждение може да се направи за сегмента П 1 П 2и точки П 3И P 4.

Така че, ако v 1 v 2< 0 И v 3 v 4< 0 , тогава отсечките се пресичат.

Векторното произведение на два вектора се изчислява по формулата:

Където:
брадва, ай- координати на първия вектор,
bx, от- координати на втория вектор.

Уравнение на права, минаваща през две различни точки, зададени от техните координати.

Нека на една права линия са дадени две несъвпадащи точки: П 1с координати ( x 1 ;y 1)И P2с координати (x 2; y 2). Съответно, вектор с начало в точката П 1и завършват в точка P2има координати (x 2 -x 1, y 2 -y 1). Ако P(x, y)е произволна точка на права, тогава координатите на вектора P 1 Pравен (x - x 1, y – y 1).

Използвайки векторното произведение, условието за колинеарност на векторите P 1 PИ П 1 П 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).

Как да намерим пресечната точка на линиите?
Очевидното решение е да се реши системата от линейни уравнения:

брадва 1 +по 1 =-c 1
брадва 2 +по 2 =-c 2 (2)

Въведете символи:

Тук де определящият фактор на системата и Dx, Dy- детерминанти, произтичащи от замяната на колоната от коефициенти със съответните неизвестни с колона от свободни членове. Ако D ≠ 0, то системата (2) е определена, т.е. има единствено решение. Това решение може да се намери с помощта на следните формули: x 1 =D x /D, y 1 =D y /D, които се наричат ​​формули на Крамър. Бързо напомняне как се изчислява детерминантата от втори ред. Детерминантата разграничава два диагонала: главния и второстепенния. Главният диагонал се състои от елементи, взети в посока от горния ляв ъгъл на определителя към долния десен ъгъл. Страничен диагонал - от горния десен ъгъл до долния ляв ъгъл. Детерминантът от втори ред е равен на произведението на елементите на главния диагонал минус произведението на елементите на второстепенния диагонал.