Křižovatka čar

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 13. října 2020; kontroly vyžadují 2 úpravy .

V euklidovské geometrii může být průsečíkem dvou přímek prázdná množina , bod nebo přímka. Rozlišení těchto případů a nalezení průsečíku se využívá například v počítačové grafice , při plánování pohybu a při detekci kolizí .

Pokud v trojrozměrné euklidovské geometrii nejsou dvě přímky ve stejné rovině , nazývají se šikmé a nemají žádné průsečíky. Pokud jsou čáry ve stejné rovině, existují tři možnosti. Pokud se shodují, mají nekonečně mnoho společných bodů (jmenovitě všechny body na těchto přímkách). Pokud jsou čáry odlišné, ale mají stejný sklon , jsou rovnoběžné a nemají žádné společné body. Jinak mají jeden průsečík.

V neeuklidovské geometrii se dvě přímky mohou protínat v několika bodech a počet dalších přímek (paralelních), které se s danou přímkou neprotínají, může být větší než jedna.

Průsečík dvou čar

Nezbytnou podmínkou pro průnik dvou přímek je, že patří do stejné roviny, to znamená, že by se tyto přímky neměly protínat. Splnění této podmínky je ekvivalentní degeneraci čtyřstěnu , ve kterém dva vrcholy leží na jedné přímce a další dva leží na druhé (tj . objem tohoto čtyřstěnu je roven nule). Algebraický tvar této podmínky naleznete v článku " Kontrola křížení ".

Jsou dány dva body na každé přímce

Uvažujme průsečík dvou přímek a na rovině, kde přímka je definována dvěma různými body a , a přímka je definována různými body a [1] . $L_{1}\,$ $L_{2}\,$ $L_{1}\,$ $(x_{1},y_{1})\,$ $(x_{2},y_{2})\,$ $L_{2}\,$ $(x_{3},y_{3})\,$ $(x_{4},y_{4})\,$

Průsečík čar a lze nalézt pomocí determinantů . $P\,$ $L_{1}\,$ $L_{2}\,$

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}}}\,\!

Determinanty lze přepsat takto:

{\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}}

Všimněte si, že průsečík odkazuje na nekonečné čáry, nikoli na úsečky mezi body, a může ležet mimo úsečky. Pokud (místo řešení v jednom kroku) hledáme řešení z hlediska Bézierových křivek prvního řádu , pak můžeme zkontrolovat parametry těchto křivek 0,0 ≤ t ≤ 1,0 a 0,0 ≤ u ≤ 1,0 ( t a u jsou parametry) .

Pokud jsou dvě čáry rovnoběžné nebo shodné, jmenovatel zmizí:

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

Pokud jsou čáry velmi blízko rovnoběžnosti (téměř rovnoběžné), mohou při výpočtu počítače nastat numerické problémy a rozpoznání takové podmínky může vyžadovat vhodný test "nejistoty" pro aplikaci. Stabilnější a obecnější řešení lze získat otočením segmentů takovým způsobem, že se jeden z nich stane vodorovným, a pak lze snadno získat parametrické řešení druhé přímky. Při řešení je nutné pečlivé zohlednění speciálních případů (rovnoběžnost/shoda přímek, překrývání segmentů).

Pokud jsou uvedeny rovnice přímek

Souřadnice a průsečíky dvou nevertikálních čar lze snadno najít pomocí následujících substitucí a transformací. $X$ $y$

Předpokládejme, že dvě přímky mají rovnice a , kde a jsou sklony čar a a jsou průsečíky čar s osou y . V průsečíku čar (pokud se protínají) budou obě souřadnice shodné, z čehož získáme rovnost: $y=ax+c$ $y=bx+d$ $A$ $b$ $C$ $d$ $y$

ax+c=bx+d

Tuto rovnost můžeme transformovat, abychom zdůraznili , $X$

ax-bx=dc

a pak

x={\frac {dc}{ab}}

Abychom našli souřadnici y , vše, co musíme udělat, je zapojit hodnotu x do jednoho z řádkových vzorců, jako je ten první:

y=a{\frac {dc}{ab}}+c

Odtud dostaneme průsečík čar

