Գծերի հատման կետ

Մեզ տրվի երկու ուղիղ՝ տրված նրանց գործակիցներով և . Պահանջվում է գտնել դրանց հատման կետը կամ պարզել, որ գծերը զուգահեռ են:

Որոշում

Եթե ​​երկու ուղիղները զուգահեռ չեն, ուրեմն հատվում են։ Խաչմերուկի կետը գտնելու համար բավական է կազմել երկու ուղիղների հավասարումների համակարգ և լուծել այն.

Օգտագործելով Cramer-ի բանաձեւը, մենք անմիջապես գտնում ենք համակարգի լուծումը, որը կլինի ցանկալի հատման կետ:

Եթե ​​հայտարարը զրո է, այսինքն.

ապա լուծումների համակարգը չունի (ուղղ զուգահեռ ենև չեն համընկնում) կամ ունի անսահման շատ (ուղղ համընկնում) Եթե ​​անհրաժեշտ է տարբերակել այս երկու դեպքերը, ապա անհրաժեշտ է ստուգել, ​​որ տողերի գործակիցները համամասնական են նույն համաչափության գործակիցով, ինչ գործակիցները, և որի համար բավական է հաշվարկել երկու որոշիչ, եթե երկուսն էլ հավասար են. զրոյի, ապա տողերը համընկնում են.

Իրականացում

struct pt (կրկնակի x, y;); struct line (կրկնակի a, b, c;); constdoble 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);եթե(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, ըստ են երկրորդ վեկտորի կոորդինատները:

Ծրագրի երկրաչափություն4; (Արդյո՞ք 2 հատված հատվում են:) Const _Eps: Real=1e-4; (հաշվարկի ճշգրտություն) var x1,y1,x2,y2,x3,y3,x4,y4՝ իրական; var v1,v2,v3,v4. իրական;գործառույթ RealLess(Const a, b: Real): Բուլյան; (Խիստ ավելի քիչ, քան) begin RealLess:= b-a> _Eps end; (RealLess) ֆունկցիա VektorMulti(ax,ay,bx,by:real): իրական; (ax,ay - a կոորդինատներ bx,by - b կոորդինատներ) start vektormulti:= ax*by-bx*ay; վերջ;Function LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real): բուլյան; (հատվածները հատվու՞մ են:) 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); եթե 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և միավորներ P1և P2.

Կետ P1ընկած է գծի ձախ կողմում P 3 P 4, դրա համար վեկտորի արտադրյալը v1 > 0, քանի որ վեկտորները դրական կողմնորոշված ​​են։
Կետ P2գտնվում է գծի աջ կողմում, դրա համար վեկտորային արտադրյալը v2< 0 , քանի որ վեկտորները բացասական կողմնորոշված ​​են։

Նշելու համար P1և P2պառկել ուղիղ գծի հակառակ կողմերում P 3 P 4, բավական է, որ պայման v 1 v 2< 0 (վեկտորային արտադրանքներն ունեին հակառակ նշաններ):

Նմանատիպ պատճառաբանություն կարող է իրականացվել հատվածի համար P 1 P 2և միավորներ P3և P4.

Այսպիսով, եթե v 1 v 2< 0 և v 3 v 4< 0 , ապա հատվածները հատվում են։

Երկու վեկտորների խաչաձև արտադրյալը հաշվարկվում է բանաձևով.

որտեղ:
կացին, այառաջին վեկտորի կոորդինատներն են,
bx, կողմիցերկրորդ վեկտորի կոորդինատներն են։

Երկու տարբեր կետերով անցնող ուղիղ գծի հավասարումը, որը տրված է դրանց կոորդինատներով:

Թող ուղիղ գծի վրա տրվեն երկու ոչ համընկնող կետեր. P1կոորդինատներով ( x1;y1)և P2կոորդինատներով (x 2 ; y 2).

Գծի խաչմերուկ

Համապատասխանաբար, կետում ծագմամբ վեկտորը P1և ավարտվում է մի կետով P2ունի կոորդինատներ (x 2 -x 1, y 2 -y 1). Եթե P (x, y)գծի կամայական կետ է, ապա վեկտորի կոորդինատները Պ 1 Պհավասար (x - x 1, y - y 1):

Խաչաձև արտադրյալի օգնությամբ վեկտորների համակցվածության պայման Պ 1 Պև 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

Վերջին հավասարումը վերաշարադրվում է հետևյալ կերպ.
կացին + ըստ + գ = 0, (1)
որտեղ
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)

Այսպիսով, ուղիղ գիծը կարող է տրվել (1) ձևի հավասարմամբ:

