Ուղիղների հատում

Ուղիղների հատում

Էվկլիդեսյան երկրաչափությունում երկու ուղիղների հատումը կարող է լինել դատարկ բազմություն, կետ կամ ուղիղ։ Այդ դեպքերի տարբերությունը և հատման կետի որոնումը օգտագործվում է, օրինակ համակարգչային գրաֆիկայում, շարժման պլանավորման և բախման հայտնաբերման ժամանակ։

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

Ոչ էվկլիդեսյան երկրաչափությունում երկու ուղիղներ կարող են հատվել մի քանի կետերում և տվյալ ուղղի հետ չհատվող (զուգահեռ) ուղիղների թիվը կարող է լինել մեկից շատ։

Երկու ուղիղների հատում

Երկու ուղիղների հատման անհրաժեշտ պայաման է հանդիսանում նրանց մեկ հարթության պատկանելը, այսինքն այդ ուղիղները չպիտի խաչվող լինեն։ Այս պայմանի տեղի ունենալը համարժեք է տետրաեդրի այլափոխմանը, որի երկու գագաթներըն ընկած են մի ուղղի վրա, իսկ հաջորդ երկուսը՝ հաջորդի (այսինքն, այդ տետրաեդրի ծավալը հավասար է 0-ի)։

Եթե յուրաքանչյուր ուղղի վրա տրված է երկու կետ

Դիտարկենք $L_{1}\,$ և $L_{2}\,$ երկու ուղիղների հատումը հարթության վրա, որտեղна $L_{1}\,$ ուղիղը որոշված է երկու՝ $(x_{1},y_{1})\,$ և $(x_{2},y_{2})\,$ տարբեր կետերով, իսկ $L_{2}\,$ ուղիղը՝ $(x_{3},y_{3})\,$ և $(x_{4},y_{4})\,$ տարբեր կետերով։

$L_{1}\,$ և $L_{2}\,$ ուղիղների $P\,$ հատման կետը կարելի է գտնել որոշչի օնությամբ։

$P_{x}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}&{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4}&y_{4}\end{vmatrix}}&{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}}\,\!\qquad P_{y}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4}&y_{4}\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}}\,\!$

Որոշիչը կարելի է արտագրել

