Točka sjecišta linija

Neka su nam dane dvije ravne crte dane njihovim koeficijentima i . Potrebno je pronaći njihovu sjecišnu točku, odnosno utvrditi da su pravci paralelni.

Odluka

Ako dva pravca nisu paralelna, tada se sijeku. Da bismo pronašli točku sjecišta, dovoljno je sastaviti sustav dviju jednadžbi pravaca i riješiti ga:

Pomoću Cramerove formule odmah nalazimo rješenje sustava koje će biti željeno točka raskrižja:

Ako je nazivnik nula, tj.

tada sustav rješenja nema (direktne su paralelni a ne podudaraju se) ili ih ima beskonačno mnogo (izravnih odgovarati). Ako je potrebno razlikovati ova dva slučaja, potrebno je provjeriti jesu li koeficijenti pravaca proporcionalni s istim koeficijentom proporcionalnosti kao koeficijenti i , za što je dovoljno izračunati dvije determinante, ako su obje jednake na nulu, tada se linije podudaraju:

Provedba

struct pt (dvostruki x, y;); linija strukture (dvostruko a, b, c;); constdouble EPS=1e-9; dvostruko det (dvostruko a, dvostruko b, dvostruko c, dvostruko d)(vrati a * d - b * c;) bool intersect (linija m, linija n, pt & res)(dvostruko 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;}

Lekcija iz serije " Geometrijski algoritmi»

Pozdrav dragi čitatelju.

Savjet 1: Kako pronaći koordinate točke sjecišta dviju linija

Napišimo još tri nove funkcije.

Funkcija LinesCross() će odrediti je li presijecati da li dva segment. U njemu se relativni položaj segmenata određuje pomoću vektorskih proizvoda. Za izračun vektorskih umnožaka napišimo funkciju - VektorMulti().

Funkcija RealLess() koristit će se za implementaciju operacije usporedbe "<” (строго меньше) для вещественных чисел.

Zadatak1. Dva su segmenta dana svojim koordinatama. Napišite program koji određuje Da li se ti segmenti sijeku? bez pronalaženja sjecišta.

Odluka
. Drugi je dan točkama.

Razmotrimo segment i točke i .

Točka se nalazi lijevo od pravca za koji je vektorski produkt > 0, jer su vektori pozitivno orijentirani.

Točka se nalazi desno od linije, za nju je vektorski produkt < 0, так как векторы отрицательно ориентированы.

Da bi točke i , ležale na suprotnim stranama pravca , dovoljno je da je ispunjen uvjet< 0 (векторные произведения имели противоположные знаки).

Slično razmišljanje može se izvesti za segment i točke i .

Pa ako , tada se segmenti sijeku.

Za provjeru ovog uvjeta koristi se funkcija LinesCross(), a za izračun vektorskih produkata koristi se funkcija VektorMulti().

ax, ay su koordinate prvog vektora,

bx, by su koordinate drugog vektora.

Geometrija programa4; (Sjeku li se 2 segmenta?) Const _Eps: Real=1e-4; (preciznost izračuna) var x1,y1,x2,y2,x3,y3,x4,y4: stvarno; var v1,v2,v3,v4: real;function RealLess(Const a, b: Real): Boolean; (Strogo manje od) begin RealLess:= b-a> _Eps end; (RealLess)funkcija VektorMulti(ax,ay,bx,by:real): real; (ax,ay - a koordinate bx,by - b koordinate) begin vektormulti:= ax*by-bx*ay; kraj;Funkcija LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:stvarno): boolean; (Sjeku li se segmenti?) 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); ako RealLess(v1*v2.0) i 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.

Rezultati izvršenja programa:

Unesite koordinate segmenata: -1 1 2 2.52 2 1 -1 3
Da.

Napisali smo program koji određuje sijeku li se segmenti zadani svojim koordinatama.

U sljedećoj lekciji ćemo napisati algoritam koji se može koristiti za određivanje nalazi li se točka unutar trokuta.

Poštovani čitatelju.

Već ste pročitali nekoliko lekcija iz serije Geometrijski algoritmi. Je li sve dostupno napisano? Bit ću vam vrlo zahvalan ako ostavite recenziju ovih lekcija. Možda još nešto treba poboljšati.

S poštovanjem, Vera Gospodarets.

Neka su dana dva segmenta. Prvi je dan točkama P 1 (x 1 ; y 1) i P 2 (x 2; y 2). Drugi je dan točkama P 3 (x 3; y 3) i P 4 (x 4; y 4).

Relativni položaj segmenata može se provjeriti pomoću vektorskih proizvoda:

Razmotrite segment P 3 P 4 i bodova P1 i P2.

Točka P1 leži lijevo od linije P 3 P 4, za to vektorski produkt v1 > 0, budući da su vektori pozitivno orijentirani.
Točka P2 nalazi se desno od crte, za to je vektorski produkt v2< 0 , budući da su vektori negativno orijentirani.

Na točku P1 i P2 leže na suprotnim stranama ravne linije P 3 P 4, dovoljno je da je uvjet v 1 v 2< 0 (vektorski produkti su imali suprotne predznake).

Slično razmišljanje može se izvesti za segment P 1 P 2 i bodova P3 i P4.

Pa ako v 1 v 2< 0 i v 3 v 4< 0 , tada se segmenti sijeku.

Umnožak dvaju vektora izračunava se po formuli:

gdje:
sjekira, da su koordinate prvog vektora,
bx, po su koordinate drugog vektora.

Jednadžba pravca koji prolazi kroz dvije različite točke zadane njihovim koordinatama.

