Menu
The program needs to read the values of three coordinates
as well as another coordinate P(x,y) and determine whether this point is inside a triangle formed from the 3 point above.
888
Barycentric coordinates can be used to express the position of any point located on the triangle with three scalars. The location of this point includes any position inside the triangle, any position on any of the three edges of the triangles, or any one of the three triangle's vertices themselves.
Draw a horizontal line to the right of each point and extend it to infinity. Count the number of times the line intersects with polygon edges. A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon. If none of the conditions is true, then point lies outside.
One simple way of finding whether the point is inside or outside a simple polygon is to test how many times a ray, starting from the point and going in any fixed direction, intersects the edges of the polygon. If the point is on the outside of the polygon the ray will intersect its edge an even number of times.
If the cross products do point in the same direction, then we need to test p with the other lines as well. If the point was on the same side of AB as C and is also on the same side of BC as A and on the same side of CA as B, then it is in the triangle.
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.
136
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
