Průsečík čára – čára - Line–line intersection

Průsečík čar.

v Euklidovská geometrie, průsečík a čára a linka může být prázdná sada, a směřovat nebo řádek. Rozlišování těchto případů a nalezení průsečíku mají využití například v počítačová grafika, plánování pohybu, a Detekce kolize.

v trojrozměrný Euklidovská geometrie, pokud dvě čáry nejsou stejné letadlo se nazývají šikmé čáry a nemají žádný průsečík. Pokud jsou ve stejné rovině, existují tři možnosti: pokud se shodují (nejsou to odlišné čáry), mají nekonečnost společných bodů (jmenovitě všech bodů na jednom z nich); pokud jsou odlišné, ale mají stejný sklon, říká se o nich paralelní a nemají žádné společné body; jinak mají jediný průsečík.

Rozlišovací znaky neeuklidovská geometrie jsou počet a umístění možných průsečíků mezi dvěma liniemi a počet možných linií bez průniků (paralelních linií) s danou linkou.

Vzorce

A nutná podmínka pro protnutí dvou čar je to, že jsou ve stejné rovině - to znamená, že nejsou šikmé čáry. Spokojenost s tímto stavem odpovídá čtyřstěn s vrcholy ve dvou bodech na jedné linii a dvou bodech na druhé linii degenerovat ve smyslu nuly objem. Algebraickou formu této podmínky viz Šikmé čáry § Testování šikmosti.

Dány dva body na každém řádku

Nejprve uvažujeme průnik dvou přímek ${displaystyle L_ {1},}$ a ${displaystyle L_ {2},}$ ve 2-dimenzionálním prostoru, s přímkou ${displaystyle L_ {1},}$ je definován dvěma odlišnými body ${displaystyle (x_ {1}, y_ {1}),}$ a ${displaystyle (x_ {2}, y_ {2}),}$ a řádek ${displaystyle L_ {2},}$ je definován dvěma odlišnými body ${displaystyle (x_ {3}, y_ {3}),}$ a ${displaystyle (x_ {4}, y_ {4}),}$ .^[1]

Křižovatka ${displaystyle P,}$ řádku ${displaystyle L_ {1},}$ a ${displaystyle L_ {2},}$ lze definovat pomocí determinanty.

{displaystyle P_ {x} = {frac {egin {vmatrix} {egin {vmatrix} x_ {1} & y_ {1} x_ {2} & y_ {2} end {vmatrix}} & {egin {vmatrix} x_ {1 } & 1 x_ {2} & 1end {vmatrix}} {egin {vmatrix} x_ {3} & y_ {3} x_ {4} & y_ {4} end {vmatrix}} & {egin {vmatrix} x_ {3 } & 1 x_ {4} & 1end {vmatrix}} konec {vmatrix}} {egin {vmatrix} {egin {vmatrix} x_ {1} & 1 x_ {2} & 1end {vmatrix}} & {egin {vmatrix} y_ { 1} & 1 y_ {2} & 1end {vmatrix}} {egin {vmatrix} x_ {3} & 1 x_ {4} & 1end {vmatrix}} & {egin {vmatrix} y_ {3} & 1 y_ {4 } & 1end {vmatrix}} konec {vmatrix}}} ,! qquad P_ {y} = {frac {egin {vmatrix} {egin {vmatrix} x_ {1} & y_ {1} x_ {2} & y_ {2} konec {vmatrix}} & {egin {vmatrix} y_ {1} & 1 y_ {2} & 1end {vmatrix}} {egin {vmatrix} x_ {3} & y_ {3} x_ {4} & y_ {4} konec {vmatrix}} & {egin {vmatrix} y_ {3} & 1 y_ {4} & 1end {vmatrix}} end {vmatrix}} {egin {vmatrix} {egin {vmatrix} x_ {1} & 1 x_ {2} & 1end {vmatrix}} & {egin {vmatrix} y_ {1} & 1 y_ {2} & 1end {vmatrix}} {egin {vmatrix} x_ {3} & 1 x_ {4} & 1end {vmatrix}} & { egin {vmatrix} y_ {3} & 1 y_ {4} & 1end {vmatrix}} konec {vmatrix}}} ,!}

Determinanty lze zapsat jako:

{displaystyle {egin {aligned} (P_ {x}, P_ {y}) = {igg (} & {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} )}} {igg)} konec {zarovnáno}}}

