Matemaattinen ongelma

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Hei vaan.

Olen pähkäillyt erään matemaattisen ongelman kanssa viikko kausia, enkä millään keksi ratkaisua ongelmaan.

Ongelma kuuluu näin:

Jos minulla on kolmiulotteisessa avaruudessa kolmiot 1 ja 2, kolmio 1 muodostuu tunnetuista pisteistä A, B ja C, ja kolmio 2 muodostuu tunnetuista pisteistä D, E ja F.

Jos siirrän kolmion 2 tunnetun vektorin u verran, ja haluan selvittää menikö yksikään kolmion 2 piste kolmion 1 läpi. Toisin sanoen haluan tietää törmäsikö kolmio 2 kolmioon 1. (Leikkasivatko kolmiot toisensa)

Tarkoituksena olisi myös selvittää törmäyspisteet jos sellaisia on.

Osaako kukaan sanoa kuinka ongelma ratkaistaan?

Yritin ratkaista ongelman käyttäen hyväkseni vektorien piste- ja ristituloa, mutta jäljelle jäi aina liikaa tuntemattomia.

Olisi hienoa jos joku osaisi auttaa minua poloista.

Kommentit (10)

Vierailija

Tämä on tämmöinen nopea intuitio, mutta toivottavasti tästä on vähän apua. Eli jos kaksi kolmiota (oletetaan tässä nyt, että kolmion sisäpisteetkin ovat kolmion pisteitä) "törmäävät", niin joko sivut leikkaavat toisiaan jossakin vaiheessa tai toisen kolmion kulma osuu toisen kolmion pisteisiin liikkeen aikana. Ensimmäisessä tilanteessa liikkuvan kolmion sivu määrittää avaruudeen suunnikkaan, jolloin voit testata, että onko suunnikkaalla yhteisiä pisteitä paikallaan olevan kolmion kanssa. Toisessa tapauksessa liikkuvan kolmion kärkipiste piirtää avaruuteen janan ja voit testata onko janalla yhteisiä pisteitä paikallaan olevan kolmion kanssa. Mikäli et laske kolmion sisäpisteitä kolmion pisteiksi, niin voit jättää toisen tavan huomioimatta.

Tuossa voi helpostikin olla joku virhe, kun noin hatusta tuon vedin. Lisäksi tilanteen laskemiseksi on varmasti olemassa parempiakin menetelmiä.

Vierailija

Tapoja on varmaan muitakin, mutta tässä on yksi.

Olkoon origo O. Merkitään pisteestä A pisteeseen B kulkevaa vektoria AB. Muut pisteet merkitään vastaavasti. Muutenkin lihavointi tarkoittaa vektoria. Lihavoimaton iso kirjain tarkoittaa pistettä ja pieni kirjain skalaaria.

Tarkastellaan pistettä D. Kun tästä pisteestä siirrytään vektorin u verran, niin tullaan pisteeseen D’. Siis u = DD’. Olkoon r reaaliluku siten, että pisteen P paikkavektori OP = OD + ru on vektoreiden AB ja AC virittämällä tasolla. Piste P on siis samassa tasossa kolmion 1 kanssa. Olkoot s ja t reaalilukuja. Vektori OP voidaan tällöin ilmaista vektoreiden AB ja AC lineearikombinaationa. Siis OP = sAB + tAC. Jos nyt pätee
(1) s ≥ 0
(2) t ≥ 0 ja
(3) s + t ≤ 1
niin silloin piste P on kolmiossa 1 ja törmäys siis tapahtuu. Mikäli kaikki epäyhtälöt toimivat myös ilman yhtäsuuruutta, niin silloin piste P on kolmion 1 sisäpiste. Mikäli yksikin yhtäsuuruus on voimassa, niin silloin piste P on kolmion reunalla.

Sama pitää tehdä myös pisteille E ja F.

Olikohan tästä nyt mitään apua…

H
Seuraa 
Viestejä2622
Liittynyt16.3.2005

