Linjekorsning

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 oktober 2020; kontroller kräver 2 redigeringar .

I euklidisk geometri kan skärningspunkten mellan två linjer vara en tom uppsättning , en punkt eller en linje. Att särskilja dessa fall och hitta skärningspunkten används till exempel i datorgrafik , i rörelseplanering och i kollisionsdetektering .

I tredimensionell euklidisk geometri, om två linjer inte är i samma plan , kallas de skeva och har inga skärningspunkter. Om linjerna är i samma plan finns det tre möjligheter. Om de sammanfaller har de oändligt många punkter gemensamma (nämligen alla punkter på dessa linjer). Om linjerna är distinkta men har samma lutning är de parallella och har inga gemensamma punkter. Annars har de en skärningspunkt.

I icke-euklidisk geometri kan två linjer skära varandra i flera punkter, och antalet andra linjer (parallella) som inte skär en given linje kan vara större än en.

Skärning av två linjer

En nödvändig förutsättning för skärningen av två linjer är att de tillhör samma plan, det vill säga att dessa linjer inte ska skära varandra. Uppfyllelsen av detta villkor är ekvivalent med degenerationen av tetraedern , där två hörn ligger på en rät linje och de andra två ligger på den andra (dvs. volymen av denna tetraeder är lika med noll). Den algebraiska formen av detta tillstånd finns i artikeln " Kontrollera korsning ".

Givet två punkter på varje rad

Betrakta skärningspunkten mellan två linjer och på planet, där linjen definieras av två olika punkter och , och linjen definieras av olika punkter och [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})\,$

Skärningen av linjer och kan hittas med hjälp av determinanter . $P\,$ $L_{1}\,$ $L_{2}\,$

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

Determinanterna kan skrivas om som:

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

Observera att skärningspunkten hänvisar till de oändliga linjerna, inte linjesegmenten mellan punkterna, och den kan ligga utanför linjesegmenten. Om vi (istället för att lösa i ett steg) letar efter en lösning i form av första ordningens Bezier -kurvor, då kan vi kontrollera parametrarna för dessa kurvor 0,0 ≤ t ≤ 1,0 och 0,0 ≤ u ≤ 1,0 ( t och u är parametrar) .

Om två linjer är parallella eller sammanfaller, försvinner nämnaren:

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

Om linjerna är mycket nära parallella (nästan parallella) kan numeriska problem uppstå i datorberäkningen, och att identifiera ett sådant tillstånd kan kräva ett lämpligt "osäkerhetstest" för applikationen. En mer stabil och generell lösning kan erhållas genom att rotera segmenten på ett sådant sätt att ett av dem blir horisontellt, och då är den parametriska lösningen av den andra räta linjen lätt att få. Vid lösning är det nödvändigt att noggrant överväga speciella fall (parallellism/sammanfall av raka linjer, överlappning av segment).

Om linjeekvationer ges

Koordinaterna och skärningspunkterna för två icke-vertikala linjer kan lätt hittas med hjälp av följande substitutioner och transformationer. $x$ $y$

Antag att två linjer har ekvationer och , där och är linjernas sluttningar , och och är skärningspunkterna mellan linjerna med y -axeln . Vid skärningspunkten för linjerna (om de skär varandra) kommer båda koordinaterna att sammanfalla, varifrån vi får likheten: $y=ax+c$ $y=bx+d$ $a$ $b$ $c$ $d$ $y$

ax+c=bx+d

Vi kan omvandla denna jämställdhet för att belysa , $x$

ax-bx=dc

och då

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

För att hitta y -koordinaten behöver vi bara koppla in x -värdet i en av linjeformlerna, som den första:

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

Härifrån får vi skärningspunkten för linjerna

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

Observera att för a = b är de två linjerna parallella. Om samtidigt c ≠ d , är linjerna olika och har inga skärningspunkter, annars sammanfaller linjerna [2] .

Användning av homogena koordinater

När man använder homogena koordinater kan skärningspunkten för två explicit givna linjer hittas helt enkelt. I ett 2-dimensionellt rum kan vilken punkt som helst definieras som en projektion av en 3-dimensionell punkt som ges av en trippel . Mappningen av 3-dimensionella koordinater till 2-dimensionella sker enligt formeln . Vi kan omvandla punkter i det 2-dimensionella rummet till homogena koordinater genom att likställa den tredje koordinaten med en - . $(x,y,w)$ $(x',y')=(x/w,y/w)$ $(x,y,1)$

Anta att vi vill hitta skärningspunkten mellan två oändliga linjer i det 2-dimensionella rummet, som ges av formlerna och . Vi kan representera dessa två linjer i linjära koordinater som , $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})$

Skärningen av två linjer ges då helt enkelt av formlerna [3] $P'$

$P'=(a_{p},b_{p},c_{p})=U_{1}\ gånger 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})$

Om , linjerna inte skär varandra. $c_{p}=0$

Skärning av n linjer

Existens och skärningsuttryck

I två dimensioner

