确定点是否位于三角形内 [英] 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)

以及另一个坐标P(x，y)并确定该点是否在由上方3个点形成的三角形内.

as well as another coordinate P(x,y) and determine whether this point is inside a triangle formed from the 3 point above.

推荐答案

做到这一点的正确方法是通过计算重心坐标.在转换为重心坐标"部分的末尾给出了计算它们的公式，但是我希望在此提供较少的数学上的解释.

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.

为简单起见，假设您有一个结构point，其值为x和y.您将点定义为:

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.

现在，重心坐标(通常称为alpha，beta和gamma)的计算如下:

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;

如果所有alpha，beta和gamma均大于0，则点p位于由点p1，p2和p3组成的三角形内

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.

其背后的解释是，可以使用三角形的点和三个系数(每个点一个，在[0,1]范围内)来描述三角形内的点:

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

重新排列此函数为您提供了计算重心坐标的公式，但是我觉得这样做的步骤可能不在问题范围内.它们在我最上面链接的Wikipedia页面上提供.

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.

因此，每个系数都必须大于0，以使点p位于三个点所描述的区域内.

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.

这篇关于确定点是否位于三角形内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！