Muunna kaikki pisteet kolmion 1 mukaiseen koordinaatistoon siten, että kolmio 1 on xy-tasossa. Laske kolmion 2 kulmapisteiden kautta kulkevien u:n suuntaisten suorien ja xy-tason leikkauspisteet. Jos joku leikkauspiste osuus kolmioon 1, tarkista onko leikkauspisteen etäisyys pitkin suoraa kolmion 2 kulmaan pidempi kuin u:n pituus. Jos on, niin ko. kulma kulkee kolmion 1 läpi.

Vanha jäärä
Seuraa 
Viestejä1557
Liittynyt12.4.2005

Olen joskus, hamassa menneisyydessäni askaroinut tällaisten törmäystehtävien kanssa. Silloin ainakin parhaaksi strategiaksi osoittautui sellainen, jossa pyrittiin pääsemään mahdollisimman pitkälle pelkillä arvojen vertailuilla, laskemista tehtiin vain, kun mikään muu ei auttanut.

Tässäkin tapauksessa kolmioille kannattaa määrittää kolmion sisältävä särmiö eli särmiö, jonka sivut ovat koordinaattiakseleiden suuntaiset ja jonka tahkoihin kolmion kärjet yhtyvät. Tällainen särmiö on helppo määrittää min-max-periaatteella.

Näiden särmiöiden leikkaus on jälleen helppo määrittää jälleen min-max-periaatteella. Jos särmiöt eivät leikkaa, eivät kolmiotkaanvarmasti leikkaa.

Jos taas särmiöillä on yhteistä tilavuutta, potentiaalinen leikkaus tapahtuu pelkästään tässä. Silloin kannattaa tarkistaa, leikkaavatko tässä uudessa särmiössä olevat kolmioiden kyljet toisen kolmion määrittämää tasoa, eli laskea janan ja tason leikkauspisteet.

Sitten lopuksi pitää tietysti laskea leikkauspisteiden inklusiivisuus eli se, sijaitsevatko kolmion tason leikkauspisteet myös kolmion sisällä. Tämä voidaan ainakin tasossa tehdä vektoreiden ristitulotestillä (so. ovatko sisäpisteet kaikkien kolmion sivujen oikealla tai vasemmalla puolella, kun kolmiolla on tietty kiertosuunta). Avaruustapauksessa pitää ilmeisesti ottaa vielä huomioon kolmion määrittämän tason positiivinen normaali.

Toivottavasti pystyin selostamaan esittämäni lähestymistavan riittävän epäselvästi, että algoritmi on helposti vektorilaskennalla koodattavissa.

Lisäys 13.3.2008 klo 14.15: Mikä jäi tuossa alussa sanomatta, kyseessä on inkrementaalisen siirron periaate, jossa liikkuvaa kolmiota siirretään ympäripiirrettyjen särmiöiden mittoihin suhteutetulla askeleella aina testien välillä loppusijaintiinsa, mikäli se sinne saakka pääsee. Askelta säätämällä kolmiot saadaan helposti myös halutulle etäisyydelle toisistaan.

Toinen tapa olisi tietysti korvata siirron synnyttämä 5-tahokas kahdeksalla kolmiolla ja testata nämä stationaarista kolmiota vastaan.

PS. Toivottavasti tämä lisäys nyt vihdoin onnistuu.

Vanha jäärä

Vierailija

Kiitoksia kaikille neuvoista.

Päätin yrittää Kalen ehdottamalla tyylillä, mutta totesin että se on melko hankalaa kun on tarkoitus saada ulos sellaisia funktioita, jotka ovat yleispäteviä, sillä tarkoitus on rakentaa algoritmi joka laskee juuri näitä leikkauspisteitä sadoittain.

a = AB
b = AC

_i = vektorin i komponentti
_j = vektorin j komponentti
_k = vektorin k komponentti

Siis aloitin näin: (OA_i + sa_i + tb_i)i + (A_j + sa_j + tb_j)j + (A_k + sa_k + tb_k)k = (D_i + ru_i)i + (D_j + ru_j)j + (D_k + ru_k)k

