determine whether point lies inside triangle
The program needs to read the values of three coordinates
- P1(x1,y1)
- P2(x2,y2)
- P3(x3,y3)
as well as another coordinate P(x,y) and determine whether this point is inside a triangle formed from the 3 point above.
Answer
The proper way to do this is by calculating the barycentric coordinates of the fourth point given the three points of your triangle. The formula to compute them is given at the end of the section "Converting to barycentric coordinates", but I hope to provide a less mathematics-intense explanation here.
Assume, for simplicity, that you have a struct, point, that has values x and y. You defined your points as:
point p1(x1, y1);
point p2(x2, y2);
point p3(x3, y3);
point p(x,y); // <-- You are checking if this point lies in the triangle.
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)*p3
Rearranging 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.
It follows that each coefficient must be greater than 0 in order for the point p to lie within the area described by the three points.