Vonalmetszés

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. október 13-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

Az euklideszi geometriában két egyenes metszéspontja lehet egy üres halmaz , egy pont vagy egy egyenes. Ezeknek az eseteknek a megkülönböztetését és a metszéspont megtalálását használják például a számítógépes grafikában , a mozgástervezésben és az ütközésészlelésben .

A háromdimenziós euklideszi geometriában, ha két egyenes nincs ugyanabban a síkban , akkor ferdeségnek nevezzük őket, és nincs metszéspontjuk. Ha a vonalak ugyanabban a síkban vannak, három lehetőség van. Ha egybeesnek, akkor végtelenül sok közös pontjuk van (nevezetesen az összes pont ezeken az egyeneseken). Ha a vonalak különállóak, de a meredeksége megegyezik , akkor párhuzamosak és nincs közös pontjuk. Ellenkező esetben egy metszéspontjuk van.

A nem euklideszi geometriában két egyenes több pontban is metszi egymást, és egy adott egyenessel nem metsző egyéb (párhuzamos) egyenesek száma egynél nagyobb lehet.

Két egyenes metszéspontja

Két egyenes metszéspontjának szükséges feltétele , hogy egy síkhoz tartozzanak, vagyis ezek az egyenesek ne metsszék egymást. Ennek a feltételnek a teljesülése egyenértékű a tetraéder degenerációjával , amelyben két csúcs van az egyik egyenesen, a másik kettő pedig a másikon (azaz ennek a tetraédernek a térfogata nullával egyenlő). Ennek a feltételnek az algebrai formája a " Keresztezettség ellenőrzése " című cikkben található .

Minden soron két pont adott

Tekintsük két egyenes és a metszéspontját a síkon, ahol az egyenest két különböző pont és , az egyenest pedig különböző pontok és [1] határozzák meg . $L_{1}\,$ $L_{2}\,$ $L_{1}\,$ $(x_{1},y_{1})\,$ ${\megjelenítési stílus (x_{2},y_{2})\,}$ $L_{2}\,$ $(x_{3},y_{3})\,$ $(x_{4},y_{4})\,$

A és vonalak metszéspontja a determinánsok segítségével található meg . $P\,$ $L_{1}\,$ $L_{2}\,$

P_{x}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix))&{\ kezdődik \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}{\ kezdődik \{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}} \end{vmatrix}}}\,\!

A determinánsok átírhatók a következőképpen:

{\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{igazított}}

Ne feledje, hogy a metszéspont a végtelen vonalakra vonatkozik, nem a pontok közötti szakaszokra , és a szakaszokon kívül is lehet. Ha (egy lépésben történő megoldás helyett) elsőrendű Bezier -görbék alapján keresünk megoldást, akkor ezeknek a görbéknek a paramétereit ellenőrizhetjük 0,0 ≤ t ≤ 1,0 és 0,0 ≤ u ≤ 1,0 ( t és u paraméterek) .

Ha két egyenes párhuzamos vagy egybeesik, a nevező eltűnik:

{\megjelenítési stílus (x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})=0 .}

Ha a vonalak nagyon közel vannak a párhuzamoshoz (majdnem párhuzamosak), akkor a számítógépes számítás során numerikus problémák adódhatnak, és egy ilyen feltétel felismerése az alkalmazáshoz megfelelő "bizonytalansági" tesztet igényelhet. Stabilabb és általánosabb megoldás érhető el, ha a szakaszokat úgy forgatjuk el, hogy az egyik vízszintes legyen, majd a második egyenes paraméteres megoldása könnyen megkapható. Megoldáskor a speciális esetek (egyenesek párhuzamossága/egybeesése, szakaszok átfedése) gondos mérlegelése szükséges.

Ha az egyenesek egyenletei adottak

Két nem függőleges egyenes koordinátái és metszéspontjai könnyen megtalálhatók a következő helyettesítések és transzformációk segítségével. $x$ $y$

Tegyük fel, hogy két egyenesnek van egyenlete és , ahol és a vonalak meredeksége , és és a vonalak metszéspontjai az y tengellyel . Az egyenesek metszéspontjában (ha metszik) mindkét koordináta egybeesik, amiből megkapjuk az egyenlőséget: $y=ax+c$ $y=bx+d$ $a$ $b$ $c$ $d$ $y$

ax+c=bx+d

Ezt az egyenlőséget úgy alakíthatjuk át, hogy kiemeljük , $x$

ax-bx=dc

és akkor

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

Az y koordináta megtalálásához mindössze annyit kell tennünk, hogy az x értéket be kell dugni az egyik vonalképletbe, például az elsőbe:

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

Innen kapjuk meg a vonalak metszéspontját

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

Figyeljük meg, hogy a = b esetén a két egyenes párhuzamos. Ha egyszerre c ≠ d , akkor az egyenesek különbözőek és nincs metszéspontjuk, ellenkező esetben az egyenesek egybeesnek [2] .

Homogén koordináták használata

Ha homogén koordinátákat használunk , akkor két kifejezetten megadott egyenes metszéspontja egyszerűen megtalálható. A 2-dimenziós térben bármely pont definiálható egy háromdimenziós pont hármasával adott vetületeként . A 3-dimenziós koordináták 2-dimenziós koordinátáinak leképezése a képlet szerint történik . A 2-dimenziós térben lévő pontokat homogén koordinátákká alakíthatjuk át, ha a harmadik koordinátát egy - . ${\megjelenítési stílus (x,y,w)}$ $(x',y')=(x/w,y/w)$ ${\megjelenítési stílus (x,y,1)}$

