有没有一种简单的方法来确定一个点是否在三角形内?是2D的,不是3D的。
当前回答
一般来说,最简单(也是最优)的算法是检查由边创建的半平面的哪一边是点。
以下是关于GameDev的一些高质量信息,包括性能问题。
这里有一些代码让你开始:
float sign (fPoint p1, fPoint p2, fPoint p3)
{
return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}
bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
float d1, d2, d3;
bool has_neg, has_pos;
d1 = sign(pt, v1, v2);
d2 = sign(pt, v2, v3);
d3 = sign(pt, v3, v1);
has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
return !(has_neg && has_pos);
}
其他回答
一般来说,最简单(也是最优)的算法是检查由边创建的半平面的哪一边是点。
以下是关于GameDev的一些高质量信息,包括性能问题。
这里有一些代码让你开始:
float sign (fPoint p1, fPoint p2, fPoint p3)
{
return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}
bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
float d1, d2, d3;
bool has_neg, has_pos;
d1 = sign(pt, v1, v2);
d2 = sign(pt, v2, v3);
d3 = sign(pt, v3, v1);
has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
return !(has_neg && has_pos);
}
我只是想用一些简单的向量数学来解释安德里亚斯给出的重心坐标解,它会更容易理解。
区域A定义为s * v02 + t * v01给出的任意向量,条件s >= 0, t >= 0。如果三角形v0 v1 v2内的任意一点,它一定在区域A内。
如果进一步限制s, t属于[0,1]。得到包含s * v02 + t * v01的所有向量的区域B,条件s, t属于[0,1]。值得注意的是,区域B的下部是三角形v0, v1, v2的镜像。问题来了,我们是否可以给定一定的s和t条件,来进一步排除区域B的低部分。
假设我们给出一个值s, t在[0,1]内变化。在下图中,点p位于v1v2的边缘。s * v02 + t * v01的所有向量沿着虚线通过简单向量和得到。在v1v2和虚线交点p处,我们有:
(1-S)|V0v2|/ |v0v2|= tp|v0v1|/ |v0v1|
得到1 - s = tp,然后1 = s + tp。如果任意t > tp,即1 < s + t where在双虚线上,则该向量在三角形外,任意t <= tp,即1 >= s + t where在单虚线上,则该向量在三角形内。
如果我们给出[0,1]中的任意s,对应的t必须满足1 >= s + t,对于三角形内的向量。
最后我们得到v = s * v02 +t * v01, v在三角形内,条件s, t, s+t属于[0,1]。然后翻译到点,我们有
P - p0 = s * (p1 - p0) + t * (p2 - p0), and s, t, s + t in [0,1]
和Andreas解方程组的解是一样的 P = p0 + s * (p1 - p0) + t * (p2 - p0),带s, t, s + t属于[0,1]。
一个简单的方法是:
找出连接 分别指向三角形的三个点 顶点和夹角之和 这些向量。如果它们的和 角度是2*那么点是 在三角形里面。
两个解释替代方案的好网站是:
黑卒和沃尔夫勒姆
bool point2Dtriangle(double e,double f, double a,double b,double c, double g,double h,double i, double v, double w){
/* inputs: e=point.x, f=point.y
a=triangle.Ax, b=triangle.Bx, c=triangle.Cx
g=triangle.Ay, h=triangle.By, i=triangle.Cy */
v = 1 - (f * (b - c) + h * (c - e) + i * (e - b)) / (g * (b - c) + h * (c - a) + i * (a - b));
w = (f * (a - b) + g * (b - e) + h * (e - a)) / (g * (b - c) + h * (c - a) + i * (a - b));
if (*v > -0.0 && *v < 1.0000001 && *w > -0.0 && *w < *v) return true;//is inside
else return false;//is outside
return 0;
}
从质心转换而来的几乎完美的笛卡尔坐标 在*v (x)和*w (y)双精度内导出。 在每种情况下,两个导出双精度对象前面都应该有一个*字符,可能是*v和*w 代码也可以用于四边形的另一个三角形。 特此签名只写三角形abc从顺时针abcd的四边形。
A---B
|..\\.o|
|....\\.|
D---C
o点在ABC三角形内 对于带有第二个三角形的测试,将此函数称为CDA方向,*v=1-*v后的结果应正确;* w = 1 - * w;为了四合院
老实说,这就像Simon P Steven的回答一样简单,但是用这种方法,你无法控制你是否想要包含三角形边缘上的点。
我的方法有点不同,但非常基本。考虑下面的三角形;
为了在三角形中有这个点我们必须满足三个条件
ACE角(绿色)应小于ACB角(红色) ECB角(蓝色)应小于ACB角(红色) 当点E和点C的x和y值应用于|AB|直线方程时,点E和点C的符号应该相同。
在此方法中,您可以完全控制单独包含或排除边缘上的点。所以你可以检查一个点是否在三角形中,例如,只包括|AC|边。
所以我的JavaScript解决方案是这样的;
function isInTriangle(t,p){ function isInBorder(a,b,c,p){ var m = (a.y - b.y) / (a.x - b.x); // calculate the slope return Math.sign(p.y - m*p.x + m*a.x - a.y) === Math.sign(c.y - m*c.x + m*a.x - a.y); } function findAngle(a,b,c){ // calculate the C angle from 3 points. var ca = Math.hypot(c.x-a.x, c.y-a.y), // ca edge length cb = Math.hypot(c.x-b.x, c.y-b.y), // cb edge length ab = Math.hypot(a.x-b.x, a.y-b.y); // ab edge length return Math.acos((ca*ca + cb*cb - ab*ab) / (2*ca*cb)); // return the C angle } var pas = t.slice(1) .map(tp => findAngle(p,tp,t[0])), // find the angle between (p,t[0]) with (t[1],t[0]) & (t[2],t[0]) ta = findAngle(t[1],t[2],t[0]); return pas[0] < ta && pas[1] < ta && isInBorder(t[1],t[2],t[0],p); } var triangle = [{x:3, y:4},{x:10, y:8},{x:6, y:10}], point1 = {x:3, y:9}, point2 = {x:7, y:9}; console.log(isInTriangle(triangle,point1)); console.log(isInTriangle(triangle,point2));