Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
248 views
in Technique[技术] by (71.8m points)

math - determine whether point lies inside triangle


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...