Háromszög és egyenes metszéspontja

Kis bevezetés

A háromszög és egyenes metszéspontjának a problémája gyakran előfordul, mikor az ember egy 3D-s játékot akar magának csinálni és nem egy előre legyártott engine-be hajigálja be a cuccokat. Pl.: amikor lősz ki kéne számolni, hogy hova csapodik be a töltény. Vagy annak meghatározására, hogy hogy ne menjünk át a falon.

Meghatározás

Hogy kicsit matematizáljuk a problémát adott egy háromszög a térben a sarkait jelöljük A,B,C pontokkal (térben vannak tehát ezeknek a pontoknak 3 koordinátája van A(a₁,a₂,a₃),B(b₁,b₂,b₃),C(c₁,c₂,c₃)). Kell egy D pont is, ahová megyünk, és egy v vektor (A vektorokat is 3 koordinátával adják meg, de nem sok köze a pontokhoz, ez a három koordináta csak azt adja meg, hogy mennyit kell menni x,y,z irányba a kezdőpontjától, hogy a végébe jussunk, arról nem szól, hogy ez a vektor honnét indul) is, amellyel azt mondjuk meg, hogy merre lövünk. És ezen adatok alapján kell megadnunk egy függvényt, amely ezen megadott pontok alapján megadja azt hogy elmegyünk-e a háromszög mellett, és ha nem, akkor megadja azt, hogy mennyire kell menni, hogy pont elérjük a háromszöget.

Megoldás

A háromszög három pontja meghatároz egy síkot. A megadott pont és a vektor pedig megad egy egyenest. A kettő metszéspontja lesz a pont, ezután már csak azt kell megnézni, hogy ez a háromszögre esik-e.

Ahhoz, hogy tudjunk a síkkal számolni, meg kell adnunk magát a síkot. De ehhez vektorokkal kell vacakolni, és valahogy a vektorokat össze kellene hozni a pontokkal. Ez az összehozás nem nehéz, ha minden vektort úgy kezelünk, mintha az origóban kezdődne, akkor az (x,y,z) koordinátákkal megadott vektor pontosan az (x,y,z) pontba mutat, ez a módja annak, hogy a vektorokból pontot csináljuk és fordítva. Egyébként az origóból kiinduló vektorokat helyvektornak is nevezik, mert a végük pont az azonos koordinátájú pontra mutat. Bár lehet, hogy ez előbbi csak rizsa volt, de talán ez segíthet abban, hogy megértsük miért kell majd a végén koordinátákat hozzáadni a dolgokhoz, hogy jó legyen.

Tehát a sík megadásához vektorokkal fogunk vacakolni. Ezt a két vektort meg a háromszögből vesszük. Legyenek ezek az e és f vektorok:

Tehát az egyik vektor az A csúcsból B csúcsba mutat a háromszögön, a másik meg az A csúcsból C csúcsba mutat. Ezek a vektorok függetlenek, ha mégis fűggenének, akkor Az A,B,C pont egy egyenesen van, ami szívás. Két független vektorból álló rendszer egy 2D-s vektortér azaz sík bázisa, és ez a sík pontosan az ABC háromszög síkja. Bármely más vektor ezen a síkon függ ettől a két vektortól, és ha függ az azt jelenti, hogy előállítható ezen vektorok lineáris kombinációjaként (mindkét vektort megszorozzuk egy számmal és összeadjük). És ezzel meg is van, hogy hogy adjuk meg a háromszög síkját: vesszük az összes vektort, ami az e és f vektorokból kikombinálható, és ha ezeknek a vektoroknak az elejét az origóba írjuk, akkor a koordinátáik pont egy origán átmenő sík pontjait adják meg. De nekünk nem ez a sík kell, hanem, ami háromszögön fekszik, ezért csak eltoljuk a sík pontjait a háromszöghöz. Ezt úgy, hogy hozzáadjuk háromszög valamelyik pontjának koordinátáit a sík pontjaihoz, és akkor ezzel el is toltuk a síkunkat a megfelelő helyre. Tehát a sík pontjait így adjuk meg:

Ahol p egy síkon lévő pont helyvektora, a vektor meg az A helyvektora, annak a koordinátáit adtuk hozzá, hogy a sík jó helyen legyen. Az alfa meg a béta akármi lehet, p tuti a síkunkon lesz.

Tehát a síkunk megvan. Most jön az egyenes. Ehhez van egy v vektorunk, amiből ha pontokat akarunk, az elejét az origóba kell tolni, ha ezt beszorozzuk egy tetszőleges számmal a kapott vektor vége tuti ugyanazon az egyenesen lesz, és a kezdőpontja ezen vektoroknak az origó, ezért egyszerű kopipszttel lehet a vektorkoordinátáiból pont koordinátákat csinálni (bár ez valahogy magától értedődő), tehát ezzel megadtunk egy origón átmenő egyenest, ami úgy áll, mint a v vektor, ezt már csak a helyére kell tolni, ehhez csak hozzákell adni a kapott ponthoz a D pont koordinátáit kész. Tehát az egyenesünk pontjait a következőképpen adjuk meg:

A kettő metszéspontja meg az a pont, ami mindkettő rajta van, és egybe esik, azaz meg kell keresni azt az alfát, bétát és gammát, amivel a két pont egybe esik:

Ezt átrendezve a következőt kapjuk:

Koordinátákkal felírva a következő egyenletrendszer lesz:

Mivel a számítógép nem ért az egyenletek levezetéséhez, ezért az ismeretleneket ki kell fejezni. Az ilyen kifejezésként való felírásra jó a Cramer-szabály. Bár ez elég macera, ha kézzel számolunk. De szépsége az, hogy csak összeadás és szorzás van benne és egyetlen egy osztás. Krámerozáshoz mátrix alakban kell felfirkálni az egyenletrendszert mátrixos alakban:

Mivel a d-a -k kiszámolhatók ezért jelöljük el g-kel őket, hogy többször ne kelljen kiszámolni őket.

A krámerozáshoz determinánsokat kell számolgatni, 4 darabot. Először a nagy baloldali mátrix determinánsát:

Nos ha ez a determináns nulla, akkor megis állhatunk, mert az egyenes párhuzamos a háromszöggel, vagy éppen rajta fekszik, mindkét esetben nem tudunk egyéretlmű metszéspontot megadni.

Még három determináns kell:

És innentől kezdve a megoldások kiszámolása már könnyű feladat:

Ezek után már csak értelmezni kell, amit kaptunk. Ezek a görögbetűk linerisan kombináló együtthatók. Gamma a v vektor együtthatója, egy szorzótényező, hogy a metszéspont mennyivel van előtte. Ha ez negatív, akkor a metszés pont a vektor "mögött" van. Az alfa és béta annak a két vektornak a kombináló együtthatója, amelyek az háromszög A pontjából indulnak ki és B illetve a C pontba mutatnak. Bármelyik negatív, a metszéspont tuti nincs a háromszögön, ha 1-nél nagyobb akkor sem. Ha a kettő között van, akkor sincs még nyert ügyünk, mert olyan pontokat is megadhat, amely nincs a háromszögön. A helyes megoldás ilyenkor az, hogy alfa+béta<=1, és ezzel készen vagyunk. Ezen tudás birtokában most már bárki megírhatja a játékát. ;-)