Všimněte si, že průsečík je určen pro nekonečně dlouhé čáry definované body, nikoli pro úsečky mezi body a může vytvořit průsečík přesahující délky úseček. Abychom našli polohu průsečíku vzhledem k úsečkám, můžeme definovat úsečky ${displaystyle L_ {1},}$ a ${displaystyle L_ {2},}$ pokud jde o první stupeň Bézier parametry:

{displaystyle L_ {1} = {x_ {1} zvolte y_ {1}} + t {x_ {2} -x_ {1} zvolte y_ {2} -y_ {1}}, qquad L_ {2} = {x_ {3} zvolte y_ {3}} + u {x_ {4} -x_ {3} zvolte y_ {4} -y_ {3}}}

(kde t a u jsou reálná čísla). Průsečík čar je nalezen s jednou z následujících hodnot t nebo u, kde

{displaystyle t = {frac {egin {vmatrix} x_ {1} -x_ {3} & x_ {3} -x_ {4} y_ {1} -y_ {3} & y_ {3} -y_ {4} konec { vmatrix}} {egin {vmatrix} x_ {1} -x_ {2} & x_ {3} -x_ {4} y_ {1} -y_ {2} & y_ {3} -y_ {4} end {vmatrix}} } = {frac {(x_ {1} -x_ {3}) (y_ {3} -y_ {4}) - (y_ {1} -y_ {3}) (x_ {3} -x_ {4}) } {(x_ {1} -x_ {2}) (y_ {3} -y_ {4}) - (y_ {1} -y_ {2}) (x_ {3} -x_ {4})}}}

a

{displaystyle u = - {frac {egin {vmatrix} x_ {1} -x_ {2} & x_ {1} -x_ {3} y_ {1} -y_ {2} & y_ {1} -y_ {3} konec {vmatrix}} {egin {vmatrix} x_ {1} -x_ {2} & x_ {3} -x_ {4} y_ {1} -y_ {2} & y_ {3} -y_ {4} end {vmatrix} }} = - {frac {(x_ {1} -x_ {2}) (y_ {1} -y_ {3}) - (y_ {1} -y_ {2}) (x_ {1} -x_ {3 })} {(x_ {1} -x_ {2}) (y_ {3} -y_ {4}) - (y_ {1} -y_ {2}) (x_ {3} -x_ {4})} },}

s:

{displaystyle (P_ {x}, P_ {y}) = (x_ {1} + t (x_ {2} -x_ {1}) ,; y_ {1} + t (y_ {2} -y_ {1} )) quad {ext {or}} quad (P_ {x}, P_ {y}) = (x_ {3} + u (x_ {4} -x_ {3}) ,; y_ {3} + u (y_ {4} -y_ {3}))}

Průsečík spadá do prvního úsečky, pokud je 0,0 ≤t ≤ 1,0 a spadá do druhého segmentu, je-li 0,0 ≤u ≤ 1,0. Tyto nerovnosti lze testovat bez nutnosti dělení, což umožňuje rychlé určení existence jakéhokoli průsečíku úsečky před výpočtem jeho přesného bodu.^[2]

Jsou-li obě čáry rovnoběžné nebo shodné, jmenovatel je nula:

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

Pokud jsou řádky téměř rovnoběžné, pak může počítačové řešení narazit na numerické problémy s implementací výše popsaného řešení: rozpoznání této podmínky může vyžadovat přibližný test v praktické aplikaci. Alternativním přístupem může být otočení úseček tak, aby jeden z nich byl vodorovný, odkud lze snadno získat řešení otočené parametrické formy druhé úsečky. Je třeba pečlivě diskutovat o zvláštních případech (paralelní linie / shodné linie, překrývající se / nepřekrývající se intervaly).

Vzhledem ke dvěma přímkovým rovnicím

The ${displaystyle x}$ a ${displaystyle y}$ souřadnice průsečíku dvou nevislých linií lze snadno zjistit pomocí následujících substitucí a přeskupení.

Předpokládejme, že dvě přímky mají rovnice ${displaystyle y = ax + c}$ a ${displaystyle y = bx + d}$ kde ${displaystyle a}$ a ${displaystyle b}$ jsou svahy (přechody) čar a kde ${displaystyle c}$ a ${displaystyle d}$ jsou y-koncepty řádků. V místě, kde se tyto dvě čáry protínají (pokud ano), obě ${displaystyle y}$ souřadnice budou stejné, proto následující rovnost:

{displaystyle ax + c = bx + d}

.

Tento výraz můžeme přeuspořádat, abychom získali hodnotu ${displaystyle x}$ ,

{displaystyle ax-bx = d-c}

,

a tak,

{displaystyle x = {frac {d-c} {a-b}}}

