Problem
Given three corner points of a triangle, and one more point P. Write a function to check whether P lies within the triangle or not.Example
For example, consider the following program, the function should return true for P(10, 15) and false for P’(30, 15)B(10,30) / \ / \ / \ / P \ P' / \ A(0,0) ----------- C(20,0)
Solution
Method 1 - Area of triangles made by point and other 2 vertices of triangleLet the coordinates of three corners be (x1, y1), (x2, y2) and (x3, y3). And coordinates of the given point P be (x, y)
- Calculate area of the given triangle, i.e., area of the triangle ABC in the above diagram. Area A = [ x1(y2 - y3) + x2(y3 - y1) + x3(y1-y2)]/2
- Area A1 = Calculate area of the triangle PAB (using the same formula)
- Area A2 = Calculate area of the triangle PBC
- Area A3 = Calculate area of the triangle PAC
- If P lies inside the triangle, then A1 + A2 + A3 must be equal to A.
float area(int x1, int y1, int x2, int y2, int x3, int y3) { return Math.abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0); } boolean isInside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y) { // Calculate area of triangle ABC float A = area (x1, y1, x2, y2, x3, y3); // Calculate area of triangle PBC float A1 = area (x, y, x2, y2, x3, y3); // Calculate area of triangle PAC float A2 = area (x1, y1, x, y, x3, y3); // Calculate area of triangle PAB float A3 = area (x1, y1, x2, y2, x, y); // Check if sum of A1, A2 and A3 is same as A return (A == A1 + A2 + A3); }
But can this differentiate whether the point lies on the edges, I don't thing so. It can only tell whether it is in triangle or not.
Method 2 - Using Barycentric coordinates
Solve the following equation system:
p = p0 + (p1 - p0) * s + (p2 - p0) * t
The point p
is inside the triangle if 0 <= s
<
= 1
and 0
<
= t
<
= 1
and s + t
<
= 1
.s
,t
and 1 - s - t
are called the barycentric coordinates of the point p
.Now, the barycentric coordinates, generally called
alpha
, beta
, and gamma
, are calculated as follows:float alpha = ((p2.y - p3.y)*(p.x - p3.x) + (p3.x - p2.x)*(p.y - p3.y)) / ((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y)); float beta = ((p3.y - p1.y)*(p.x - p3.x) + (p1.x - p3.x)*(p.y - p3.y)) / ((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y)); float gamma = 1.0f - alpha - beta;If all of
alpha
, beta
, and gamma
are greater than 0
, then the point p
lies within the triangle made of points p1
, p2
, and p3
.The explanation behind this is that a point inside a triangle can be described using the points of the triangle, and three coefficients (one for each point, in the range [0,1]):
p = (alpha)*p1 + (beta)*p2 + (gamma)*p3Rearranging this function gives you the formula to compute barycentric coordinates, but I feel like the steps to do so might be beyond the scope of the question. They are provided on the Wikipedia page that I linked up top.
References
0 comments:
Post a Comment