Linjojen leikkaus

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 13.10.2020 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Euklidisessa geometriassa kahden suoran leikkauspiste voi olla tyhjä joukko , piste tai suora. Näiden tapausten erottamista ja leikkauspisteen löytämistä käytetään esimerkiksi tietokonegrafiikassa , liikkeen suunnittelussa ja törmäysten havaitsemisessa .

Kolmiulotteisessa euklidisessa geometriassa, jos kaksi suoraa eivät ole samassa tasossa , niitä kutsutaan vinoiksi eikä niillä ole leikkauspisteitä. Jos viivat ovat samassa tasossa, on kolme mahdollisuutta. Jos ne ovat samat, niillä on äärettömän monta yhteistä pistettä (eli kaikki pisteet näillä viivoilla). Jos viivat ovat erillisiä, mutta niillä on sama kaltevuus , ne ovat yhdensuuntaisia eikä niillä ole yhteisiä pisteitä. Muuten niillä on yksi leikkauspiste.

Ei -euklidisessa geometriassa kaksi suoraa voi leikata useissa pisteissä, ja muiden suorien (rinnakkaisten) määrä, jotka eivät leikkaa tietyn suoran kanssa, voi olla suurempi kuin yksi.

Kahden viivan leikkauspiste

Kahden suoran leikkaamisen välttämätön ehto on, että ne kuuluvat samaan tasoon, eli nämä suorat eivät saa olla leikkaavia. Tämän ehdon täyttyminen vastaa tetraedrin degeneraatiota , jossa kaksi kärkeä ovat yhdellä suoralla ja kaksi muuta toisella (eli tämän tetraedrin tilavuus on nolla). Tämän ehdon algebrallinen muoto löytyy artikkelista " Ristikkäisyyden tarkistaminen ".

Jokaisella rivillä on annettu kaksi pistettä

Tarkastellaan kahden suoran leikkauskohtaa ja tasossa, jossa suora määritellään kahdella eri pisteellä ja , ja suoran määrittelevät eri pisteet ja [1] . $L_{1}\,$ $L_{2}\,$ $L_{1}\,$ ${\näyttötyyli (x_{1},y_{1})\,}$ ${\näyttötyyli (x_{2},y_{2})\,}$ $L_{2}\,$ ${\näyttötyyli (x_{3},y_{3})\,}$ ${\näyttötyyli (x_{4},y_{4})\,}$

Viivojen ja leikkauspiste löytyy determinanteista . $P\,$ $L_{1}\,$ $L_{2}\,$

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

Determinantit voidaan kirjoittaa uudelleen seuraavasti:

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

Huomaa, että leikkauspiste viittaa äärettömiin suoriin, ei pisteiden välisiin janaihin, ja se voi sijaita janaosien ulkopuolella. Jos etsimme ratkaisua (yhteen vaiheen ratkaisemisen sijaan) ensimmäisen asteen Bezier -käyrien perusteella, voimme tarkistaa näiden käyrien parametrit 0,0 ≤ t ≤ 1,0 ja 0,0 ≤ u ≤ 1,0 ( t ja u ovat parametreja) .

Jos kaksi suoraa ovat yhdensuuntaisia tai osuvat yhteen, nimittäjä häviää:

{\näyttötyyli (x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})=0 .}

Jos suorat ovat hyvin lähellä yhdensuuntaisia (melkein yhdensuuntaisia), tietokonelaskennassa voi ilmetä numeerisia ongelmia, ja tällaisen ehdon tunnistaminen voi vaatia sovellukselle sopivan "epävarmuustestin". Vakaampi ja yleisempi ratkaisu saadaan kiertämällä segmenttejä siten, että yksi niistä tulee vaakasuoraan, jolloin toisen suoran parametrinen ratkaisu on helppo saada. Ratkaisussa erityistapaukset (suorien yhdensuuntaisuus/sattuma, osien päällekkäisyys) on huomioitava huolellisesti.

Jos suorayhtälöt annetaan

Kahden ei-pystysuoran suoran koordinaatit ja leikkauspisteet löytyvät helposti seuraavilla substituutioilla ja muunnoksilla. $x$ $y$

Oletetaan, että kahdella rivillä on yhtälöt ja , Jossa ja ovat linjojen kaltevuus , ja ja ovat viivojen leikkauspisteet y - akselin kanssa . Viivojen leikkauspisteessä (jos ne leikkaavat) molemmat koordinaatit osuvat yhteen, josta saamme yhtäläisyyden: $y=ax+c$ $y=bx+d$ $a$ $b$ $c$ $d$ $y$

