Hi there,
does someone know how to check if a 2D-point is in a 2D-triangle?
Btw: Does someone know any good maths forums?
Search the forum or maybe the advanced forum, there is a fairly current thread on this very topic in one of them. I believe the title is something like ‘Simple geometry question’.
well, I can think of a fairly simple way off hand:
rotate the triangle so one side is along the x axis.
using the point slope formula, generate the equation of the hypotenuse for each other side.
plug in the x value of the point into the slope formulas and compare the y to the height of your point.
if the point is higher than the formula’s value, it is above the triangle.
if it is less, but greater than 0, it is inside.
just remember to rotate/translate your point with your rotation. you will need to intersect your sides to find the top vertex of the triangle if you don’t know where it is after tranformation. This will distinguish which slope to compare your value you to.
Hope this helps.
[This message has been edited by Cardinal (edited 07-07-2001).]
Make vectors from the point to all vertices and add up the angles between all the vectors and check to see if the angle is around 360 degrees.
Come on guys, are there no mathematicians here. Theres one solution that occures to me.
You have a triangle points 1, 2 and 3. And another point, 4.
Create 3 triangles each with point 4 as one vertex. You check the area of each one, but don’t get the absolute value. if you use the order as below then if the point lies insdie the trianglge all the signs will be the same for the area, if one is different then the point lies outside the triangle.
Equ1 = (x1-x4)(y2-y4) - (y1-y4)(x2-x4)
Equ2 = (x2-x4)(y3-y4) - (y2-y4)(x2-x4)
Equ3 = (x3-x4)(y1-y4) - (y3-y4)(x1-x4)
the simlest way to check it the signs are the same is to
Equ4 = (Equ1Equ2)(Equ2*Equ3)
Note however that if any of them are 0 then the point lies along the infinite line of one of the line segements made by the triangle edges, the easy way out is to say this isn’t on the triangle, otherwise its a simpl3 check to see if a point on a 2d line is on a line segement.
Hmm…
And how about a 3D-triangle and a 3D-Point. I know that the point and the triangle are on the same infinite plane…
In that case, change your 3D coordinates to 2D coordinates by first finding a suitable 2D basis. Then use that method mentioned by Zadkiel.
Yep, try the x and y coordinates first, check the area of the triangle they make, if its non zero the those axis will work, if not then try a different combination
the normal method of choosing what 2d plane projection of a triangle to use is to choose the one with the greatest normal
eg if (norm.x > norm.y && norm.x > norm.z )
use the yz plane
nope, I am not a mathematician… If I were, I would probably solve it using topology.
[i]the normal method of choosing what 2d plane projection of a triangle to use is to choose the one with the greatest normal[/]
You’d be surprised how similar that method is to mine, however it is slightly bigger and slower. With the area method the plane which gives you the biggest area is also the best, but when dealing with floating point values any plane of projection which gives you nonzero for the area will work.
Triangle vertices x,y,z
Point vertex m
a=m-x
b=m-y
c=m-z
If angle(a,b)+angle(a,c)+angle(b,c)=360° point is in triangle.
angle(a,b)+angle(a,c)+angle(b,c)=360°
=> cos(a,b)+cos(a,c)+cos(b,c)=1
ab=|a||b|cos(a,b) <=> (ab)/(|a|*|b|)=cos(a,b)
<=> (ab)/(|a||b|)+(ac)/(|a||c|)+(bc)/(|b||c|)=1
<=> (ab)²/(|a|²|b|²)+(ac)²/(|a|²|c|²)+(bc)²/(|b|²|c|²)=1
<=> ((ab)²|c|²+(ac)²|b|²+(bc)²|a|²)/(|a|²*|b|²*|c|²)=1
<=> (ab)²|c|²+(ac)²|b|²+(bc)²|a|²=|a|²*|b|²*|c|²
<=> (axbx+ayby+azbz)²(cx²+cy²+cz²)+(axcx+aycy+azcz)²(bx²+by²+bz²)+(bxcx+bycy+bzcz)(ax²+ay²+az²)=(ax²+ay²+az²)(bx²+by²+bz²)(cx²+cy²+cz²)
Or am I wrong?
angle(a,b)+angle(a,c)+angle(b,c)=360°
=> cos(a,b)+cos(a,c)+cos(b,c)=1
That statement is invalid in general. It is valid only with certain angles, but not all angles. See:
cos 290 + cos 20 + cos 50 = 1.924 >> 1
[This message has been edited by DFrey (edited 07-09-2001).]
doh!
You could reduce other problems from 3D to 2D too by the method of leaving the biggest component of the normal vector.
I’m using this for determining the section of a ray with a convex polygon (including holes). As I only need to know if it cuts (and not the position), I can project it to 2D and then use the standard algorithm for point in polygon.
BTW, I also use the area method for determining point in triangle, and it is the fastest method I’ve found so far.