${\begin{aligned}(P_{x},P_{y})={\bigg (}&{\frac {(x_{1}y_{2}-y_{1}x_{2})(x_{3}-x_{4})-(x_{1}-x_{2})(x_{3}y_{4}-y_{3}x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}},\\&{\frac {(x_{1}y_{2}-y_{1}x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}y_{4}-y_{3}x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}{\bigg )}\end{aligned}}$

տեսքով։

Նկատենք, որ հատման կետը վերաբերվում է անվերջ ուղիղներին, այլ ոչ թե երկու կետերի միջև հատվածին, և այն կարող է ընկած լինել հատվածներից դուրս։ Եթե (մեկ քայլով գտնելու փոխարեն) լուծումը որոնել Բեզեի առաջին կարգի կորերի տերմինաբանությամբ, ապա կարելի է ստուգել այդ կորերի պարամետրերը 0.0 ≤ t ≤ 1.0 и 0.0 ≤ u ≤ 1.0 (t և u-ն պարամետրեր են)։

Եթե երկու ուղիղներ զուգահեռ են կամ համընկնում են, հայտարարը վերածվում է զրոյի.

$(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})=0:$

Եթե ուղիղները շատ մոտ են զուգահեռության (գրեթե զուգահեռ են), համակարգչում հաշվարկման ժամանակկարող են ի հայտ գալ թվային խնդիրներ և այդպիսի պայմանի ճանաչումը կիրառման համար կարող է պահանջել «անորոշության» համապատախան թեստ։

Եթե տրված են ուղիղների հավասարումները

Երկու ոչ ուղղահայաց ուղեղների հատման կետի $x$ և $y$ կոորդինատները կարելի է հեշտությամբ գտնել հետևյալ ներկայացումների և ձևափոխությունների օգնությամբ։

Ենթադրենք, որ երկու ուղիղներն ունեն $y=ax+c$ և $y=bx+d$, հավասարումները, որտեղ $a$ և $b$ -ն ուղիղների անկյունային գործակիցներն են, իսկ $c$ և $d$ -ն՝ ուղիղների հատումները y առանցքի հետ։ Ուղիղների հատման կետում (եթե նրանք հատվում են), երկու $y$ կոորդինատները կհամընկնեն, որտեղից ստանում ենք

$ax+c=bx+d$

հավասարությունը։

$x$ դուրս բերելու համար մենք այս հավասարությունը կարող ենք ձևափոխել՝

$ax-bx=d-c$,

այստեղից էլ՝

$x={\frac {d-c}{a-b}}$:

Որպեսզի գտնենք y կոորդինատը, x-ի արժեքը տեղադրենք ուղիղների բանաձևերից մեկի մեջ, օրինակ՝ առաջինի.

$y=a{\frac {d-c}{a-b}}+c$:

Այստեղից ստանում ենք ուղիղների հատման կետը.

$P\left({\frac {d-c}{a-b}},a{\frac {d-c}{a-b}}+c\right)=P\left({\frac {d-c}{a-b}},{\frac {ad-bc}{a-b}}\right)$:

Նկատենք, որ a = b դեպքում երկու ուղիղները զուգահեռ են։ Եթե այդ դեպքում c ≠ d, ուղիղները տերբեր են և չունեն հատման կետ, հակառակ դեպքում ուղիղները համընկնում են։

Համասեռ կոորդինատների օգտագործում

Համասեռ կոորդինատների օգտագործման ժամանակ երկու հստակ տրված ուղիղների հատման կետը կարող է գտնվել հեշտությամբ։ Երկչափ տարածությունում յուրաքանչյուր կետ կարող է որոշվել որպես $(x,y,w)$ եռաչափ կետի պրոյեկցիա։ Եռաչափ կոորդինատների արտապատկերումը երկչափի տեղի է ունենում $(x',y')=(x/w,y/w)$ բանաձևով։ Երրորդ կոորդինատը միավորի հավասարեցնելով մենք կարող ենք երկչափ տարածությունում կետերը ձևափոխել համասեռ կոորդինատների՝ $(x,y,1)$:

Ենթադրենք, որ մենք ուզում ենք գտնել երկու անվերջ ուղիղների հատումը երկչափ տարածությունում, որոնք տրված են $a_{1}x+b_{1}y+c_{1}=0$ և $a_{2}x+b_{2}y+c_{2}=0$ բանաձևերով։ Այդ երկու ուղիղները մենք կարող ենք ներկայացնել գծային կոորդինատներով՝ $U_{1}=(a_{1},b_{1},c_{1})$ և $U_{2}=(a_{2},b_{2},c_{2})$:

Երկու ուղիղների $P'$ հատումն այդ դեպքում պարզապես տրվում է հետևյալ բանաձևերով.

$P'=(a_{p},b_{p},c_{p})=U_{1}\times U_{2}=(b_{1}c_{2}-b_{2}c_{1},a_{2}c_{1}-a_{1}c_{2},a_{1}b_{2}-a_{2}b_{1})$

Եթե $c_{p}=0$, ուղիղները չեն հատվում։

n ուղիղների հատում

Հատման գոյությունն ու արտահայտությունը

Երկչափ տարածությունում

Երկչափ տարածությունում երկուսից ավել ուղիղները գրեթե ճշգրիտ չեն հատվում մեկ կետում։ Որպեսզի որոշենք, թե հատվում են նրանք արդյոք մի կետում, և, եթե հատվում են, որպեսզի գտնենք հատման կետը i-րդ հավասարումը (i = 1, ...,n) գրենք որպես $(a_{i1}\quad a_{i2})(x\quad y)^{T}=b_{i},$ և այդ հավասարումները կցակազմենք մատրիցային տեսքով՝

$Aw=b,$

որտեղ n × 2 չափի A մատրիցի i-րդ տողը հավասար է $(a_{i1},a_{i2})$, w-ն հանդիսանում է (x, y)^T -ի 2 × 1 վեկտորը, իսկ b սյունակ-վեկտրի i-րդ անդամը հավասար է b_i : Եթե A մատրիցի սյունակներն անկախ են, ապա մատրիցի ռանգը հավասար է 2։ Այն և միայն այն դեպքում, երբ [A | b ] ընդլայնված մատրիցի ռանգը ևս 2 է, գոյություն ունի մատրիցային հավասարմամբ լուծում, այդ դեպքում գոյություն ունի նաև n ուղիղների հատման կետը։ Հատման կետը, եթե այդպիսին գոյություն ունի, տրվում է

$w=A^{g}b=(A^{T}A)^{-1}A^{T}b,$

բանաձևով, որտեղ $A^{g}$ -ն $A$ մատրիցի կեղծ հակադարձ մատրիցան է։ Այլընտրանքային լուծումը կարող է գտնվել կամայական երկու անկախ հավասարումների լուծման ճանապարհով։ Բայց, եթե A մատրիցի ռանգը հավասար է 1, իսկ ընդլայնված մատրիցի ռանգը հավասար է 2, լուծում չունի։ Իսկ, երբ ընդլայնված մատրիցի ռանգը հավասար է 1, ապա բոլոր ուղիղները համընկնում են։

Եռաչափ տարածությունում

Վերևում ներկայացված մոտեցումը հյեշտությամբ տարածվում է նաև եռաչափ տարածության վրա։ Եռաչափ և ավելի բարձր չափողականությամբ տարածություններում նույնիսկ երկու ուղիղները հավանաբար չեն հատվում։ Ոչ զուգահեռ և չհատվող ուղիղների զույգը կոչվում է խաչվող։ Բայց, երբ հատումը գոյություն ունի, այն կարելի է գտնել հետևյալ կերպ։

Եռաչափ տարածությունում ուղիղը ներկայացվում է երկու հարթությունների հատմամբ, որոնցից յուրաքանչյուրը տրվում է $(a_{i1}\quad a_{i2}\quad a_{i3})(x\quad y\quad z)^{T}=b_{i}$ բանաձևով։ Այդ դեպքում n ուղիղների բազմությունը կարող է ներկայացվել 2n հավասարումների տեսքով՝ w = (x, y, z)^T եռաչափ կոորդինատային վեկտրներից

$Aw=b$,

որտեղ A -ն՝ 2n × 3 չափի մատրից է, իսկ b-ն՝ 2n × 1: Ինչպես և առաջ, հատման միակ կետը գոյություն ունի այն և միայն այն դեպքում, երբ A մատրիցն ունի ըստ սյուների լրիվ ռանգ, իսկ մատրիցի [A | b ] ընդլայնումը այդպիսին չի հանդիսանում։ Հատման միակ կետը, եթե գոյություն ունի, տրվում է

$w=(A^{T}A)^{-1}A^{T}b$

բանաձևով։

Չհատվող ուղիղներին մոտ կետ

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

Երկչափ տարածությունում

Երկչափ տարածության դեպքում i ուղիղը ներկայացնենք որպես ուղղի վրա $p_{i}$ կետ և ուղղին ուղղահայաց ${\hat {n}}_{i}$ միավոր նորմալը։ Այսինքն, եթե $x_{1}$-ը և $x_{2}$-ը 1 ուղղի կետեր են, ապա թող $p_{1}=x_{1}$ և

${\hat {n}}_{1}:={\begin{bmatrix}0&-1\\1&0\end{bmatrix}}(x_{2}-x_{1})/\|x_{2}-x_{1}\|$,

որը հանդիսանում է ուղղի երկայնքով միավոր վեկտոր, շրջած 90º-ով։

Նկատենք, որ հեռավորությունը x կետից մինչև $(p,{\hat {n}})$ ուղիղը տրվում է հետևյալ բանաձևով.

$d(x,(p,n))=\|(x-p)\cdot {\hat {n}}\|=\|(x-p)^{\top }{\hat {n}}\|={\sqrt {(x-p)^{\top }{\hat {n}}{\hat {n}}^{\top }(x-p)}}:$

Հետևաբար, x-ից մինչև ուղիղ հեռավորության քառակուսին հավասար է

$d(x,(p,n))^{2}=(x-p)^{\top }({\hat {n}}{\hat {n}}^{\top })(x-p):$

Մինչև ուղիղների խումբը հեռավորության քառակուսիների գումարը հանդիասանում է օբյեկտիվ ֆունկցիա.

$E(x)=\sum _{i}(x-p_{i})^{\top }({\hat {n}}_{i}{\hat {n}}_{i}^{\top })(x-p_{i}):$

Արտահայտությունը կարելի է ձևափոխել.

${\begin{aligned}E(x)&=\sum _{i}x^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }x-x^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}-p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }x+p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\\&=x^{\top }\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)x-2x^{\top }\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right)+\sum _{i}p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}:\end{aligned}}$