ax+c=bx+d

Voimme muuttaa tämän tasa-arvon korostaaksemme , $x$

ax-bx=dc

ja sitten

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

Löytääksemme y -koordinaatin , meidän tarvitsee vain kytkeä x -arvo johonkin viivakaavasta, kuten ensimmäiseen:

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

Täältä saamme viivojen leikkauspisteen

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

Huomaa, että a = b :n kaksi suoraa ovat yhdensuuntaisia. Jos samaan aikaan c ≠ d , suorat ovat erilaisia eikä niillä ole leikkauskohtia, muuten suorat osuvat yhteen [2] .

Homogeenisten koordinaattien käyttö

Homogeenisiä koordinaatteja käytettäessä kahden eksplisiittisesti annetun suoran leikkauspiste löytyy yksinkertaisesti. 2-ulotteisessa avaruudessa mikä tahansa piste voidaan määritellä kolmiulotteisen kolmiulotteisen pisteen projektioksi . Kolmiulotteisten koordinaattien kartoitus 2-ulotteisiksi tapahtuu kaavan mukaan . Voimme muuntaa 2-ulotteisen avaruuden pisteet homogeenisiksi koordinaatteiksi rinnastamalla kolmannen koordinaatin yhteen - . ${\näyttötyyli (x,y,w)}$ $(x',y')=(x/w,y/w)$ ${\näyttötyyli (x,y,1)}$

Oletetaan, että haluamme löytää kahden äärettömän suoran leikkauspisteen 2-ulotteisessa avaruudessa, jotka on annettu kaavoilla ja . Voimme esittää nämä kaksi viivaa lineaarisissa koordinaateissa kuten , $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})$

Kahden suoran leikkauspiste saadaan sitten yksinkertaisesti kaavoilla [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})$

Jos , linjat eivät leikkaa. $c_{p}=0$

N: n rivin leikkauspiste

Olemassaolo- ja leikkauslauseke

Kahdessa ulottuvuudessa

Kaksiulotteisessa avaruudessa suorat, joissa on enemmän kuin kaksi, eivät läheskään varmasti leikkaa yhdessä pisteessä. Sen määrittämiseksi, leikkaavatko ne yhdessä pisteessä, ja jos ne leikkaavat, löytääksemme leikkauspisteen, kirjoitamme i : nnen yhtälön ( i = 1, ..., n ) muodossa ja järjestämme nämä yhtälöt matriisimuotoon $(a_{i1}\quad a_{i2})(x\quad y)^{T}=b_{i},$

Aw=b,

missä n × 2 -matriisin A i . rivi on , w on 2 × 1 vektori ( x, y ) T ja sarakevektorin b i . elementti on b i . Jos matriisin A sarakkeet ovat riippumattomia, niin matriisin järjestys on 2. Jos ja vain jos laajennetun matriisin järjestys on [ A | b ] on myös yhtä kuin 2, matriisiyhtälöön on ratkaisu, ja sitten on myös n suoran leikkauspiste . Leikkauspiste, jos se on olemassa, on annettu ${\näyttötyyli (a_{i1},a_{i2})}$

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

missä on matriisin pseudoinversio . Vaihtoehtoisesti ratkaisu voidaan löytää ratkaisemalla mitkä tahansa kaksi riippumatonta yhtälöä. Mutta jos matriisin A järjestys on 1 ja lisätyn matriisin arvo on 2, ratkaisuja ei ole. Siinä tapauksessa, että laajennetun matriisin järjestys on yhtä suuri kuin 1, kaikki rivit ovat samat. ${\näyttötyyli A^{g))$ $A$

3D-avaruudessa

Yllä esitetty lähestymistapa ulottuu helposti kolmiulotteiseen avaruuteen. Kolmiulotteisissa ja korkeammissa tiloissa edes kaksi suoraa eivät läheskään varmasti leikkaa toisiaan. Ei-rinnakkaisia ei-leikkaavia viivoja kutsutaan vinoiksi . Mutta kun risteys on olemassa, se voidaan löytää seuraavasti.

