## 2015. január 30., péntek

### PROJECT A POINT ONTO THE SURFACE OF THE TRIANGLE

PROJECT A POINT ONTO THE SURFACE OF THE TRIANGLE

in the variable names d means distance,length, magnitude; 3d means three dimensional. If 3d not used then it is 2D.
To get IT point I will use line-line intersection.
The coordinates should be flattened so this time I project from above so I flatten Z.
Example:  P1 [x,y,z] = P1[x,y,0] or just use point2 variable type to calculate P1[x,y]
Draw a line L1 from any Triangle point to T point.
The Vector from P3 through T which is L1 will be then:
normalize(T-P3)

Now, this line we intersect with the other line P2-P1 to get the exact point through T lies on the Line.
This is necessary because our IT point lays exactly on this line.
Get the angles:
α = acos(dot normalize(P3-P2) normalize(P3-T))
Γ = acos(dot normalize(T-P3) normalize(P1-P2))
To Get the lenght of the dP2IP1 first get the lenght of dP2P3
dP2P3 = SQRT((P3.x-P2x)^2+(P3.y-P2y)^2)
Then
dP2P3/(sin Γ)=dP2IP1/(sin α) therefore:
dP2IP1 = asin (dP2P3/(sin Γ) * (sin α))
Make IP1 out of the gathered data:
IP1 = normalize(P2-P1)*dP2IP1 + P2

We have to convert this length dP2IP1 to the 3d lenght of the P2-IP1by using ratios. This means if the P2-IP1 lenght have a ratio of the whole length of the 2d P2-P1 line then the 3D line 3dP2IP1 lenght will have the same ratio. Therefore:
ratio = dP2IP1/dP2P1
Now have to caclulate the other lenght dTP3 and ratio2. Width 3dIP1P3 whic will give the IT point.
3dIP1P3 = SQRT((IP1.x-P3.x)^2+(IP1.y-P3.y)^2)
ratio2 = SQRT((T.x-P3.x)^2+(T.y-P3.y)^2)/3dIP1P3
Calulate the real 3d lenght of P2-P1 by using triagle law.
So it is dP2P1 2d lenght and the Z coords will make the other lenght of
the 90 degree triangle to calculate the 3d lenght of the P2-P1. 3ddP2P1 = SQRT(P2.z-P1.Z)^2+dP2P1^2)

Now the rest With 3d coords:
3dIP1 = normalize(P2-P1) * 3ddP2P1*ratio + P2
3ddP3IP1 = sqrt((IP1.z-P3.z)^2 + sqrt((IP1.x-P3.x)^2+(IP1.y-P3.y)^2))
Finally the T1 point:
T1=normalize (P3-IP1)*3ddP3IP1*ratio2 + P3

To accelerate the code use the magnitudes and normalizations only once where possible.

## 2015. január 29., csütörtök

### "EARLISH" DETERMINATION THAT THE POINT IS INSIDE THE DOMAIN OF THE TRIANGLE OR NOT.

"EARLISH" DETERMINATION THAT THE POINT
IS INSIDE THE DOMAIN OF THE TRIANGLE OR NOT.

To check that T is actually in triangle P1,P2,P3 we need totest the α,ß,Γ angles individually. And if any of the angle is bigger than 180.0 then the point is outside of the domain.To calculate these angles make 3 vectors out of the triangle points and T.

vec1 = normalize( P1-T)
vec2 = normalize( P2-T)
vec3 = normalize( P3-T)

Then the angles:
α = acos (dot vec1 vec2)
ß = acos (dot vec1 vec3)
Γ = acos (dot vec3 vec2)

if α>180.0 or ß>180.0 or Γ>180.0 then the point is outside of the triangle's domain. Well if any of the angle is 180.0 degree exactly then it is on the circumference of the triangle.

Now  you got to watch out that the dumb acos cannot do more than 180.0 so if any of those 2 is equals to the third than it is likely that you have the smaller side so you have to 360-value to get the real, also if you add the angles together and it is not 360.0 you can be sure that acos did cheat on one of them and it does lies outside of a triangle!

## 2015. január 27., kedd