Մինիմումը գտնելու համար ածանցում ենք ըստ x-ի և արդյունքը հավասարեցնում զրոյի.

${\frac {\partial E(x)}{\partial x}}=0=2\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)x-2\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right)$

Այսպիսով,

$\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)x=\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}$,

որտեղից

$x=\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)^{-1}\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right):$

Եռաչափ տարածությունում

Չնայած, երկուսից բարձր չափողականությամբ տարածություններում ${\hat {n}}_{i}$ նորմալները չեն կարող որոշվել, դա կարելի է ընդհանրացնել ցանկացած չափողականության տարածության հետ, եթե նշենք, որ ${\hat {n}}_{i}{\hat {n}}_{i}^{\top }$ հանդիսանում է պարզապես (համաչափ) մատրիցա իր բոլոր սեփական միավորի հավասար նշանակություններով, բացառապես ուղղի երկայնքով զրոյական սեփական նշանակության, ինչը տալիս է $p_{i}$ կետի և մեկ այլ կետի միջև կիսանորմ։ Կամայական չափողականությամբ տարածության մեջ, ${\hat {v}}_{i}$-ն հանդիսանում է միավոր վեկտոր i-րդ ուղղի երկայնքով, ապա

${\hat {n}}_{i}{\hat {n}}_{i}^{\top }$-ն վերածվում է $E-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }$,

որտեղ E -ն միավոր մատրից է, հետևաբար.

$x=\left(\sum _{i}E-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }\right)^{-1}\left(\sum _{i}(E-{\hat {v}}_{i}{\hat {v}}_{i}^{\top })p_{i}\right):$

Գրականություն

• Б. Н. Делоне, Д. А. Райков Аналитическая геометрия. — М., Л.: ОГИЗ, Государственнон издательство технико-теоретической литературы, 1948. — Т. 1.

Արտաքին հղումներ

• Distance between Lines and Segments with their Closest Point of Approach Արխիվացված 2012-02-27 Wayback Machine, կիրառելի է երկչափ, եռաչափ կամ ավելի բարձր չափողականությամբ տարածություններում։