Osuuko piste kolmioon.

Tarkista ensiksi, onko piste samassa tasossa kuin kolmio. https://www.quora.com/What-is-the-simplest-way-to-determine-if-4-points-lie-on-the-same-plane Tarkista sitten, onko piste kolmion sisällä vai ulkona. http://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle

Milloin piste (a,b) on monikulmion sisällä? Määrätään niiden monikulmion sivujen lukumäärä, jotka leikkaavat puolisuoraa x = a, y > b Jos se on pariton luku, niin piste on monikulmion sisällä. Ongelmana on vielä tapaus, missä puolisuora kulkee jonkin kulmapisteen kautta (tai on hyvin lähellä sitä). Silloin voisi käyttää suuntaan kulkevaa puolisuoraa.

Kertoisitko mikä on ongelmasi? Oletatko, että täällä joku avulias Aatu tekee pelin puolestasi ajankulukseen?

Nopein ja yksinkertaisin lienee laatikkotarkastelu. Siinä ensin määrität kolmiolle koordinaattiakseleiden suuntaisen minimilaatikon, mikä onnistuu helposti min-max-testeillä. Sen jälkeen tutkit, onko tarkasteleva piste laatikon sisällä. Kaikkeen tähän tarvitaan pelkkiä vertailuja, laskea ei tarvitse mitään.

Algoritmin ongelmana on se, että sen hyväksymisetäisyys vaihtelee kolmion koon ja aseman mukaisesti, mutta olet etsimässäkin likimenetelmää.

Jotta ei keksittäisi turhaan lisää ruutia, kannattaa katsella ajatuksella esimerkiksi seuraavat:

https://en.wikipedia.org/wiki/Möller–Trumbore_intersection_algorithm

http://cg-dev.ltas.ulg.ac.be/inf/Fast MinimumStorage RayTriangle Intersection.pdf

Kolmion nurkkapisteiden paikkavektorit olkoot R1,R2 ja R3.Näiden kautta kulkeva taso olkoon

(1) ax by c z = d eli (A.R) = d (= (A,R1) = (A,R2) = (A,R3))

Jotta tuo liikkuva piste P sijaitsisi haluamallasi tavalla, sen tulee olla sellaisen kolmikulmaisen laatikon sisällä jonka laatikon pohja ja katto ovat tason 1 suuntaiset ja näiden muodostamat tasot ovat etäisyyksillä e1 ja e2 tasosta (1). Lienee tarkoitus valita e1 = e2 = e.

Nämä tasot ovat

(2) ax by cz = d f ja (3) ax by cz = d - f (f > 0).

Tasojen (2) ja (3) etäisyys tasosta (1) on e =f /sqrt(a^2 b^2 c^2).Pisteen P pitää olla korkeintaan etäisyydellä e tasosta (1). Pelissä määritellään kuinka suuri e saa korkeintaan olla. Ensin siis tarkastetaan, että liikkuva piste P toteuttaa tämän ehdon.

Tason (1) yhtälö saadaan siitä, että sen(eräs) normaali on vektori A = ai b j c k.

Toisaalta normaali on (R2 - R1) x (R3 - R1) joten a,b ja c ovat laskettavissa.
Toinen yksikkönormaali on N = 1/ sqrt(a^2 b^2 c^2) (a i b j c k) ja sekä N että -N ovat yksikkönormaaleja.Ja d = (A,R1) = (A,R2) = (A,R3)

Pisteen P paikkavektori olkoon R(P). Pisteen P kautta kulkeva tason (1) suuntainen taso on

(4) (A,R) = (A,R(P))

joten P:n etäisyys tasosta (1) on g = l d - (A,R(P)) l / sqrt/(a^2 b^2 c^2). Osuma tulee kun

(5) g <= e.

Mutta osumaan tarvitaan myös että P on tuon laatikon sisällä myös pohjan (ja kannen) suunnassa.Jos nyt g toteuttaa ehdon (5) niin pisteen R(P) /- g N, joka on siis P:n projektio tasolle (1), ja jossa tai - merkki valitaan niin että normaali osoittaa tason (1) suuntaan pisteestä P, on oltava alkuperäisen kolmion sisällä.

Kolmion kärjet olivat R1,R2 ja R3, joten täytyy olla

(6) R(P) / - g N = t1 R1 t2 R2 t3 R3

missä barysentriset koordinaatit t(i) ovat ei-negatiiviset ja t(1) t(2) t(3) = 1.

Jos P toteuttaa ehdot (5) ja (6) niin osuma tuli.

Ohman