Tegyük fel, hogy meg akarjuk találni két végtelen egyenes metszéspontját 2-dimenziós térben, amelyeket az és a képletek adnak meg . Ezt a két egyenest lineáris koordinátákkal ábrázolhatjuk, mint , $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})$

Két egyenes metszéspontját egyszerűen megadjuk a képletekkel [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})$

Ha , a vonalak nem metszik egymást. $c_{p}=0$

n vonal metszéspontja

Létezés és metszés kifejezés

Két dimenzióban

A kétdimenziós térben a kettőnél több vonalak szinte biztosan nem metszik egymást egy pontban. Annak meghatározására, hogy egy pontban metszik-e egymást, és ha metszik-e, akkor megtaláljuk a metszéspontot, felírjuk az i - edik egyenletet ( i = 1, ..., n ), és ezeket az egyenleteket mátrix alakban rendezzük. $(a_{i1}\quad a_{i2})(x\quad y)^{T}=b_{i},$

Aw=b,

ahol az n × 2 A mátrix i- edik sora , w egy 2 × 1 vektor ( x, y ) T , és a b oszlopvektor i- edik eleme b i . Ha az A mátrix oszlopai függetlenek , akkor a mátrix rangja 2. Akkor és csak akkor, ha a kiterjesztett mátrix rangja [ A | b ] is egyenlő 2-vel, van megoldása a mátrixegyenletnek, majd van n egyenes metszéspontja is . A metszéspontot, ha létezik, az adja meg $(a_{i1},a_{i2})$

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

ahol a mátrix pszeudoinverze . Alternatív megoldásként a megoldást két független egyenlet megoldásával is megtalálhatjuk. De ha az A mátrix rangja 1 és a kiterjesztett mátrix rangja 2, akkor nincs megoldás. Abban az esetben, ha a kiterjesztett mátrix rangja egyenlő 1-gyel, minden sor egybeesik. ${\displaystyle A^{g))$ $A$

3D térben

A fent bemutatott megközelítés könnyen kiterjeszthető a háromdimenziós térre is. Háromdimenziós és magasabb terekben még két egyenes sem metszi egymást szinte biztosan. A nem párhuzamos, nem metsző egyenesek párjait ferdeségnek nevezzük . De ha létezik egy kereszteződés, az a következőképpen található meg.

A háromdimenziós térben egy egyenest két sík metszéspontja ábrázol, amelyek mindegyikét a képlet adja meg. Ekkor az n egyenes halmaz 2 n egyenletként ábrázolható egy 3 dimenziós w = koordináta vektorból . x , y , z ) T : $(a_{i1}\quad a_{i2}\quad a_{i3})(x\quad y\quad z)^{T}=b_{i}.$

Aw=b

ahol A egy 2n × 3 mátrix és b egy 2n × 1 mátrix Mint korábban, akkor és csak akkor létezik egyedi metszéspont, ha A teljes oszloprangsorral és a kiterjesztett mátrixszal rendelkezik [ A | b ] nem. Az egyetlen metszéspontot, ha létezik, az adja meg

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

Legközelebbi pont a nem metsző vonalakhoz

A kettes és nagyobb dimenziókban megtalálhatjuk azt a pontot, amely a legközelebb van ehhez a két (vagy több) egyeneshez a legkisebb négyzetösszeg értelmében .

Két dimenzióban

Kétdimenziós tér esetén ábrázoljuk az i egyenest az egyenes pontjaként és az egyenesre merőleges egységnormálisként . Vagyis ha és pontok az 1. egyenesen, akkor legyen és $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}\|

amely az egységvektor a 90°-kal elforgatott egyenes mentén.

Figyeljük meg, hogy az x pont és az egyenes távolságát a képlet adja meg $(p,{\hat {n)))$

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

Ezért az x távolság négyzete az egyenes

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

Egy vonalhalmaz távolságának négyzetes összege a célfüggvény :

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

A kifejezés konvertálható:

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

A minimum meghatározásához különbséget teszünk x -hez képest, és az eredményt nullára állítjuk:

{\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}^{\ fent }p_{i}\jobbra)

Ily módon

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

ahol

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

3D térben

Bár a normál kettő feletti dimenziókban nem definiálható , de bármely dimenzióra általánosítható, ha észrevesszük, hogy ez egyszerűen egy (szimmetrikus) mátrix, amelynek minden sajátértéke egyenlő eggyel, kivéve a nulla sajátértéket az egyenes irányában. , amely félnormát ad egy pont és egy másik pont között. Egy tetszőleges méretű térben, ha egységvektor az i -edik egyenes mentén, akkor ${\hat {n}}_{i}$ ${\hat {n}}_{i}{\hat {n}}_{i}^{\top }$ $p_{i}$ ${\hat {v}}_{i}$

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

átváltozik _

E-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }

ahol E az azonosságmátrix, majd

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}\jobbra).

Lásd még

Jegyzetek

↑ Weisstein, Eric W. "Vonal-vonal metszéspont". A Mathworldből . Egy Wolfram webes forrás . Letöltve: 2008. január 10. Az eredetiből archiválva : 2007. október 10.. (határozatlan)
↑ Hasonló számítások találhatók Delaunay és Raikov könyvében (202-203. oldal)
↑ Homogén koordináták . robotics.stanford.edu . Letöltve: 2015. augusztus 18. Az eredetiből archiválva : 2015. augusztus 23.. (határozatlan)

Irodalom

B. N. Delaunay, D. A. Raikov. Analitikus geometria. - M., L.: OGIZ, Állami Műszaki és Elméleti Irodalmi Kiadó, 1948. - T. 1.

Linkek

A vonalak és szakaszok közötti távolság a legközelebbi megközelítési ponttal , két, három vagy több dimenzióra vonatkozik.