Neka su na pravoj liniji zadane dvije točke koje se ne podudaraju: P1 s koordinatama ( x1;y1) i P2 s koordinatama (x 2; y 2).

Sjecište linija

Prema tome, vektor s ishodištem u točki P1 i završiti u točki P2 ima koordinate (x 2 -x 1, y 2 -y 1). Ako P(x, y) je proizvoljna točka na pravcu, zatim koordinate vektora P 1 P jednak (x - x 1, y - y 1).

Uz pomoć križnog produkta uvjet kolinarnosti vektora P 1 P i P 1 P 2 može se napisati ovako:
|P 1 P,P 1 P 2 |=0, tj. (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
ili
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0

Posljednja jednadžba se prepisuje na sljedeći način:
ax + by + c = 0, (1)
gdje
a \u003d (y 2 -y 1),
b \u003d (x 1 -x 2),
c \u003d x 1 (y 1 -y 2) + y 1 (x 2 -x 1)

Dakle, pravac se može dati jednadžbom oblika (1).

Kako pronaći točku sjecišta linija?
Očito rješenje je riješiti sustav jednadžbi linija:

sjekira 1 +po 1 =-c 1
sjekira 2 +po 2 =-c 2 (2)

Unesite oznake:

Ovdje D je determinanta sustava, i D x ,D y su determinante dobivene zamjenom stupca koeficijenata za odgovarajuću nepoznanicu stupcem slobodnih članova. Ako D ≠ 0, tada je sustav (2) određen, odnosno ima jedinstveno rješenje. Ovo se rješenje može pronaći pomoću sljedećih formula: x 1 \u003d D x / D, y 1 \u003d D y / D, koje se nazivaju Cramerove formule. Mali podsjetnik kako se izračunava determinanta drugog reda. Odrednica razlikuje dvije dijagonale: glavnu i sporednu. Glavnu dijagonalu čine elementi uzeti u smjeru od gornjeg lijevog kuta determinante prema donjem desnom kutu. Bočna dijagonala - od gornjeg desnog do donjeg lijevog kuta. Determinanta drugog reda jednaka je umnošku elemenata glavne dijagonale minus umnošku elemenata sporedne dijagonale.

Neka su dana dva segmenta. Prvi je dan točkama P 1 (x 1 ; y 1) i P 2 (x 2; y 2). Drugi je dan točkama P 3 (x 3; y 3) i P 4 (x 4; y 4).

Relativni položaj segmenata može se provjeriti pomoću vektorskih proizvoda:

Razmotrite segment P 3 P 4 i bodova P1 i P2.

Točka P1 leži lijevo od linije P 3 P 4, za to vektorski produkt v1 > 0, budući da su vektori pozitivno orijentirani.
Točka P2 nalazi se desno od crte, za to je vektorski produkt v2< 0 , budući da su vektori negativno orijentirani.

Na točku P1 i P2 leže na suprotnim stranama ravne linije P 3 P 4, dovoljno je da je uvjet v 1 v 2< 0 (vektorski produkti su imali suprotne predznake).

Slično razmišljanje može se izvesti za segment P 1 P 2 i bodova P3 i P4.

Pa ako v 1 v 2< 0 i v 3 v 4< 0 , tada se segmenti sijeku.

Umnožak dvaju vektora izračunava se po formuli:

gdje:
sjekira, da- koordinate prvog vektora,
bx, po- koordinate drugog vektora.

Jednadžba pravca koji prolazi kroz dvije različite točke zadane njihovim koordinatama.

Neka su na pravoj liniji zadane dvije točke koje se ne podudaraju: P1 s koordinatama ( x1;y1) i P2 s koordinatama (x 2; y 2). Prema tome, vektor s ishodištem u točki P1 i završiti u točki P2 ima koordinate (x 2 -x 1, y 2 -y 1). Ako P(x, y) je proizvoljna točka na pravcu, zatim koordinate vektora P 1 P jednak (x - x 1, y - y 1).

Uz pomoć križnog produkta uvjet kolinarnosti vektora P 1 P i P 1 P 2 može se napisati ovako:
|P 1 P ,P 1 P 2 |=0, tj. (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
ili
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0

Posljednja jednadžba se prepisuje na sljedeći način:
ax + by + c = 0, (1)
gdje
a \u003d (y 2 -y 1),
b \u003d (x 1 -x 2),
c \u003d x 1 (y 1 -y 2) + y 1 (x 2 -x 1)

Dakle, pravac se može dati jednadžbom oblika (1).

Kako pronaći točku sjecišta linija?
Očito rješenje je riješiti sustav jednadžbi linija:

sjekira 1 +po 1 =-c 1
sjekira 2 +po 2 =-c 2 (2)

Unesite oznake:

Ovdje D je determinanta sustava, i D x ,D y su determinante koje proizlaze iz zamjene stupca koeficijenata za odgovarajuću nepoznanicu stupcem slobodnih članova. Ako D ≠ 0, tada je sustav (2) određen, odnosno ima jedinstveno rješenje. Ovo se rješenje može pronaći pomoću sljedećih formula: x 1 \u003d D x / D, y 1 \u003d D y / D, koje se nazivaju Cramerove formule. Mali podsjetnik kako se izračunava determinanta drugog reda. Odrednica razlikuje dvije dijagonale: glavnu i sporednu. Glavnu dijagonalu čine elementi uzeti u smjeru od gornjeg lijevog kuta determinante prema donjem desnom kutu. Bočna dijagonala - od gornjeg desnog do donjeg lijevog kuta. Determinanta drugog reda jednaka je umnošku elemenata glavne dijagonale minus umnošku elemenata sporedne dijagonale.