Priesečník čiar

Dajme nám dve priamky dané ich koeficientmi a . Je potrebné nájsť ich priesečník, prípadne zistiť, či sú čiary rovnobežné.

Riešenie

Ak dve čiary nie sú rovnobežné, potom sa pretínajú. Na nájdenie priesečníka stačí zostaviť sústavu dvoch rovníc priamok a vyriešiť ju:

Pomocou Cramerovho vzorca okamžite nájdeme riešenie systému, ktoré bude požadované priesečník:

Ak je menovateľ nula, t.j.

potom systém riešení nemá (priamy sú paralelné a nezhodujú sa) alebo má nekonečne veľa (priamy zápas). Ak je potrebné tieto dva prípady rozlíšiť, je potrebné skontrolovať, či sú koeficienty úsečiek úmerné s rovnakým koeficientom úmernosti ako koeficienty a , pre ktoré stačí vypočítať dva determinanty, ak sú oba rovnaké. na nulu, potom sa čiary zhodujú:

Implementácia

štruktúra pt (dvojité x, y;); riadok štruktúry (dvojité a, b, c;); constdouble EPS=1e-9; double det (double a, double b, double c, double d)(return a * d - b * c;) bool intersect (priamka m, priamka 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;}

Lekcia zo seriálu " Geometrické algoritmy»

Dobrý deň, milý čitateľ.

Tip 1: Ako nájsť súradnice priesečníka dvoch čiar

Napíšme ďalšie tri nové funkcie.

Funkcia LinesCross() určí, či pretínajúči dva segment. V ňom sa relatívna poloha segmentov určuje pomocou vektorových produktov. Na výpočet vektorových produktov napíšme funkciu - VektorMulti().

Na implementáciu porovnávacej operácie sa použije funkcia RealLess() “<” (строго меньше) для вещественных чисел.

Úloha1. Dva segmenty sú dané ich súradnicami. Napíšte program, ktorý určí Pretínajú sa tieto segmenty? bez nájdenia priesečníka.

Riešenie
. Druhý je daný bodkami.

Zvážte segment a body a .

Bod leží naľavo od čiary, pre ktorú je vektorový súčin > 0, pretože vektory sú kladne orientované.

Bod sa nachádza napravo od čiary, je to vektorový súčin < 0, так как векторы отрицательно ориентированы.

Aby body a , ležali na opačných stranách čiary , stačí, aby bola splnená podmienka< 0 (векторные произведения имели противоположные знаки).

Podobné úvahy možno vykonať pre segment a body a .

Ak teda , potom sa segmenty pretínajú.

Na kontrolu tohto stavu slúži funkcia LinesCross() a na výpočet vektorových súčinov funkcia VektorMulti().

ax, ay sú súradnice prvého vektora,

bx, by sú súradnice druhého vektora.

Geometria programu4; (Pretínajú sa 2 segmenty?) Const _Eps: Real=1e-4; (presnosť výpočtu) var x1,y1,x2,y2,x3,y3,x4,y4: skutočné; var v1,v2,v3,v4: real;funkcia RealLess(Const a, b: Real): Boolean; (Striktne menej ako) begin RealLess:= b-a> _Eps end; (RealLess)function VektorMulti(ax,ay,bx,by:real): real; (ax,ay - a súradnice bx,by - b súradnice) begin vektormulti:= ax*by-bx*ay; end;Function LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real): boolean; (Pretínajú sa segmenty?) 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) a 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.

Výsledky spustenia programu:

Zadajte súradnice segmentov: -1 1 2 2,52 2 1 -1 3
Áno.

Napísali sme program, ktorý určí, či sa úseky dané ich súradnicami pretínajú.

V nasledujúcej lekcii napíšeme algoritmus, ktorý možno použiť na určenie, či bod leží vo vnútri trojuholníka.

Vážený čitateľ.

Už ste si prečítali niekoľko lekcií zo série Geometrické algoritmy. Je všetko dostupné napísané? Budem veľmi vďačný, ak zanecháte recenziu na tieto lekcie. Možno treba ešte niečo zlepšiť.

S pozdravom, Vera Gospodarets.

Nech sú uvedené dva segmenty. Prvý je daný bodkami P 1 (x 1 ;y 1) A P 2 (x 2 ;y 2). Druhý je daný bodkami P 3 (x 3 ;y 3) A P 4 (x 4 ;y 4).

Relatívnu polohu segmentov je možné skontrolovať pomocou vektorových produktov:

Zvážte segment P 3 P 4 a body P1 A P2.

Bodka P1 leží naľavo od čiary P 3 P 4, teda vektorový súčin v1 > 0, pretože vektory sú pozitívne orientované.
Bodka P2 umiestnený napravo od riadku, pre to vektorový súčin v2< 0 , pretože vektory sú negatívne orientované.

Ukázať P1 A P2 ležať na opačných stranách priamky P 3 P 4, stačí, aby bola splnená podmienka v 1 v 2< 0 (vektorové produkty mali opačné znamienka).

Podobné úvahy možno vykonať pre segment P 1 P 2 a body P3 A P4.

Ak teda v 1 v 2< 0 A v 3 v 4< 0 , potom sa segmenty pretínajú.

Krížový súčin dvoch vektorov sa vypočíta podľa vzorca:

Kde:
sekera, áno sú súradnice prvého vektora,
bx, podľa sú súradnice druhého vektora.

Rovnica priamky prechádzajúcej cez dva rôzne body dané ich súradnicami.