P\left({\frac {dc}{ab)),a{\frac {dc}{ab))+c\right)=P\left({\frac {dc}{ab)), {\frac {ad-bc}{ab}}\right)

Všimněte si, že pro a = b jsou dvě přímky rovnoběžné. Jestliže zároveň c ≠ d , jsou přímky různé a nemají průsečíky, jinak se přímky shodují [2] .

Použití homogenních souřadnic

Při použití homogenních souřadnic lze zcela jednoduše najít průsečík dvou explicitně daných čar. Ve 2-rozměrném prostoru lze libovolný bod definovat jako projekci 3-rozměrného bodu daného trojitým . Mapování 3-rozměrných souřadnic na 2-rozměrné probíhá podle vzorce . Body ve 2-rozměrném prostoru můžeme převést na homogenní souřadnice tak, že třetí souřadnici přirovnáme k jedné - . $(x,y,w)$ $(x',y')=(x/w,y/w)$ $(x,y,1)$

Předpokládejme, že chceme najít průsečík dvou nekonečných čar ve 2-rozměrném prostoru, které jsou dány vzorci a . Tyto dvě čáry můžeme reprezentovat v lineárních souřadnicích jako , $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})$

Průsečík dvou přímek je pak jednoduše dán vzorci [3] $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})$

Pokud , čáry se neprotínají. $c_{p}=0$

Průsečík n čar

Existenční a průnikový výraz

Ve dvou rozměrech

Ve dvourozměrném prostoru se čáry s více než dvěma téměř jistě neprotínají v jednom bodě. Abychom určili, zda se protínají v jednom bodě, a pokud se protínají, abychom našli průsečík, napíšeme i -tou rovnici ( i = 1, ..., n ) jako a uspořádáme tyto rovnice do maticového tvaru $(a_{i1}\quad a_{i2})(x\quad y)^{T}=b_{i},$

Aw=b,

kde i -tý řádek matice n × 2 A je , w je vektor 2 × 1 ( x, y ) T a i -tý prvek sloupcového vektoru b je b i . Pokud jsou sloupce matice A nezávislé, pak je hodnost matice 2. Právě tehdy, když je hodnost rozšířené matice [ A | b ] je také rovno 2, existuje řešení maticové rovnice a pak také průsečík n přímek. Průsečík, pokud existuje, je dán pomocí $(a_{i1},a_{i2})$

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

kde je pseudoinverze matice . Alternativně lze řešení nalézt řešením libovolných dvou nezávislých rovnic. Ale pokud je hodnost matice A 1 a hodnost rozšířené matice je 2, neexistují žádná řešení. V případě, že je hodnost rozšířené matice rovna 1, všechny řádky se shodují. ${\displaystyle A^{g))$ $A$

Ve 3D prostoru

Výše uvedený přístup se snadno rozšiřuje na trojrozměrný prostor. V trojrozměrných a vyšších prostorech se téměř jistě neprotínají ani dvě čáry. Dvojice nerovnoběžných neprotínajících se čar se nazývají zešikmení . Ale když křižovatka existuje, lze ji najít následovně.

V trojrozměrném prostoru je přímka reprezentována průsečíkem dvou rovin, z nichž každá je dána vzorcem Pak množinu n přímek lze znázornit jako 2 n rovnic z 3rozměrného souřadnicového vektoru w = ( x , y , z ) T : $(a_{i1}\quad a_{i2}\quad a_{i3})(x\quad y\quad z)^{T}=b_{i}.$

Aw=b

kde A je matice 2n × 3 a b je matice 2n × 1. Stejně jako dříve existuje jedinečný průsečík tehdy a pouze tehdy, když má A celé pořadí sloupců a rozšířená matice [ A | b ] není. Jediný průsečík, pokud existuje, je dán pomocí

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

Nejbližší bod k neprotínajícím se čarám

V dimenzích dvě a výše lze najít bod, který je nejblíže těmto dvěma (nebo více) čarám ve smyslu nejmenšího součtu čtverců .

Ve dvou rozměrech

V případě dvourozměrného prostoru reprezentujte přímku i jako bod na přímce a jednotku kolmou k přímce. To znamená, že pokud a jsou body na přímce 1, pak nechť a $p_{i}$ ${\hat {n}}_{i}$ $x_{1}$ $x_{2}$ $p_{1}=x_{1}$

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