.

Chcete-li najít y koordinovat, vše, co musíme udělat, je nahradit hodnotu X do jedné ze dvou přímkových rovnic, například do první:

{displaystyle y = a {frac {d-c} {a-b}} + c}

.

Proto je průsečík

{displaystyle Pleft ({frac {d-c} {a-b}}, a {frac {d-c} {a-b}} + cight)}

.

Všimněte si, jestli A = b pak jsou dva řádky paralelní. Li C ≠ d řádky jsou také různé a neexistuje žádný průnik, jinak jsou tyto dvě čáry totožné.

Použití homogenních souřadnic

Používáním homogenní souřadnice, průsečík dvou implicitně definovaných linií lze určit docela snadno. Ve 2D lze každý bod definovat jako projekci 3D bodu, který je dán jako uspořádaný trojnásobek ${displaystyle (x, y, w)}$ . Mapování z 3D do 2D souřadnic je ${displaystyle (x ', y') = (x / w, y / w)}$ . Můžeme převést 2D body na homogenní souřadnice tak, že je definujeme jako ${displaystyle (x, y, 1)}$ .

Předpokládejme, že chceme najít průnik dvou nekonečných čar ve 2-dimenzionálním prostoru, definovaném jako ${displaystyle a_ {1} x + b_ {1} y + c_ {1} = 0}$ a ${displaystyle a_ {2} x + b_ {2} y + c_ {2} = 0}$ . Můžeme tyto dva řádky reprezentovat souřadnice čáry tak jako ${displaystyle U_ {1} = (a_ {1}, b_ {1}, c_ {1})}$ a ${displaystyle U_ {2} = (a_ {2}, b_ {2}, c_ {2})}$ ,

