Како да откриете дали отсечките се сечат. Одредување на точка на пресек на два отсечки. Пресечна точка

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

Да ни бидат дадени две прави, дефинирани со нивните коефициенти и . Треба да ја пронајдете нивната точка на пресек или да дознаете дека линиите се паралелни.

Решение

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

Користејќи ја формулата на Крамер, веднаш наоѓаме решение за системот, кое ќе биде посакуваното раскрсница:

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

тогаш системот нема решенија (директни паралелнои не се совпаѓаат) или има бескрајно многу (директни натпревар). Доколку е потребно да се направи разлика помеѓу овие два случаи, потребно е да се провери дали коефициентите на правите се пропорционални со истиот коефициент на пропорционалност како и коефициентите и , за што е доволно да се пресметаат двете детерминанти; ако се и двете еднакво на нула, тогаш линиите се совпаѓаат:

Имплементација

struct pt (двојно x, y;); struct линија (двојна a, b, c;); констуден EPS =1e-9; двојно det (двојно a, двојно b, двојно c, двојно d) (враќање a * d - b * c;) bool се вкрстува (линија m, линија n, pt & res) (двојно 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() се користи за пресметување векторски производи.

секира, 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;функција RealLess(Const a, b: Real): Булова; (Строго помалку од) започне RealLess:= b-a> _Eps end; (RealLess)функција VektorMulti(ax,ay,bx,by:real): реално; (ax,ay - a координати bx,by - b координати) почнуваат vektormulti:= ax*by-bx*ay; крај;Function LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real): бул; (Дали отсечките се сечат?) почнуваат 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); ако 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И P2.

Точка P 1лежи лево од линијата P 3 P 4, за неа векторскиот производ v 1 > 0, бидејќи векторите се позитивно ориентирани.
Точка P2лоциран десно од линијата, за него векторскиот производ v 2< 0 , бидејќи векторите се негативно ориентирани.

Да се ​​истакне поентата P 1И P2лежеше на спротивните страни на права линија 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 , тогаш отсечките се сечат.

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

Каде:
секира, ај- координати на првиот вектор,
bx, од страна на— координати на вториот вектор.

Равенка на права што минува низ две различни точки одредени со нивните координати.

Нека се дадени две точки кои не се совпаѓаат на права линија: P 1со координати ( x 1 ;y 1)И P2со координати (x 2 ; y 2).

Пресек на линии

Според тоа, вектор со потекло во точката P 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И 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

Последната равенка е препишана на следниов начин:
секира + со + 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).

Релативната положба на сегментите може да се провери со помош на векторски производи:

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

Точка P 1лежи лево од линијата P 3 P 4, за неа векторскиот производ v 1 > 0, бидејќи векторите се позитивно ориентирани.
Точка P2лоциран десно од линијата, за него векторскиот производ v 2< 0 , бидејќи векторите се негативно ориентирани.

Да се ​​истакне поентата P 1И P2лежеше на спротивните страни на права линија 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 , тогаш отсечките се сечат.

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

Каде:
секира, ај- координати на првиот вектор,
bx, од страна на- координати на вториот вектор.

Равенка на права што минува низ две различни точки одредени со нивните координати.

Нека се дадени две точки кои не се совпаѓаат на права линија: P 1со координати ( x 1 ;y 1)И P2со координати (x 2 ; y 2). Според тоа, вектор со потекло во точката P 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И 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

Последната равенка е препишана на следниов начин:
секира + со + 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, кои се нарекуваат Крамерови формули. Брзо потсетување за тоа како се пресметува детерминантата од втор ред. Детерминантата разликува две дијагонали: главната и секундарната. Главната дијагонала се состои од елементи земени во насока од горниот лев агол на детерминантата до долниот десен агол. Странична дијагонала - од горниот десен до долниот лев. Детерминантата од втор ред е еднаква на производот од елементите на главната дијагонала минус производот од елементите на секундарната дијагонала.