Tocka in trikotnik + 3D

Kaksen je najhitrejsi in najboljsi algoritem za ugotavljanje, ali tocka lezi ali ne v trikotniku.
Sori mal je tko napisan, pa pliz hlp!

Hmm, pa poskusimo. Drugi način. (V tej obliki samo za trikotnike)

1. V točko položi premico (v poljubni smeri)
2. Prični računati presečne točke med stranicami in premico. Dobiš lahko več rezultatov:
a, ni presečišč (mimobežna premica). točka je definitivno izven trikotnika
b, samo eno presečišče. Primer, ko premica gre skozi eno od oglišč. Točka je izven trikotnika
c, dve presečišči. Tvoriš vektorja od točk do presečišča. Če sta isto usmerjena, je točka izven trikotnika. Če sta isto usmerjena, je v trikotniku.


Samo moje razmišljanje...

Jože

Tole je verjetno najhitrejši način kako ugotoviti ali je točka zunaj ali znotraj trikotnika:

A common way to check if a point is in a triangle is to find the vectors connecting the point to each of the triangle's three vertices and sum the angles between those vectors. If the sum of the angles is 2*pi then the point is inside the triangle, otherwise it is not. It works, but it is very slow. This text explains a faster and much easier method.

First off, forgive the nasty coloring. I'm really sorry about it. Honest.
Okay, A B C forms a triangle and all the points inside it are yellow. Lines AB, BC, and CA each split space in half and one of those halves is entirely outside the triangle. This is what we'll take advantage of.

For a point to be inside the traingle A B C it must be below AB and left of BC and right of AC. If any one of these tests fails we can return early.



But, how do we tell if a point is on the correct side of a line? I'm glad you asked.


If you take the cross product of [B-A] and [p-A], you'll get a vector pointing out of the screen. On the other hand, if you take the cross product of [B-A] and [p'-A] you'll get a vector pointing into the screen. Ah ha! In fact if you cross [B-A] with the vector from A to any point above the line AB, the resulting vector points out of the screen while using any point below AB yields a vector pointing into the screen. So all we need to do to distinguish which side of a line a point lies on is take a cross product.

The only question remaining is: how do we know what direction the cross product should point in? Because the triangle can be oriented in any way in 3d-space, there isn't some set value we can compare with. Instead what we need is a reference point - a point that we know is on a certain side of the line. For our triangle, this is just the third point C.

So, any point p where [B-A] cross [p-A] does not point in the same direction as [B-A] cross [C-A] isn't inside the triangle. If the cross products do point in the same direction, then we need to test p with the other lines as well. If the point was on the same side of AB as C and is also on the same side of BC as A and on the same side of CA as B, then it is in the triangle.

Implementing this is a breeze. We'll make a function that tells us if two points are on the same side of a line and have the actual point-in-triangle function call this for each edge.


function SameSide(p1,p2, a,b)
cp1 = CrossProduct(b-a, p1-a)
cp2 = CrossProduct(b-a, p2-a)
if DotProduct(cp1, cp2) >= 0 then return true
else return false

function PointInTriangle(p, a,b,c)
if SameSide(p,a, b,c) and SameSide(p,b, a,c)
and SameSide(p,c, a,b) then return true
else return false

Hm...
Samo potem moraš pa konstruirat ravnino, izračunat razdaljo točke od ravnine, to točko projecirat na ravnino in šele potem s pomočjo baricentričnih koordinat ugotovit ali je točka dejansko v trikotniku ali je samo na ravnini.
Or am I missing something?

Sej verjetno lahko predpostavimo, da bo tocka na isti ravnini kot trikotnik. Da se izracunati tudi s petimi dot produkti.