Křižovatka ${displaystyle P '}$ dvou řádků je pak jednoduše dané,^[3]

${displaystyle P '= (a_ {p}, b_ {p}, c_ {p}) = U_ {1} imes 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})}$

Li ${displaystyle c_ {p} = 0}$ čáry se neprotínají.

Více než dva řádky

Průnik dvou řádků lze zobecnit tak, aby zahrnoval další řádky. Existence a výraz pro n- problém průsečíku řádků je následující.

Ve dvou rozměrech

Ve dvou rozměrech, více než dvou řádcích téměř jistě neprotínají se v jednom bodě. Chcete-li zjistit, zda ano, a pokud ano, najít průsečík, napište i-tá rovnice (i = 1, ...,n) tak jako ${displaystyle (a_ {i1} quad a_ {i2}) (xquad y) ^ {T} = b_ {i},}$ a tyto rovnice skládejte do maticového tvaru jako

{displaystyle Aw = b,}

Kde i-tá řada n × 2 matice A je ${displaystyle (a_ {i1}, a_ {i2})}$ , w je vektor 2 × 1 (x, y)^Ta i-tý prvek vektoru sloupce b je b_i. Li A má nezávislé sloupce, jeho hodnost je 2. Pak právě tehdy, pokud je hodnost rozšířená matice [A | b ] je také 2, existuje řešení maticové rovnice a tedy průsečík n řádky. Průsečík, pokud existuje, je dán vztahem

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

kde ${displaystyle A ^ {g}}$ je Moore-Penrose zobecnil inverzní z ${displaystyle A}$ (který má formu zobrazenou, protože A má celé pořadí sloupců). Alternativně lze řešení najít společným řešením jakýchkoli dvou nezávislých rovnic. Ale pokud hodnost A je pouze 1, pak je-li hodnost rozšířené matice 2, neexistuje řešení, ale pokud je její hodnost 1, pak se všechny řádky shodují.

Ve třech rozměrech

Výše uvedený přístup lze snadno rozšířit do tří dimenzí. Ve třech nebo více dimenzích se téměř jistě neprotínají ani dvě čáry; jsou volány páry neparalelních linií, které se neprotínají šikmé čáry. Pokud ale křižovatka existuje, lze ji najít následovně.

Ve třech rozměrech je čára reprezentována průsečíkem dvou rovin, z nichž každá má rovnici tvaru ${displaystyle (a_ {i1} quad a_ {i2} quad a_ {i3}) (xquad yquad z) ^ {T} = b_ {i}.}$ Tedy soubor n řádky mohou být reprezentovány 2n rovnice v trojrozměrném souřadnicovém vektoru w = (X, y, z)^T:

{displaystyle Aw = b}

kam teď A je 2n × 3 a b je 2n × 1. Stejně jako dříve existuje jedinečný průsečík právě tehdy A má celé pořadí sloupců a rozšířenou matici [A | b ] ne, a jedinečný průnik, pokud existuje, je dán vztahem

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

Nejbližší body ke zkoseným čarám

Ve dvou nebo více dimenzích můžeme obvykle najít bod, který je vzájemně nejblíže ke dvěma nebo více přímkám v a nejmenší čtverce smysl.

Ve dvou rozměrech

V dvourozměrném případě první představuje čáru i jako bod, ${displaystyle p_ {i}}$ , na lince a a jednotka normální vektor, ${displaystyle {hat {n}} _ {i}}$ , kolmo k této přímce. To je, pokud ${displaystyle x_ {1}}$ a ${displaystyle x_ {2}}$ jsou body na řádku 1, pak nechte ${displaystyle p_ {1} = x_ {1}}$ a nechte

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

což je jednotkový vektor podél čáry otočený o 90 stupňů.

Všimněte si, že vzdálenost od bodu, X na řádek ${displaystyle (p, {hat {n}})}$ darováno

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

A tak na druhou vzdálenost od bodu, X, na řádek je

{displaystyle d (x, (p, n)) ^ {2} = (x-p) ^ {op} ({hat {n}} {hat {n}} ^ {op}) (x-p).}

Součet čtverců vzdáleností k mnoha řádkům je nákladová funkce:

{displaystyle E (x) = součet _ {i} (x-p_ {i}) ^ {op} ({hat {n}} _ {i} {hat {n}} _ {i} ^ {op}) (x-p_ {i}).}

To lze přeskupit:

{displaystyle {egin {aligned} E (x) & = sum _ {i} x ^ {op} {hat {n}} _ {i} {hat {n}} _ {i} ^ {op} xx ^ { op} {hat {n}} _ {i} {hat {n}} _ {i} ^ {op} p_ {i} -p_ {i} ^ {op} {hat {n}} _ {i} { klobouk {n}} _ {i} ^ {op} x + p_ {i} ^ {op} {hat {n}} _ {i} {hat {n}} _ {i} ^ {op} p_ {i } & = x ^ {op} vlevo (součet _ {i} {hat {n}} _ {i} {hat {n}} _ {i} ^ {op} ight) x-2x ^ {op} vlevo (součet _ {i} {hat {n}} _ {i} {hat {n}} _ {i} ^ {op} p_ {i} ight) + součet _ {i} p_ {i} ^ {op} {hat {n}} _ {i} {hat {n}} _ {i} ^ {op} p_ {i} .end {aligned}}}

Abychom našli minimum, rozlišujeme s ohledem na X a nastavte výsledek rovný nulovému vektoru:

{displaystyle {frac {částečné E (x)} {částečné x}} = 0 = 2 vlevo (součet _ {i} {klobouk {n}} _ {i} {klobouk {n}} _ {i} ^ {op} ight) x-2left (součet _ {i} {hat {n}} _ {i} {hat {n}} _ {i} ^ {op} p_ {i} ight)}

tak

{displaystyle left (sum _ {i} {hat {n}} _ {i} {hat {n}} _ {i} ^ {op} ight) x = sum _ {i} {hat {n}} _ { i} {hat {n}} _ {i} ^ {op} p_ {i}}

a tak

{displaystyle x = left (sum _ {i} {hat {n}} _ {i} {hat {n}} _ {i} ^ {op} ight) ^ {- 1} left (sum _ {i} { klobouk {n}} _ {i} {hat {n}} _ {i} ^ {op} p_ {i} ight).}

Ve více než dvou dimenzích

Zatímco ${displaystyle {hat {n}} _ {i}}$ není dobře definován ve více než dvou dimenzích, lze to zobecnit na libovolný počet dimenzí ${displaystyle {hat {n}} _ {i} {hat {n}} _ {i} ^ {op}}$ je jednoduše (symetrická) matice s jednotou všech vlastních čísel kromě nulové vlastní hodnoty ve směru podél linie poskytující seminář na vzdálenost mezi ${displaystyle p_ {i}}$ a další bod udávající vzdálenost k přímce. V libovolném počtu rozměrů, pokud ${displaystyle {hat {v}} _ {i}}$ je jednotkový vektor podél the i-tý řádek, tedy

{displaystyle {hat {n}} _ {i} {hat {n}} _ {i} ^ {op}}

se stává

{displaystyle I- {hat {v}} _ {i} {hat {v}} _ {i} ^ {op}}

kde Já je matice identity atd^[4]

{displaystyle x = left (sum _ {i} I- {hat {v}} _ {i} {hat {v}} _ {i} ^ {op} ight) ^ {- 1} left (sum _ {i } (I- {hat {v}} _ {i} {hat {v}} _ {i} ^ {op}) p_ {i} ight).}

Obecná derivace

Abychom našli průsečík sady přímek, vypočítáme bod s minimální vzdáleností od nich. Každý řádek je definován počátkem ${displaystyle a_ {i}}$ a jednotkový směrový vektor, ${displaystyle n_ {i}}$ . Čtverec vzdálenosti od bodu ${displaystyle p}$ jeden z řádků je dán Pythagorasem:

{displaystyle d_ {i} ^ {2} = {{left [left | p - {{a} _ {i}} ight | ight]} ^ {2}} - {{left [{{left (p- { {a} _ {i}} ight)} ^ {T}} * {{n} _ {i}} ight]} ^ {2}} = {{left (p - {{a} _ {i}} ight)} ^ {T}} * vlevo (p - {{a} _ {i}} ight) - {{left [{{left (p - {{a} _ {i}} ight)} ^ {T }} * {{n} _ {i}} ight]} ^ {2}}}

Kde: ${displaystyle {left (p-a_ {i} ight)} ^ {T} * n_ {i}}$ je projekce: ${displaystyle left (p - {{a} _ {i}} ight)}$ na lince ${displaystyle i}$ . Součet vzdáleností od čtverce ke všem řádkům je:

{displaystyle {underset {i} {mathop {sum}}}, d_ {i} ^ {2} = {underset {i} {mathop {sum}}}, left [{{left (p - {{a} _ {i}} ight)} ^ {T}} * vlevo (p - {{a} _ {i}} ight) - {{left [{{left (p - {{a} _ {i}} ight) } ^ {T}} * {{n} _ {i}} ight]} ^ {2}} ight]}

Abychom tento výraz minimalizovali, rozlišujeme jej s ohledem na ${displaystyle p}$ .

{displaystyle {underset {i} {mathop {sum}}}, left [2 * left (p - {{a} _ {i}} ight) -2 * ight [{{left (p - {{a} _ {i}} ight)} ^ {T}} * {{n} _ {i}}] * {{n} _ {i}}] = 0}

{displaystyle {underset {i} {mathop {sum}}}, left (p - {{a} _ {i}} ight) = {underset {i} {mathop {sum}}}, left [{{n} _ {i}} * {{n} _ {i}} ^ {T} ight] * vlevo (p - {{a} _ {i}} ight)}

Výsledkem je:

{displaystyle [{underset {i} {mathop {sum}}}, left [I - {{n} _ {i}} * {{n} _ {i}} ^ {T} ight]] * p = { podmnožina {i} {mathop {sum}}}, vlevo [I - {{n} _ {i}} * {{n} _ {i}} ^ {T} ight] * {{a} _ {i} }}

Kde ${displaystyle I}$ je matice identity. Toto je matice ${displaystyle ~ S * p = C}$ , s řešením ${displaystyle p = {{S} ^ {+}} * C}$ , kde ${displaystyle {S} ^ {+}}$ , je pseudo-inverzní ${displaystyle S}$ .

Viz také

Reference

^ „Weisstein, Eric W.“ Line-Line Intersection. „From MathWorld“. Webový zdroj Wolfram. Citováno 2008-01-10.
^ Antonio, Franklin (1992). „Kapitola IV.6: Rychlejší průsečík segmentů linky“. V Kirk, David (ed.). Grafické drahokamy III. Academic Press, Inc. str. 199–202. ISBN 0-12-059756-X.
^ "Homogenní souřadnice". robotics.stanford.edu. Citováno 2015-08-18.
^ Traa, Johannes. „Křižovatka nejmenších čtverců“ (PDF). Citováno 30. srpna 2018.

externí 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ů.

[Wolfram-1] „Weisstein, Eric W.“ Line-Line Intersection. „From MathWorld“. Webový zdroj Wolfram. Citováno 2008-01-10.

[GGIII-2] Antonio, Franklin (1992). „Kapitola IV.6: Rychlejší průsečík segmentů linky“. V Kirk, David (ed.). Grafické drahokamy III. Academic Press, Inc. str. 199–202. ISBN 0-12-059756-X.

[3] "Homogenní souřadnice". robotics.stanford.edu. Citováno 2015-08-18.

[4] Traa, Johannes. „Křižovatka nejmenších čtverců“ (PDF). Citováno 30. srpna 2018.

[1]

[2]

[3]

[4]