how to find if point in triangle?
etp
must have learnt this somewhere in school, but I can't for the life of me
remember:
How do you find out whether point (x,y) is within a triangle (a,b,c)? It's
easy enough to check if it is within a square (x1,x2,y1,y2):
if ( (x1<x<x2)&&(y1<y<y2) )
{ /* within! */ )
else
{ /* not within! */ }
... what about checking for 5 sided? n sided?
thanks!
--
epa...@UNSPAMoznewmedia.com
remove UNSPAM to mail
Iain Davidson
etp wrote in message ...
>Hello, I really hope this question doesn't sound too stupid... I'm sure I
>must have learnt this somewhere in school, but I can't for the life of me
>remember:
>
>How do you find out whether point (x,y) is within a triangle (a,b,c)? It's
>easy enough to check if it is within a square (x1,x2,y1,y2):
>
>if ( (x1<x<x2)&&(y1<y<y2) )
> { /* within! */ )
>else
> { /* not within! */ }
>
>... what about checking for 5 sided? n sided?
If p is a point inside the triange abc then
area abc = area apb + area bpc + area cpa
if not
area abc < area apb + area bpc + area cpa
you can split up any polygon into triangles.
The area of triangle (x1,y1), (x2,y2), (x3,y3) =
is the absolute value of the determinant
x1 y1 1
x2 y2 1
x3 y3 1
Horst Kraemer
> Hello, I really hope this question doesn't sound too stupid... I'm sure I
> must have learnt this somewhere in school, but I can't for the life of me
> remember:
No. I don't think you learnt this explicitly at school.
> How do you find out whether point (x,y) is within a triangle (a,b,c)? It's
> easy enough to check if it is within a square (x1,x2,y1,y2):
Here you are checking it against a square with edge parallel to the
coordinate axis. That's the easiest case of all...
> if ( (x1<x<x2)&&(y1<y<y2) )
> { /* within! */ )
> else
> { /* not within! */ }
If you want to program it:
Tringle A : (xA.yA) B: (xB,yB) C: (xC,yC)
Test point P : (xP,yP)
d = (xB-xA)*(yC-yA)-(yB-yA)*(xC-xA);
b = (xP-xA)*(yC-yA)-(yP-yA)*(xC-xA);
c = (xB-xA)*(yP-yA)-(yB-yA)*(xP-xA);
if (d==0) {/* error, no triangle */}
if (d<0) { d=-d,b=-b;c=-c; }
within = 0<=b && 0<=c && b+c<d;
There are many interpretation of this formula. One of them is
If ABC are not on one straigth line then the vector P may be
represented in a unique way as
P = A + u(B-A) + v(C-A) (1)
P is within the triangle if u>=0 && v>=0 && u+v<=1
u=b/d and v=c/d are the solutions of the linear equation system (1)
for given P,A,B,C,D.
> ... what about checking for 5 sided? n sided?
That's a long story. Check the excellent FAQ of
comp.graphics.algorithms for an efficient algorithm. If the polygon is
guaranteed to be convex you may set up an algorithm similar to the
triangle method I proposed. If not a widely used formal approach is to
count the intersections of an arbitrary straight ray starting at P
with the edges of the n-gon. If this ray does not intersect a vertex
point of the polygon then P is within if and only if the number of the
intersections with edges is odd. The problem is very tricky - though -
if the ray intersects a vertex point of the polygon or if one edge of
the polygon lies fully within the ray...
Regards
Horst
Raymond Manzoni
> I had a bad feeling and here I'm again with my false claims!
>
> Note that the 4th method may be restated simpler :
> - if x and y are so that ap = x.ab +y.bc then p is in the triangle if
> 0<=x<=1 and 0<=y<=1 which is in fact a variant of the second one.
>
was right if written ap = x.(ab +y.bc) (exclusive) or if 0<=y<=x was
supposed...
I will try to stop posting after 2 in the morning, shame on me.
Raymond
Raymond Manzoni
> Hello, I really hope this question doesn't sound too stupid... I'm sure I
> must have learnt this somewhere in school, but I can't for the life of me
> remember:
>
> How do you find out whether point (x,y) is within a triangle (a,b,c)? It's
> easy enough to check if it is within a square (x1,x2,y1,y2):
>
> if ( (x1<x<x2)&&(y1<y<y2) )
> { /* within! */ )
> else
> { /* not within! */ }
>
> ... what about checking for 5 sided? n sided?
>
> thanks!
>
> --
> epa...@UNSPAMoznewmedia.com
> remove UNSPAM to mail
Hi,
Some ideas I had (if p is your (x,y) point) supposing a,b,c are
different:
- Draw the half-line starting from p and parallel to vector bc then it
must cut one and only one of the segments ab and ac.
- if you imagine p as the gravity center of the points a,b,c with various
weights then these must all be positive.
- if points of triangle a,b,c are drawn clockwise then determinants of
matrix with followings vectors in columns (for example) |ap,ab| and |bp,bc|
and |cp,ca| are all positives.
- if x and y are so that x.ap = ab +y.bc then p is in the triangle if p=a
or 0<x<=1 and 0<=y<=1
to solve this last thing multiply by a vector orthogonal to vector ap
to get y and then solve for x.
Will be all for this night. Good evening,
Raymond Manzoni
Raymond Manzoni
>
> Hi,
>
> Some ideas I had (if p is your (x,y) point) supposing a,b,c are
> different:
and non aligned !
>
>
> - Draw the half-line starting from p and parallel to vector bc then it
> must cut one and only one of the segments ab and ac.
>
> - if you imagine p as the gravity center of the points a,b,c with various
> weights then these must all be positive.
>
> - if points of triangle a,b,c are drawn clockwise then determinants of
> matrix with followings vectors in columns (for example) |ap,ab| and |bp,bc|
> and |cp,ca| are all positives.
>
> - if x and y are so that x.ap = ab +y.bc then p is in the triangle if p=a
> or 0<x<=1 and 0<=y<=1
no ! or (x>=1 and 0<=y<=1)
I had a bad feeling and here I'm again with my false claims!
Note that the 4th method may be restated simpler :
- if x and y are so that ap = x.ab +y.bc then p is in the triangle if
0<=x<=1 and 0<=y<=1 which is in fact a variant of the second one.
to solve this multiply by an orthogonal to vector bc (exchange the 2
components and change the sign of one of them for that purpose) to get x and the
same may be done for y.
Hope it's nearer of truth,
Raymond Manzoni
Zdislav V. Kovarik
etp <e...@home.com> wrote:
>Hello, I really hope this question doesn't sound too stupid... I'm sure I
>must have learnt this somewhere in school, but I can't for the life of me
>remember:
>
>How do you find out whether point (x,y) is within a triangle (a,b,c)?
>... what about checking for 5 sided? n sided?
If you are allowed to use arctangent and complex numbers, you can "count
how many times the contour runs around the given point". If the contour is
traced counterclockwise, the number of runs is 1 inside, 0 outside. Before
using the following MATLAB routine, you might check separately if the
point is on the boundary.
Cheers, ZVK(Slavek).
Here is the routine:
% runs.m calculates the index of a point P with respect
% to a closed polygonal path given by n points.
% Method: using Cauchy integral along the boundary
% ******> Input: XY , an n-by-2 matrix XY (the rows
% defining the points),
% P, a 2-component vector.
% defining the points),
% P, a 2-component vector.
% ******> Output: r, the net number of runs of XY around P
% It is assumed that the last point is connected
% to the first point.
% ******> Call: r=runs(XY,P)
% By Z.V. Kovarik, May 3, 1996
%
function r=runs(XY,P);
i=sqrt(-1);
P=P(1)+i*P(2);
Z=XY(:,1)+i*XY(:,2);
n=length(Z);
Z=[Z;Z(1)]-P; % closing up the path
Z=Z(1+(1:n))./Z(1:n); % complex rotations - unscaled
r=round(sum(atan(imag(Z)./(abs(Z)+real(Z))))/pi);
% end of routine
Charles H. Giffen
>
> Hello, I really hope this question doesn't sound too stupid... I'm sure I
> must have learnt this somewhere in school, but I can't for the life of me
> remember:
>
> easy enough to check if it is within a square (x1,x2,y1,y2):
>
> if ( (x1<x<x2)&&(y1<y<y2) )
> { /* within! */ )
> else
> { /* not within! */ }
>
>
>
> --
> epa...@UNSPAMoznewmedia.com
> remove UNSPAM to mail
The best algorithm to see if p is in triangle abc is to
check that a & p are on the same side of the line through
bc, that b & p are on the same side of the line through ca,
and that c & p are on the same side of the line through ab.
Pascal code which accomplishes this is:
type
Point = record
x,y : real
end;
function Det ( p,q : Point ) : real;
begin
Det := p.x*q.y - p.y*q.x
end;
function Cross ( p,q,r : Point ) : real;
begin
Cross := Det(q,r) - Det(p,r) + Det(p,q)
end;
function Sign ( t : real ) : integer;
begin
if (t > 0) then Sign := 1
else if (t < 0) then Sign := -1
else Sign := 0
end;
function SameSide ( a,b,p,q : Point ) : boolean;
{ returns true if p and q are on the same
side of the line through a and b }
begin
if Sign(Cross(a,b,p))*Sign(Cross(a,p,q)) = 1
then SameSide := TRUE
else SameSide := FALSE
end;
function InTriangle ( a,b,c,p : Point ) : boolean;
{ returns true if p is inside triangle abc }
begin
InTriangle :=
Sameside(a,b,c,p) and SameSide(b,c,a,p) and SameSide(c,a,b,p)
end;
However, since Cross(a,b,c) = Cross(b,c,a) = Cross(c,a,b),
there is redundancy in the above routine (there are also
other redundancies, too). Better, then, is the following:
function IsInTriangle ( a,b,c,p : Point ) : boolean;
var
abc : integer;
bc,ca,abap,bp,cp : real;
begin
bc := Det(b,c);
ca := Det(c,a);
ab := Det(a,b);
ap := Det(a,p);
bp := Det(b,p);
cp := Det(c,p);
abc := Sign(bc + ca + ab);
IsInTriangle :=
(abc*(bc-bp+cp)>0) and (abc*(ca-cp+ap)>0) and (abc*(ab-ap+bp)>0)
end;
--Chuck Giffen