Punctul de intersecție al liniilor

Să ni se dea două drepte date de coeficienții lor și . Este necesar să găsiți punctul lor de intersecție sau să aflați că liniile sunt paralele.

Soluţie

Dacă două drepte nu sunt paralele, atunci se intersectează. Pentru a găsi punctul de intersecție, este suficient să compuneți un sistem de două ecuații de drepte și să îl rezolvați:

Folosind formula lui Cramer, găsim imediat o soluție la sistem, care va fi cea dorită punct de intersecție:

Dacă numitorul este zero, i.e.

atunci sistemul de soluții nu are (direct sunt paraleleși nu coincid) sau are infinit de multe (direct Meci). Dacă este necesar să se facă distincția între aceste două cazuri, este necesar să se verifice dacă coeficienții liniilor sunt proporționali cu același coeficient de proporționalitate ca și coeficienții și , pentru care este suficient să se calculeze doi determinanți, dacă ambii sunt egali. la zero, atunci liniile coincid:

Implementarea

struct pt (dublu x, y;); linie struct (dublu a, b, c;); constdouble EPS=1e-9; dublu det (dublu a, dublu b, dublu c, dublu d)(return a * d - b * c;) bool intersect (linia m, linia 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;}

Lecție din seria " Algoritmi geometrici»

Bună dragă cititoare.

Sfat 1: Cum să găsiți coordonatele punctului de intersecție a două linii

Să mai scriem trei funcții noi.

Funcția LinesCross() va determina dacă se intersectează fie că doi segment. În ea, poziția relativă a segmentelor este determinată folosind produse vectoriale. Pentru a calcula produsele vectoriale, să scriem o funcție - VektorMulti().

Funcția RealLess() va fi folosită pentru a implementa operația de comparare „<” (строго меньше) для вещественных чисел.

Sarcina 1. Două segmente sunt date de coordonatele lor. Scrieți un program care determină Aceste segmente se intersectează? fără a găsi punctul de intersecție.

Soluţie
. Al doilea este dat de puncte.

Se consideră un segment și puncte și .

Punctul se află în stânga dreptei, pentru care produsul vectorial > 0, deoarece vectorii sunt orientați pozitiv.

Punctul este situat în dreapta liniei, pentru el produsul vectorial < 0, так как векторы отрицательно ориентированы.

Pentru ca punctele și , să se afle pe părțile opuse ale dreptei , este suficient ca condiția< 0 (векторные произведения имели противоположные знаки).

Raționament similar poate fi efectuat pentru segment și puncte și .

Astfel, dacă , apoi segmentele se intersectează.

Pentru a verifica această condiție se folosește funcția LinesCross(), iar pentru calcularea produselor vectoriale se folosește funcția VektorMulti().

ax, ay sunt coordonatele primului vector,

bx, by sunt coordonatele celui de-al doilea vector.

Geometria programului4; (Se intersectează 2 segmente?) Const _Eps: Real=1e-4; (precizia calculului) var x1,y1,x2,y2,x3,y3,x4,y4: real; var v1,v2,v3,v4: real;funcție RealLess(Const a, b: Real): Boolean; (Strict mai puțin decât) begin RealLess:= b-a> _Eps end; (RealLess)funcție VektorMulti(ax,ay,bx,by:real): real; (ax,ay - a coordonate bx,by - b coordonate) begin vektormulti:= ax*by-bx*ay; final;Function LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real): boolean; (Se intersectează segmentele?) begin v1:=vektormulti(x4-x3,y4-y3,x1-x3,y1-y3); v2:=vectormulti(x4-x3,y4-y3,x2-x3,y2-y3); v3:=vectormulti(x2-x1,y2-y1,x3-x1,y3-y1); v4:=vectormulti(x2-x1,y2-y1,x4-x1,y4-y1); dacă 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.

Rezultatele executiei programului:

Introduceți coordonatele segmentelor: -1 1 2 2.52 2 1 -1 3
Da.

Am scris un program care determină dacă segmentele date de coordonatele lor se intersectează.

În lecția următoare, vom scrie un algoritm care poate fi folosit pentru a determina dacă un punct se află în interiorul unui triunghi.

Draga cititorule.

Ați citit deja câteva lecții din seria Algoritmi geometrici. Este totul disponibil scris? Vă voi fi foarte recunoscător dacă lăsați o recenzie despre aceste lecții. Poate că mai trebuie îmbunătățit ceva.

Cu stimă, Vera Gospodarets.

Să fie date două segmente. Primul este dat de puncte P 1 (x 1 ;y 1)și P 2 (x 2 ;y 2). Al doilea este dat de puncte P 3 (x 3 ;y 3)și P 4 (x 4 ;y 4).

Poziția relativă a segmentelor poate fi verificată folosind produse vectoriale:

Luați în considerare segmentul P 3 P 4și puncte P1și P2.

Punct P1 se află în stânga liniei P 3 P 4, pentru el produsul vectorial v1 > 0, deoarece vectorii sunt orientați pozitiv.
Punct P2 situat în dreapta liniei, pentru aceasta produsul vectorial v2< 0 , deoarece vectorii sunt orientați negativ.

La punctul P1și P2 stați pe părțile opuse ale unei linii drepte P 3 P 4, este suficient ca condiția v 1 v 2< 0 (produsele vectoriale aveau semne opuse).

Raționament similar poate fi efectuat pentru segment P 1 P 2și puncte P3și P4.

Astfel, dacă v 1 v 2< 0 și v 3 v 4< 0 , apoi segmentele se intersectează.