### FAST LINE-CIRCLE INTERSECTION BASED ON TRIANGLE LAWS

"EARLY" DETERMINING INTERSECTION TYPE.

(Magnitude or distance variables are starting with d)

Get the distance (magnitude) in between center point C and P1 line point and C and P2 point
using triangle method.

dP1C = sqrt((C.x - P1.x)^2 + (C.y - P1.y)^2)
dP2C = sqrt((C.x - P2.x)^2 + (C.y - P2.y)^2)

If (dP1C==r and dP2C==r) then the line is a chord, therefore the intersection points are P1 and P2
If (dP1C<r and dP2C<r) then the line is inside the circle and it does not intersects.
If (dP1C<r and dP2C==r) or (dP1C==r and dP2C<r) then the line is inside the circle and the
intersection point is P1 or P2 based on which one is on the circle (dP1C or dP2C equals to radius).
If (dP1C==r and dP2C>r) or  (dP1C==r and dP2C>r)  or (dP1C>r and dP2C>r) then
the tangent angle THETA Θ and the angle OMEGA in between P1-C and P1-P2 will define
that the line is intersecting or not.

The tangent point is T1. The angle in between tangent
and radius is always 90 degree, therefore it is a triangle with 90 degree.

The tangent angle Θ = Asin(r/dP1C)  // (sin(90) = 1.0)
The omega: Ω = acos((dP1C^2 + dP1P2^2 - dP2C^2)/(2*dP1C*dP1P2))

If (Θ>Ω and dP1C==r and dP2C>r) or (Θ>Ω and dP2C==r and dP1C>r) then the line intersects
with the circle at two point and one of the point is the P1 or P2 depends on which one
is in the circumference (dP1C==r or dP2C==r). The other intersection point have to be calculated.
If (Θ<Ω and dP1C>r and dP2C>r) Then there is two intersection point and only this time both have
to be calculated.
If (Θ=Ω and dP1C==r) or (Θ=Ω and dP2C==r ) then the line will be tangent to
the circle and There is one intersection point.
If (Θ<Ω and dP1C==r and dP2c>r) or (Θ<Ω and dP2C==r and dP1c>r)
then the end of the line is on the cirlce.
Therefore the one (dP1C or dP2c) equals to the radius that point is on the circle.

FASTEST METHOD FOR DOUBLE OR SINGLE INTERSECTION  USING TRIANGLE CHORDS LAW.
(this method cant be used when
the dP1C<r and dP2C>r  or dP1C>r and dP2C<r for this call function below)

Reuse the variables from the early determination.
To get α = asin(dP1C/ (r/sin(Ω))
To get Γ= 180 - Ω - α
To get dP1IP1 = sin(Γ)*(r/sin(Ω))
To get ß=180-α
To get ε=180-2ß
dIP1IP2 = 2r*sin(ε/2)

So the intersection points are:
IP1 = (normalize P1-P2)*dP1IP1+P1
IP2 = (normalize P1-P2)*(IP1IP2+dP1IP1)+IP1

because the magnitude calculated before at early determination the normalization can be done by hand by dividing the translated vector with the magnitude. Saves some processing time.

If dP1C==r then reorganize your code that:

ß = Ω //calculated at early determination
ε =180-(2*BETA)
IP1 = P1 //  dP1C == r  therefore P1=IP1
dP1IP1 = 0
α = No need to calculate
Γ = No need to calculate

then like above:
dIP1IP2 = 2r*sin(ε/2)
So intersection points are:
IP1 = P1
IP2 = (normalize P1-P2)*dIP1IP2 +IP1

CALCULATE SINGLE INTERSECTION IN CASE ONE OF THE POINT IS INSIDE THE CIRCLE'S DOMAIN

To get Beta ß=acos(dot (normalize C-P1) (normalize P1-P2))
To get Gamma Γ=asin(dP1C/(r/sin(ß)))
To get Epsilon ε = 180-(Γ+ß)
To get P1-IP1's magnitude: dP1IP1 = (r/sin(ß))*sin(ε)
IP2 =(normalize(P1-P2)*dP1IP1)+P1