有没有一种简单的方法来确定一个点是否在三角形内?是2D的,不是3D的。
当前回答
老实说,这就像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));
其他回答
我要做的是预先计算三个面法线,
在三维中通过边向量和面法向量的叉乘得到。 通过简单地交换分量和负一个,
对于任意一条边的内/外都是边法线和点到点向量的点积,改变符号。重复其他两(或更多)面。
好处:
在同一个三角形上进行多点测试,很多都是预先计算好的。 早期拒签的常见情况是外分多内分。(如果点分布偏向一侧,可以先测试这一侧。)
我在最后一次尝试谷歌和找到这个页面之前写了这段代码,所以我想我应该分享它。它基本上是Kisielewicz答案的优化版本。我也研究了重心法,但从维基百科的文章来看,我很难看出它是如何更有效的(我猜有一些更深层次的等价性)。不管怎样,这个算法的优点是不用除法;一个潜在的问题是边缘检测的行为取决于方向。
bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c)
{
int as_x = s.x - a.x;
int as_y = s.y - a.y;
bool s_ab = (b.x - a.x) * as_y - (b.y - a.y) * as_x > 0;
if ((c.x - a.x) * as_y - (c.y - a.y) * as_x > 0 == s_ab)
return false;
if ((c.x - b.x) * (s.y - b.y) - (c.y - b.y)*(s.x - b.x) > 0 != s_ab)
return false;
return true;
}
换句话说,思想是这样的:点s是在直线AB和直线AC的左边还是右边?如果是真的,它就不可能在里面。如果为假,则至少在“锥”内满足条件。现在,因为我们知道三角形(三角形)内的一个点必须与BC(以及CA)在AB的同一侧,我们检查它们是否不同。如果有,s就不可能在里面,否则s一定在里面。
计算中的一些关键字是线半平面和行列式(2x2叉乘)。也许一个更有教学意义的方法是将它看作是一个在AB、BC和CA的同一侧(左或右)的点。然而,上面的方法似乎更适合进行一些优化。
重心法Java版:
class Triangle {
Triangle(double x1, double y1, double x2, double y2, double x3,
double y3) {
this.x3 = x3;
this.y3 = y3;
y23 = y2 - y3;
x32 = x3 - x2;
y31 = y3 - y1;
x13 = x1 - x3;
det = y23 * x13 - x32 * y31;
minD = Math.min(det, 0);
maxD = Math.max(det, 0);
}
boolean contains(double x, double y) {
double dx = x - x3;
double dy = y - y3;
double a = y23 * dx + x32 * dy;
if (a < minD || a > maxD)
return false;
double b = y31 * dx + x13 * dy;
if (b < minD || b > maxD)
return false;
double c = det - a - b;
if (c < minD || c > maxD)
return false;
return true;
}
private final double x3, y3;
private final double y23, x32, y31, x13;
private final double det, minD, maxD;
}
上面的代码可以准确地处理整数,假设没有溢出。它也适用于顺时针和逆时针三角形。它不适用于共线三角形(但您可以通过测试det==0来检查)。
如果你要用同一个三角形测试不同的点,以重心为中心的版本是最快的。
重心版本在3个三角形点上是不对称的,所以它可能不如Kornel Kisielewicz的边缘半平面版本一致,因为浮点舍入误差。
图片来源:我根据维基百科关于重心坐标的文章制作了上面的代码。
其中一个最简单的方法来检查是否由三角形的顶点组成的面积 (x1,y1) (x2,y2) (x3,y3)是否为正。
面积可由公式计算:
1/2 [x1(y2–y3) + x2(y3–y1) + x3(y1–y2)]
或者python代码可以写成:
def triangleornot(p1,p2,p3):
return (1/ 2) [p1[0](p2[1]–p3[1]) + p2[0] (p3[1]–p1[1]) + p3[0] (p1[0]–p2[0])]
bool isInside( float x, float y, float x1, float y1, float x2, float y2, float x3, float y3 ) {
float l1 = (x-x1)*(y3-y1) - (x3-x1)*(y-y1),
l2 = (x-x2)*(y1-y2) - (x1-x2)*(y-y2),
l3 = (x-x3)*(y2-y3) - (x2-x3)*(y-y3);
return (l1>0 && l2>0 && l3>0) || (l1<0 && l2<0 && l3<0);
}
没有比这更有效率的了!三角形的每边都可以有独立的位置和方向,因此需要进行l1、l2和l3三个计算,每个计算需要进行2次乘法。一旦l1, l2和l3是已知的,结果只是一些基本的比较和布尔运算。
推荐文章
- 为什么Python的无穷散列中有π的数字?
- 四舍五入BigDecimal *总是*有两位小数点后
- 从数字中移除无关紧要的尾随零?
- 负数的Mod快把我的脑子都融化了
- 如何计算圆周长上的一点?
- 从整数流中找到运行中位数
- 在日历应用程序中建模重复事件的最佳方法是什么?
- 在任何情况下,您更喜欢高大o时间复杂度算法而不是低大o时间复杂度算法吗?
- 如何确保整数的除法总是四舍五入?
- 如何使用JavaScript比较软件版本号?数量(只)
- 跳跃表vs.二叉搜索树
- 如何使四舍五入百分比加起来为100%
- 是否有可能得到一个函数的所有参数作为单一对象内的函数?
- LL和LR解析之间的区别是什么?
- 如何缩小与已知的最小值和最大值的数字范围