I tvådimensionellt utrymme, skär linjer med fler än två nästan säkert inte vid en punkt. För att avgöra om de skär varandra vid en punkt, och om de skär varandra, för att hitta skärningspunkten, skriver vi den i -:e ekvationen ( i = 1, ..., n ) som och ordnar dessa ekvationer i matrisform $(a_{i1}\quad a_{i2})(x\quad y)^{T}=b_{i},$

Aw=b,

där den i: te raden av n × 2 matrisen A är , w är en 2 × 1 vektor ( x, y ) T , och det i: te elementet i kolumnvektorn b är bi . Om kolumnerna i matrisen A är oberoende, är matrisens rangordning 2. Om och endast om rangordningen för den utökade matrisen är [ A | b ] är också lika med 2, det finns en lösning på matrisekvationen, och sedan finns det också en skärningspunkt för n linjer. Skärningspunkten, om den finns, ges av $(a_{i1},a_{i2})$

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

var är pseudoinversen av matrisen . Alternativt kan lösningen hittas genom att lösa två oberoende ekvationer. Men om rangordningen för matris A är 1 och rangordningen för den utökade matrisen är 2, finns det inga lösningar. I det fall då rangordningen för den utökade matrisen är lika med 1, sammanfaller alla linjer. ${\displaystyle A^{g))$ $A$

I 3D-rymden

Tillvägagångssättet som presenteras ovan sträcker sig lätt till tredimensionellt utrymme. I tredimensionella och högre utrymmen skär inte ens två linjer nästan säkert. Par av icke-parallella icke-korsande linjer kallas skev . Men när en korsning finns kan den hittas på följande sätt.

I det tredimensionella rymden representeras en rät linje av skärningspunkten mellan två plan, som vart och ett ges av formeln. Sedan kan uppsättningen av n räta linjer representeras som 2 n ekvationer från en 3-dimensionell koordinatvektor w = ( x , y , z ) T : $(a_{i1}\quad a_{i2}\quad a_{i3})(x\quad y\quad z)^{T}=b_{i}.$

Aw=b

där A är en 2n × 3 matris och b är en 2n × 1 matris. Som tidigare finns en unik skärningspunkt om och endast om A har full kolumnrankning och den utökade matrisen [ A | b ] är det inte. Den enda skärningspunkten, om den finns, ges av

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

Närmaste punkt till icke-korsande linjer

I dimension två och uppåt kan man hitta den punkt som ligger närmast dessa två (eller flera) linjer i betydelsen minsta kvadratsumman .

I två dimensioner

I fallet med ett tvådimensionellt utrymme, representera linjen i som en punkt på linjen och en normalenhet vinkelrät mot linjen. Det vill säga om och är punkter på rad 1, låt och $pi}$ ${\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}\|

vilket är enhetsvektorn längs linjen roterad 90º.

Observera att avståndet från punkten x till linjen ges av formeln $(p,{\hat {n)))$

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

Därför är kvadraten på avståndet från x till linjen

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

Summan av kvadrerade avstånd till en rad linjer är målfunktionen :

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

Uttrycket kan konverteras:

{\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(\summa _{i}{\hat {n}}_{i} {\hat {n}}_{i}^{\top }\right)x-2x^{\top }\left(\summa _{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}}

För att hitta minimum, differentierar vi med avseende på x och sätter resultatet lika med noll:

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

På det här sättet,

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

var

x=\left(\summa _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)^{-1}\ vänster(\summa _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\höger).

I 3D-rymden

Även om normalen inte kan definieras i dimensioner över två , kan den generaliseras till vilken dimension som helst om man märker att den helt enkelt är en (symmetrisk) matris med alla egenvärden lika med ett, förutom egenvärdet noll i linjens riktning , vilket ger en semi- norm mellan en punkt och en annan punkt . I ett utrymme av vilken dimension som helst, är if en enhetsvektor längs den i -te räta linjen, alltså ${\hat {n}}_{i}$ ${\hat {n}}_{i}{\hat {n}}_{i}^{\top }$ $pi}$ ${\hat {v}}_{i}$

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

förvandlas till

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

där E är identitetsmatrisen, och sedan

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).

Se även

Anteckningar

↑ Weisstein, Eric W. "Linje-linje skärning." Från Mathworld . En Wolfram webbresurs . Hämtad 10 januari 2008. Arkiverad från originalet 10 oktober 2007. (obestämd)
↑ Liknande beräkningar finns i boken av Delaunay och Raikov (s. 202-203)
↑ Homogena koordinater . robotics.stanford.edu . Hämtad 18 augusti 2015. Arkiverad från originalet 23 augusti 2015. (obestämd)

Litteratur

B.N. Delaunay, D.A. Raikov. Analytisk geometri. - M., L.: OGIZ, Statens förlag för teknisk och teoretisk litteratur, 1948. - T. 1.

Länkar

Avstånd mellan linjer och segment med deras närmaste ingångspunkt , tillämpligt på två, tre eller fler dimensioner.