Mutta jonkin aikaa laskettuani alkoi tuntua jotenkin mahdottomalta, josko joku saisi tuon järkevään muotoon minulle niin olisi hienoa.

mattile71
Seuraa 
Viestejä198
Liittynyt6.9.2006

Koodasin näitä joskus ammatikseni.
Tee asiat helpoimman kautta.Tee luokat vektori,jana ja taso.
Vektorille funktiot +, - , pistetulo(dot) ja ristitulo.
Sitten funktio, jolla tarkastetaan törmääkö jana tasoon.(Löytyy netistä,
jos et itse halua/osaa laskea)

Suosittelisin tuota H:n ideaa. "Ammu " kolmio 2 kolmion 1 määrittelemän
tason läpi.Saat kaksi kolmiota 2-uloitteiseen tasoon.Sitten tarkistat
niiden törmäyksen 2-uloittesella törmäysfunktiolla.
Jos kolmio ei mene ammuttaessa läpi niin muodostuu suunnikas.

Tee pieni asia kerrallaa.Yksi funktio kerrallaan.

Vanha jäärä
Seuraa 
Viestejä1557
Liittynyt12.4.2005

Tuli tuossa mieleen kokeilla "Kyllä Kuukkeli tietää" -totuutta. Ja tiesihän tuo:

http://mis.hevra.haifa.ac.il/~ishimshon ... mshoni.pdf

Samoilla kirjoittajilla on lähes sama artikkeli muuallakin:

http://www.ee.technion.ac.il/cgm/Comput ... lision.pdf

Lisää löytyy vaikka millä mitalla, kun kuukkeloi sanoilla "algorithm space triangle intersection" ja on tarmoa kahlata kaikki materiaali läpi.

Vanha jäärä

JAM
Seuraa 
Viestejä192
Liittynyt5.4.2006

Noissa Kuukkelin tarjoamissa artikkeleissa näyttää olevan asiaa.

Korjaan kuitenkin vähän Kalen kaavaa :

OP = OA + sAB + tAC. Jos nyt pätee
(1) s ≥ 0
(2) t ≥ 0 ja
(3) s + t ≤ 1
niin silloin piste P on kolmiossa 1 . Vastaavasti voidaan parametrisoida toinen kolmio:

OP = OD + uDE + vDF

Kun halutaan tutkia, osuuko jokin 2. kolmion piste 1. kolmioon on ratkaistava annetuilla u:n ja v:n arvoilla s, t ja x yhtälössä

OA+ sAB + tAC=OD + uDE + vDF +xu

Jos ratkaisussa s ja t toteuttavat ehdot (1)-(3) ja 0≤ x≤ 1, niin törmäys tapahtuu. Ratkaistavaksi tulee siis kolme yhtälöä kolmelle tuntemattomalle s, t ja x.

Vierailija
JAM
Korjaan kuitenkin vähän Kalen kaavaa :

OP = OA + sAB + tAC. Jos nyt pätee
(1) s ≥ 0
(2) t ≥ 0 ja
(3) s + t ≤ 1
niin silloin piste P on kolmiossa 1 .


Aivan. Ensimmäinen paikkavektori OA unohtui. Hyvä korjaus.

Vanha jäärä
Seuraa 
Viestejä1557
Liittynyt12.4.2005

Kun tuossa hieman itsekin katselin noita Kuukkelin tuloksia, niin havaitsin, että olin ehdottamassa aivan turhan mutkikkaita menetelmiä. Syy on siinä, että aiemmin olen pääosin ollut tekemisissä mutkikkaampien, yleensä ei-konveksisten tasomonikulmioiden kanssa. Kolmioiden kanssa selvitään vähemmälläkin.

Mutta edelleen olisin ehdottamassa aluksi tuota hierarkkista särmiötestiä, koska sillä on nopea tarkistaa, onko törmäysmahdollisuutta edes olemassa, eikä se vaadi muuta kuin lukujen vertailun. Liukulukulaskennan välttäminen on minun kokemuksieni mukaan kaikkein tehokkain geometristen algoritmien nopeuttaja.

Vanha jäärä

Uusimmat

Suosituimmat