Produsul încrucișat a doi vectori se calculează cu formula:

Unde:
topor, Ay sunt coordonatele primului vector,
bx, de sunt coordonatele celui de-al doilea vector.

Ecuația unei drepte care trece prin două puncte diferite date de coordonatele lor.

Să fie date două puncte necoincidente pe o linie dreaptă: P1 cu coordonate ( x1;y1)și P2 cu coordonate (x 2 ; y 2).

Intersecția liniilor

În consecință, vectorul cu originea în punct P1și se termină într-un punct P2 are coordonate (x 2 -x 1, y 2 -y 1). În cazul în care un P(x, y) este un punct arbitrar pe linie, apoi coordonatele vectorului P 1 P egal (x - x 1, y - y 1).

Cu ajutorul produsului încrucișat, condiția de colinaritate a vectorilor P 1 Pși P 1 P 2 se poate scrie asa:
|P 1 P, P 1 P 2 |=0, adică (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
sau
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0

Ultima ecuație este rescrisă după cum urmează:
ax + by + c = 0, (1)
Unde
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)

Deci, linia dreaptă poate fi dată de o ecuație de forma (1).

Cum să găsiți punctul de intersecție al liniilor?
Soluția evidentă este rezolvarea sistemului de ecuații de drepte:

ax 1 +by 1 =-c 1
ax 2 +by 2 =-c 2 (2)

Introduceți denumiri:

Aici D este determinantul sistemului și D x ,D y sunt determinanții obținuți prin înlocuirea coloanei de coeficienți pentru necunoscuta corespunzătoare cu o coloană de termeni liberi. În cazul în care un D ≠ 0, atunci sistemul (2) este definit, adică are o soluție unică. Această soluție poate fi găsită folosind următoarele formule: x 1 \u003d D x / D, y 1 \u003d D y / D, care se numesc formulele lui Cramer. O mică reamintire a modului în care este calculat determinantul de ordinul doi. Determinantul distinge între două diagonale: principală și secundară. Diagonala principală este formată din elemente luate în direcția de la colțul din stânga sus al determinantului până la colțul din dreapta jos. Diagonala laterală - din dreapta sus la stânga jos. Determinantul de ordinul doi este egal cu produsul elementelor diagonalei principale minus produsul elementelor diagonalei secundare.

Să fie date două segmente. Primul este dat de puncte P 1 (x 1 ;y 1)și P 2 (x 2 ;y 2). Al doilea este dat de puncte P 3 (x 3 ;y 3)și P 4 (x 4 ;y 4).

Poziția relativă a segmentelor poate fi verificată folosind produse vectoriale:

Luați în considerare segmentul P 3 P 4și puncte P1și P2.

Punct P1 se află în stânga liniei P 3 P 4, pentru el produsul vectorial v1 > 0, deoarece vectorii sunt orientați pozitiv.
Punct P2 situat în dreapta liniei, pentru aceasta produsul vectorial v2< 0 , deoarece vectorii sunt orientați negativ.

La punctul P1și P2 stați pe părțile opuse ale unei linii drepte P 3 P 4, este suficient ca condiția v 1 v 2< 0 (produsele vectoriale aveau semne opuse).

Raționament similar poate fi efectuat pentru segment P 1 P 2și puncte P3și P4.

Astfel, dacă v 1 v 2< 0 și v 3 v 4< 0 , apoi segmentele se intersectează.

Produsul încrucișat a doi vectori se calculează cu formula:

Unde:
topor, Ay- coordonatele primului vector,
bx, de- coordonatele celui de-al doilea vector.

Ecuația unei drepte care trece prin două puncte diferite date de coordonatele lor.

Să fie date două puncte necoincidente pe o linie dreaptă: P1 cu coordonate ( x1;y1)și P2 cu coordonate (x 2 ; y 2). În consecință, vectorul cu originea în punct P1și se termină într-un punct P2 are coordonate (x 2 -x 1, y 2 -y 1). În cazul în care un P(x, y) este un punct arbitrar pe linie, apoi coordonatele vectorului P 1 P egal (x - x 1, y - y 1).

Cu ajutorul produsului încrucișat, condiția de colinaritate a vectorilor P 1 Pși P 1 P 2 se poate scrie asa:
|P1P,P1P2 |=0, adică (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
sau
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0

Ultima ecuație este rescrisă după cum urmează:
ax + by + c = 0, (1)
Unde
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)

Deci, linia dreaptă poate fi dată de o ecuație de forma (1).

Cum să găsiți punctul de intersecție al liniilor?
Soluția evidentă este rezolvarea sistemului de ecuații de drepte:

ax 1 +by 1 =-c 1
ax 2 +by 2 =-c 2 (2)

Introduceți denumiri:

Aici D este determinantul sistemului și D x ,D y sunt determinanții rezultați din înlocuirea coloanei de coeficienți pentru necunoscuta corespunzătoare cu o coloană de termeni liberi. În cazul în care un D ≠ 0, atunci sistemul (2) este definit, adică are o soluție unică. Această soluție poate fi găsită folosind următoarele formule: x 1 \u003d D x / D, y 1 \u003d D y / D, care se numesc formulele lui Cramer. O mică reamintire a modului în care este calculat determinantul de ordinul doi. Determinantul distinge între două diagonale: principală și secundară. Diagonala principală este formată din elemente luate în direcția de la colțul din stânga sus al determinantului până la colțul din dreapta jos. Diagonala laterală - din dreapta sus la stânga jos. Determinantul de ordinul doi este egal cu produsul elementelor diagonalei principale minus produsul elementelor diagonalei secundare.