Ինչպե՞ս գտնել գծերի հատման կետը:
Ակնհայտ լուծումը ուղիղների հավասարումների համակարգը լուծելն է.

կացին 1 +ըստ 1 =-c 1
կացին 2 +ըստ 2 =-c 2 (2)

Մուտքագրեք նշանակումները.

Այստեղ Դհամակարգի որոշիչն է, և D x, D yայն որոշիչներն են, որոնք ստացվում են՝ համապատասխան անհայտի գործակիցների սյունակը ազատ անդամներով սյունակով փոխարինելով: Եթե D ≠ 0, ապա համակարգը (2) որոշակի է, այսինքն՝ ունի յուրահատուկ լուծում։ Այս լուծումը կարելի է գտնել հետևյալ բանաձևերի միջոցով. x 1 \u003d D x / D, y 1 \u003d 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և միավորներ P1և P2.

Կետ P1ընկած է գծի ձախ կողմում P 3 P 4, դրա համար վեկտորի արտադրյալը v1 > 0, քանի որ վեկտորները դրական կողմնորոշված ​​են։
Կետ P2գտնվում է գծի աջ կողմում, դրա համար վեկտորային արտադրյալը v2< 0 , քանի որ վեկտորները բացասական կողմնորոշված ​​են։

Նշելու համար P1և P2պառկել ուղիղ գծի հակառակ կողմերում P 3 P 4, բավական է, որ պայման v 1 v 2< 0 (վեկտորային արտադրանքներն ունեին հակառակ նշաններ):

Նմանատիպ պատճառաբանություն կարող է իրականացվել հատվածի համար P 1 P 2և միավորներ P3և P4.

Այսպիսով, եթե v 1 v 2< 0 և v 3 v 4< 0 , ապա հատվածները հատվում են։

Երկու վեկտորների խաչաձև արտադրյալը հաշվարկվում է բանաձևով.

որտեղ:
կացին, այ- առաջին վեկտորի կոորդինատները,
bx, կողմից- երկրորդ վեկտորի կոորդինատները:

Երկու տարբեր կետերով անցնող ուղիղ գծի հավասարումը, որը տրված է դրանց կոորդինատներով:

Թող ուղիղ գծի վրա տրվեն երկու ոչ համընկնող կետեր. P1կոորդինատներով ( x1;y1)և P2կոորդինատներով (x 2 ; y 2). Համապատասխանաբար, կետում ծագմամբ վեկտորը P1և ավարտվում է մի կետով P2ունի կոորդինատներ (x 2 -x 1, y 2 -y 1). Եթե P (x, y)գծի կամայական կետ է, ապա վեկտորի կոորդինատները Պ 1 Պհավասար (x - x 1, y - y 1):

Խաչաձև արտադրյալի օգնությամբ վեկտորների համակցվածության պայման Պ 1 Պև 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

Վերջին հավասարումը վերաշարադրվում է հետևյալ կերպ.
կացին + ըստ + գ = 0, (1)
որտեղ
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)

Այսպիսով, ուղիղ գիծը կարող է տրվել (1) ձևի հավասարմամբ:

Ինչպե՞ս գտնել գծերի հատման կետը:
Ակնհայտ լուծումը ուղիղների հավասարումների համակարգը լուծելն է.

կացին 1 +ըստ 1 =-c 1
կացին 2 +ըստ 2 =-c 2 (2)

Մուտքագրեք նշանակումները.

Այստեղ Դհամակարգի որոշիչն է, և D x, D yհամապատասխան անհայտի գործակիցների սյունակը ազատ անդամներով սյունակով փոխարինելու արդյունքում առաջացող որոշիչներն են: Եթե D ≠ 0, ապա համակարգը (2) որոշակի է, այսինքն՝ ունի յուրահատուկ լուծում։ Այս լուծումը կարելի է գտնել հետևյալ բանաձևերի միջոցով. x 1 \u003d D x / D, y 1 \u003d D y / D, որոնք կոչվում են Կրամերի բանաձեւեր։ Մի փոքր հիշեցում, թե ինչպես է հաշվարկվում երկրորդ կարգի որոշիչը: Որոշիչը տարբերում է երկու անկյունագծեր՝ հիմնական և երկրորդական: Հիմնական անկյունագիծը բաղկացած է տարրերից, որոնք վերցված են որոշիչի վերին ձախ անկյունից դեպի ստորին աջ անկյուն ուղղությամբ: Կողքի անկյունագիծ - վերին աջից դեպի ներքևի ձախ: Երկրորդ կարգի որոշիչը հավասար է հիմնական անկյունագծի տարրերի արտադրյալին` հանած երկրորդական անկյունագծի տարրերի արտադրյալը: