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

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

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

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

## Երկու ուղիղների հատում
Երկու ուղիղների հատման անհրաժեշտ պայաման է հանդիսանում նրանց մեկ հարթության պատկանելը, այսինքն այդ ուղիղները չպիտի խաչվող լինեն։ Այս պայմանի տեղի ունենալը համարժեք է տետրաեդրի այլափոխմանը, որի երկու գագաթներըն ընկած են մի ուղղի վրա, իսկ հաջորդ երկուսը՝ հաջորդի (այսինքն, այդ տետրաեդրի ծավալը հավասար է 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{align}
(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{align}


տեսքով։

Նկատենք, որ հատման կետը վերաբերվում է անվերջ ուղիղներին, այլ ոչ թե երկու կետերի միջև հատվածին, և այն կարող է ընկած լինել հատվածներից դուրս։ Եթե (մեկ քայլով գտնելու փոխարեն) լուծումը որոնել Բեզեի առաջին կարգի կորերի տերմինաբանությամբ, ապա կարելի է ստուգել այդ կորերի պարամետրերը  0.0&nbsp;≤&nbsp;*t*&nbsp;≤&nbsp;1.0 и 0.0&nbsp;≤&nbsp;*u*&nbsp;≤&nbsp;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_1x + b_1y + c_1 = 0 և a_2x + b_2y + 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^gb=(A^TA)^{-1}A^Tb,

բանաձևով, որտեղ A^g -ն A մատրիցի կեղծ հակադարձ մատրիցան է։ Այլընտրանքային լուծումը կարող է գտնվել կամայական երկու անկախ հավասարումների լուծման ճանապարհով։ Բայց, եթե *A* մատրիցի ռանգը հավասար է 1, իսկ ընդլայնված մատրիցի ռանգը հավասար է 2, լուծում չունի։ Իսկ, երբ ընդլայնված մատրիցի ռանգը հավասար է 1, ապա բոլոր ուղիղները համընկնում են։ 
#### Եռաչափ տարածությունում
Վերևում ներկայացված մոտեցումը հյեշտությամբ տարածվում է նաև եռաչափ տարածության վրա։ Եռաչափ և ավելի բարձր չափողականությամբ տարածություններում նույնիսկ երկու ուղիղները հավանաբար չեն հատվում։ Ոչ զուգահեռ և չհատվող ուղիղների զույգը կոչվում է խաչվող։ Բայց, երբ հատումը գոյություն ունի, այն կարելի է գտնել հետևյալ կերպ։

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

Aw=b,

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

:w = (A^TA)^{-1}A^Tb
բանաձևով։

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

#### Երկչափ տարածությունում
Երկչափ տարածության դեպքում *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{align}
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 - 2 x^\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{align}


Մինիմումը գտնելու համար ածանցում ենք ըստ *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):

## Ծանոթագրություններ

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

## Արտաքին հղումներ
* Distance between Lines and Segments with their Closest Point of Approach , կիրառելի է երկչափ, եռաչափ կամ ավելի բարձր չափողականությամբ տարածություններում։

Կատեգորիա:Գծային հանրահաշիվ
Կատեգորիա:Երկրաչափական ալգորիթմներ
Կատեգորիա:Էվկլիդեսյան երկրաչափություն