Kolmiulotteisessa avaruudessa suoraa edustaa kahden tason leikkauspiste, joista kukin on annettu kaavalla. Sitten n suoran joukko voidaan esittää 2 n yhtälönä 3-ulotteisesta koordinaattivektorista w = ( x , y , z ) T : $(a_{i1}\quad a_{i2}\quad a_{i3})(x\quad y\quad z)^{T}=b_{i}.$

Aw=b

jossa A on 2n × 3 -matriisi ja b on 2n × 1 -matriisi Kuten aiemminkin, ainutlaatuinen leikkauspiste on olemassa, jos ja vain jos A: lla on täysi sarakearvo ja lisätty matriisi [ A | b ] ei ole. Ainoa leikkauspiste, jos se on olemassa, on annettu

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

Lähin piste ei-leikkaavalle viivolle

Dimensioista kaksi ja ylempänä voidaan löytää piste, joka on lähinnä näitä kahta (tai useampaa) suoraa pienimmän neliösumman merkityksessä .

Kahdessa ulottuvuudessa

Jos kyseessä on kaksiulotteinen avaruus, esitä suora i suoran pisteenä ja yksikkönormaalina , joka on kohtisuorassa suoraa vastaan. Eli jos ja ovat pisteitä rivillä 1, niin olkoon ja $p_{i}$ ${\näyttötyyli {\hattu {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}\|

joka on yksikkövektori pitkin linjaa, jota on kierretty 90º.

Huomaa, että etäisyys pisteestä x suoraan saadaan kaavalla $(p,{\hattu {n)))$

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

Siksi x :n ja suoran välisen etäisyyden neliö on

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

Linjojen etäisyyksien neliösumma on tavoitefunktio :

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

Lauseke voidaan muuntaa:

{\begin{aligned}E(x)&=\sum _{i}x^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^ {\top }xx^{\top }{\hattu {n}}_{i}{\hattu {n}}_{i}^{\top }p_{i}-p_{i}^{\top }{\hattu {n}}_{i}{\hattu {n}}_{i}^{\top }x+p_{i}^{\top }{\hat {n}}_{i} {\hat {n}}_{i}^{\top }p_{i}\\&=x^{\top }\left(\sum _{i}{\hat {n}}_{i} {\hattu {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}}

Löytääksemme minimin, teemme eron x :n suhteen ja asetamme tulokseksi nollan:

{\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}^{\ ylhäällä }p_{i}\oikea)

Tällä tavalla,

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

missä

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

3D-avaruudessa

Vaikka normaalia ei voida määritellä dimensioissa, jotka ovat yli kaksi , se voidaan yleistää mihin tahansa ulottuvuuteen, jos huomaa, että se on yksinkertaisesti (symmetrinen) matriisi, jonka kaikki ominaisarvot ovat yhtä suuret kuin yksi, paitsi nolla-ominaisarvo suoran suunnassa , joka antaa puolinormin pisteen ja toisen pisteen välillä. Minkä tahansa ulottuvuuden avaruudessa, jos on yksikkövektori pitkin i : ttä suoraa, niin ${\näyttötyyli {\hattu {n}}_{i}}$ ${\hat {n}}_{i}{\hat {n}}_{i}^{\top }$ $p_{i}$ ${\hat {v}}_{i}$

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

muuttuu _

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

missä E on identiteettimatriisi, ja sitten

x=\left(\sum _{i}E-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }\oikea)^{-1 }\left(\sum _{i}(E-{\hat {v))_{i}{\hat {v))_{i}^{\top })p_{i}\oikea).

Katso myös

Muistiinpanot

↑ Weisstein, Eric W. "Line-Line leikkaus." Mathworldistä . Wolfram-verkkoresurssi . Haettu 10. tammikuuta 2008. Arkistoitu alkuperäisestä 10. lokakuuta 2007. (määrätön)
↑ Samanlaisia laskelmia löytyy Delaunayn ja Raikovin kirjasta (s. 202-203)
↑ Homogeeniset koordinaatit . robotics.stanford.edu . Haettu 18. elokuuta 2015. Arkistoitu alkuperäisestä 23. elokuuta 2015. (määrätön)

Kirjallisuus

B. N. Delaunay, D. A. Raikov. Analyyttinen geometria. - M., L.: OGIZ, Valtion teknisen ja teoreettisen kirjallisuuden kustantaja, 1948. - T. 1.

Linkit

Linjojen ja osien välinen etäisyys niiden lähimmän lähestymispisteen kanssa , koskee kahta, kolmea tai useampaa ulottuvuutta.