Nech sú na priamke dané dva nezhodné body: P1 so súradnicami ( x1;y1) A P2 so súradnicami (x 2; y 2).

Križovatka liniek

Podľa toho vektor s počiatkom v bode P1 a skončiť v bode P2 má súradnice (x 2 - x 1, y 2 - y 1). Ak P(x, y) je ľubovoľný bod na priamke, potom súradnice vektora P 1 P rovný (x - x 1, y - y 1).

Pomocou krížového súčinu podmienka kolinárnosti vektorov P 1 P A P 1 P 2 dá sa napísať takto:
|P1P,P1P2 |=0, t.j. (x-x 1)(y2-y1)-(y-y1)(x2-x1)=0
alebo
(y 2 - y 1) x + (x 1 - x 2) y + x 1 (y 1 - y 2) + y 1 (x 2 - x 1) = 0

Posledná rovnica je prepísaná takto:
ax + by + c = 0, (1)
Kde
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)

Takže priamka môže byť daná rovnicou v tvare (1).

Ako nájsť priesečník čiar?
Samozrejmým riešením je vyriešiť sústavu rovníc priamok:

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

Zadajte označenia:

Tu D je determinantom systému a D x, D y sú determinanty získané nahradením stĺpca koeficientov pre zodpovedajúcu neznámu stĺpcom voľných členov. Ak D ≠ 0, potom je systém (2) určitý, to znamená, že má jedinečné riešenie. Toto riešenie možno nájsť pomocou nasledujúcich vzorcov: x 1 \u003d D x / D, y 1 \u003d D y / D, ktoré sa nazývajú Cramerove vzorce. Malá pripomienka, ako sa počíta determinant druhého rádu. Determinant rozlišuje dve uhlopriečky: hlavnú a vedľajšiu. Hlavná diagonála pozostáva z prvkov v smere od ľavého horného rohu determinantu k pravému dolnému rohu. Bočná uhlopriečka - z pravého horného rohu do ľavého dolného rohu. Determinant druhého rádu sa rovná súčinu prvkov hlavnej uhlopriečky mínus súčin prvkov vedľajšej uhlopriečky.

Nech sú uvedené dva segmenty. Prvý je daný bodkami P 1 (x 1 ;y 1) A P 2 (x 2 ;y 2). Druhý je daný bodkami P 3 (x 3 ;y 3) A P 4 (x 4 ;y 4).

Relatívnu polohu segmentov je možné skontrolovať pomocou vektorových produktov:

Zvážte segment P 3 P 4 a body P1 A P2.

Bodka P1 leží naľavo od čiary P 3 P 4, teda vektorový súčin v1 > 0, pretože vektory sú pozitívne orientované.
Bodka P2 umiestnený napravo od riadku, pre to vektorový súčin v2< 0 , pretože vektory sú negatívne orientované.

Ukázať P1 A P2 ležať na opačných stranách priamky P 3 P 4, stačí, aby bola splnená podmienka v 1 v 2< 0 (vektorové produkty mali opačné znamienka).

Podobné úvahy možno vykonať pre segment P 1 P 2 a body P3 A P4.

Ak teda v 1 v 2< 0 A v 3 v 4< 0 , potom sa segmenty pretínajú.

Krížový súčin dvoch vektorov sa vypočíta podľa vzorca:

Kde:
sekera, áno- súradnice prvého vektora,
bx, podľa- súradnice druhého vektora.

Rovnica priamky prechádzajúcej cez dva rôzne body dané ich súradnicami.

Nech sú na priamke dané dva nezhodné body: P1 so súradnicami ( x1;y1) A P2 so súradnicami (x 2; y 2). Podľa toho vektor s počiatkom v bode P1 a skončiť v bode P2 má súradnice (x 2 - x 1, y 2 - y 1). Ak P(x, y) je ľubovoľný bod na priamke, potom súradnice vektora P 1 P rovný (x - x 1, y - y 1).

Pomocou krížového súčinu podmienka kolinárnosti vektorov P 1 P A P 1 P 2 dá sa napísať takto:
|P1P,P1P2 |=0, t.j. (x-x 1)(y2-y1)-(y-y1)(x2-x1)=0
alebo
(y 2 - y 1) x + (x 1 - x 2) y + x 1 (y 1 - y 2) + y 1 (x 2 - x 1) = 0

Posledná rovnica je prepísaná takto:
ax + by + c = 0, (1)
Kde
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)

Takže priamka môže byť daná rovnicou v tvare (1).

Ako nájsť priesečník čiar?
Samozrejmým riešením je vyriešiť sústavu rovníc priamok:

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

Zadajte označenia:

Tu D je determinantom systému a D x, D y sú determinanty vyplývajúce z nahradenia stĺpca koeficientov pre zodpovedajúcu neznámu stĺpcom voľných členov. Ak D ≠ 0, potom je systém (2) určitý, to znamená, že má jedinečné riešenie. Toto riešenie možno nájsť pomocou nasledujúcich vzorcov: x 1 \u003d D x / D, y 1 \u003d D y / D, ktoré sa nazývajú Cramerove vzorce. Malá pripomienka, ako sa počíta determinant druhého rádu. Determinant rozlišuje dve uhlopriečky: hlavnú a vedľajšiu. Hlavná diagonála pozostáva z prvkov v smere od ľavého horného rohu determinantu k pravému dolnému rohu. Bočná uhlopriečka - z pravého horného rohu do ľavého dolného rohu. Determinant druhého rádu sa rovná súčinu prvkov hlavnej uhlopriečky mínus súčin prvkov vedľajšej uhlopriečky.