což je jednotkový vektor podél přímky otočené o 90º.

Všimněte si, že vzdálenost od bodu x k přímce je dána vzorcem $(p,{\hat {n)))$

d(x,(p,n))=\|(xp)\cdot {\hat {n))\|=\|(xp)^{\top }{\hat {n))\| ={\sqrt {(xp)^{\top }{\hat {n}}{\hat {n}}^{\top }(xp))).

Druhá mocnina vzdálenosti od x k přímce je tedy

d(x,(p,n))^{2}=(xp)^{\top }({\hat {n)){\hat {n))^{\top })(xp) .

Součet čtverců vzdáleností k sadě čar je účelová funkce :

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

Výraz lze převést:

{\begin{aligned}E(x)&=\sum _{i}x^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^ {\top }xx^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}-p_{i}^{\top }{\klobouk {n}}_{i}{\klobouček {n}}_{i}^{\top }x+p_{i}^{\top }{\klobouk {n}}_{i} {\hat {n}}_{i}^{\top }p_{i}\\&=x^{\top }\left(\sum _{i}{\hat {n}}_{i} {\klobouk {n}}_{i}^{\horní }\vpravo)x-2x^{\horní }\vlevo(\součet _{i}{\klobouček {n}}_{i}{\klobouček {n}}_{i}^{\top }p_{i}\vpravo)+\součet _{i}p_{i}^{\top }{\klobouček {n}}_{i}{\klobouček {n}}_{i}^{\top }p_{i}.\end{aligned}}

Abychom našli minimum, derivujeme s ohledem na x a výsledek nastavíme na nulu:

{\frac {\partial E(x)}{\partial x}}=0=2\left(\sum _{i}{\hat {n}}_{i}{\hat {n} }_{i}^{\top }\right)x-2\left(\součet _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\ nahoru }p_{i}\vpravo)

Takto,

\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)x=\sum _{i} {\klobouček {n}}_{i}{\klobouček {n}}_{i}^{\top }p_{i}

kde

x=\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)^{-1}\ vlevo(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\vpravo).

Ve 3D prostoru

Ačkoli normálu nelze definovat v dimenzích vyšších než dvě , lze ji zobecnit na jakoukoli dimenzi, pokud si všimneme, že jde jednoduše o (symetrickou) matici se všemi vlastními hodnotami rovnými jedné, kromě nulové vlastní hodnoty ve směru přímky. , který udává polonormu mezi bodem a jiným bodem . V prostoru libovolné dimenze, jestliže je jednotkový vektor podél i -té přímky, pak ${\hat {n}}_{i}$ ${\hat {n}}_{i}{\hat {n}}_{i}^{\top }$ $p_{i}$ ${\hat {v}}_{i}$

{\hat {n}}_{i}{\hat {n}}_{i}^{\top }

promění v

E-{\klobouček {v}}_{i}{\klobouček {v}}_{i}^{\top }

kde E je matice identity, a pak

x=\left(\sum _{i}E-{\klobouček {v}}_{i}{\klobouček {v}}_{i}^{\top }\vpravo)^{-1 }\left(\sum _{i}(E-{\hat {v))_{i}{\hat {v))_{i}^{\top })p_{i}\right).

Viz také

Poznámky

↑ Weisstein, Eric W. "Line-Line Intersection." Z Mathworldu . Webový zdroj Wolfram . Získáno 10. ledna 2008. Archivováno z originálu 10. října 2007. (neurčitý)
↑ Podobné výpočty lze nalézt v knize Delaunaye a Raikova (str. 202-203)
↑ Homogenní souřadnice . robotika.stanford.edu . Získáno 18. 8. 2015. Archivováno z originálu 23. 8. 2015. (neurčitý)

Literatura

B. N. Delaunay, D. A. Raikov. Analytická geometrie. - M., L.: OGIZ, Státní nakladatelství technické a teoretické literatury, 1948. - T. 1.

Odkazy

Vzdálenost mezi čarami a segmenty s jejich nejbližším bodem přiblížení , použitelná pro dva, tři nebo více rozměrů.