如何确定一个点是否在一个二维三angular形？

有一个简单的方法来确定一个点是否在三angular形内？ 这是2D，而不是3D。

Answer 1

一般来说，最简单的（也是非常优化的）algorithm是检查由该边所创build的半平面的哪一侧。

这里有一些关于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) { bool b1, b2, b3; b1 = sign(pt, v1, v2) < 0.0f; b2 = sign(pt, v2, v3) < 0.0f; b3 = sign(pt, v3, v1) < 0.0f; return ((b1 == b2) && (b2 == b3)); } 

Answer 2

解下面的方程组：

 p = p0 + (p1 - p0) * s + (p2 - p0) * t 

如果0 <= s <= 1且0 <= t <= 1且s + t <= 1 ，则点p在三angular形内部。

s ， t和1 - s - t称为点p的重心坐标 。

Answer 3

我同意安德烈亚斯·布林克 （ Andreas Brinck）的说法 ，重心坐标对于这个任务来说非常方便。 请注意，每次都不需要求解方程组：只是评估parsing解。 使用安德烈亚斯的符号，解决scheme是：

 s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py); t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py); 

Area是三angular形的（签名）区域：

 Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y); 

只需评估s ， t和1-st 。 点p在三angular形内部，当且仅当它们都是正的。

编辑：注意区域的上述expression式假定三angular形节点编号是逆时针方向。 如果编号是顺时针，这个expression式将返回一个负面的区域（但是正确的幅度）。 testing本身（ s>0 && t>0 && 1-st>0 ）不依赖于编号的方向，但是，由于上面乘以1/(2*Area)的expression式也会改变符号if三angular形节点的方向改变。

编辑2：为了更好的计算效率，请参阅下面的coproc的注释（这使得如果事先知道三angular形节点的方向（顺时针或逆时针），在expression式中除以2*Area s和t可以避免）。 在安德烈亚斯·布林克 （ Andreas Brinck ）的回答下的评论中，也可以看到佩罗·阿祖尔 （ Perro Azul ）的jsfiddle-code。

Answer 4

我在与Google进行最后一次尝试之前编写了这个代码，并find了这个页面，所以我想我会分享它。 这基本上是Kisielewicz答案的优化版本。 我也研究了重心法，但从维基百科的文章来看，我很难看到它是如何更有效率的（我猜测有一些更深层次的等价性）。 无论如何，这个algorithm的优点是不使用划分; 潜在的问题是取决于方向的边缘检测的行为。

 bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c) { int as_x = sx-ax; int as_y = sy-ay; bool s_ab = (bx-ax)*as_y-(by-ay)*as_x > 0; if((cx-ax)*as_y-(cy-ay)*as_x > 0 == s_ab) return false; if((cx-bx)*(sy-by)-(cy-by)*(sx-bx) > 0 != s_ab) return false; return true; } 

换句话说，这个想法是这样的：AB和AC两条线的左边还是右边？ 如果属实，它不能在里面。 如果错误的话，至less在满足条件的“锥体”内部。 既然我们知道三angular形（三angular形）内的一个点必须与BC（同样也是CA）的AB相同，我们检查它们是否不同。 如果他们这样做，s不可能在里面，否则s必须在里面。

计算中的一些关键字是行半平面和行列式（2×2叉积）。 也许更多的教学方法可能是把它看作是一个点，如果它是对同一方（左侧或右侧）AB，BC和CA的每一行。 上述方式似乎更适合一些优化。

Answer 5

Andreasdr和Perro Azul发布的重心方法的C＃版本。 请注意，如果s和t有相反的符号，则可以避免面积计算。 我用相当彻底的unit testingvalidation了正确的行为。

 public static bool PointInTriangle(Point p, Point p0, Point p1, Point p2) { var s = p0.Y * p2.X - p0.X * p2.Y + (p2.Y - p0.Y) * pX + (p0.X - p2.X) * pY; var t = p0.X * p1.Y - p0.Y * p1.X + (p0.Y - p1.Y) * pX + (p1.X - p0.X) * pY; if ((s < 0) != (t < 0)) return false; var A = -p1.Y * p2.X + p0.Y * (p2.X - p1.X) + p0.X * (p1.Y - p2.Y) + p1.X * p2.Y; if (A < 0.0) { s = -s; t = -t; A = -A; } return s > 0 && t > 0 && (s + t) <= A; } 

_{[ 编辑 ]}
^{接受@Pierre的build议修改; 看评论}

Answer 6

一个简单的方法是：

find将点连接到每个三angular形的三个顶点的vector，然后求和这些vector之间的angular度。 如果angular度的总和是2 * pi，那么点就在三angular形内。

解释替代scheme的两个好网站是：

黑木和狼

Answer 7

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; } 

上面的代码将整数准确地工作，假设没有溢出。 它也将使用顺时针和逆时针三angular形。 它不会与共线三angular形（但你可以通过testingdet == 0来检查）。

重心版本是最快的，如果你要用相同的三angular形testing不同的点。

重心版本在三个三angular形点不是对称的，所以由于浮点舍入误差，它可能不如Kornel Kisielewicz的边缘半平面版本一致。

信用：我从维基百科关于重心坐标的文章中做出了上述代码。

Answer 8

我所做的是预先计算三面法线，

• 在3D中由侧vector和面法向vector的交叉乘积。

• 在2D中通过简单地交换组件并且否定一个组件，

那么任何一边的内外都是边法线和点顶点向量的点积，变换符号。 重复其他两个（或更多）方面。

优点：

• 在相同的三angular形上进行多点testing，预先计算出的很多。

• 早期拒绝常见的情况比内部分外更多。 （如果点分布加权到一边，可以先testing那边。）

Answer 9

这是一个高效的Python实现：

 def PointInsideTriangle2(pt,tri): '''checks if point pt(2) is inside triangle tri(3x2). @Developer''' a = 1/(-tri[1,1]*tri[2,0]+tri[0,1]*(-tri[1,0]+tri[2,0])+ \ tri[0,0]*(tri[1,1]-tri[2,1])+tri[1,0]*tri[2,1]) s = a*(tri[2,0]*tri[0,1]-tri[0,0]*tri[2,1]+(tri[2,1]-tri[0,1])*pt[0]+ \ (tri[0,0]-tri[2,0])*pt[1]) if s<0: return False else: t = a*(tri[0,0]*tri[1,1]-tri[1,0]*tri[0,1]+(tri[0,1]-tri[1,1])*pt[0]+ \ (tri[1,0]-tri[0,0])*pt[1]) return ((t>0) and (1-st>0)) 

和一个输出示例：

Answer 10

通过使用重心坐标的parsing解（ Andreas Brinck指出）和：

• 没有在括号内分配乘法
• 避免通过存储他们几次相同的条款
• 减less比较（正如coproc和Thomas Eding指出的那样）

可以最大限度地减less“昂贵”操作的数量：

 function ptInTriangle(p, p0, p1, p2) { var dX = px-p2.x; var dY = py-p2.y; var dX21 = p2.x-p1.x; var dY12 = p1.y-p2.y; var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y); var s = dY12*dX + dX21*dY; var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY; if (D<0) return s<=0 && t<=0 && s+t>=D; return s>=0 && t>=0 && s+t<=D; } 

（代码可以粘贴在Perro Azul jsfiddle中 ）

导致：

• variables“回忆”：30
• variables存储：7
• 补充：4
• 减法：8
• 乘法：6
• 部门：没有
• 比较：4

这与Kornel Kisielewicz解决scheme（25次召回，1次存储，15次减法，6次乘法，5次比较）相比，可能会更好，如果需要顺时针/逆时针检测（需要6次召回，1次加法，2次减法，2乘法和1比较本身，使用分析溶液行列式，由rhgb指出）。

Answer 11

如果你正在寻找速度，这是一个可以帮助你的程序。

将三angular形顶点排列在其纵坐标上。 这最糟糕的是三个比较。 设Y0，Y1，Y2为三个sorting值。 通过他们画三个水平线，你把飞机分成两个半架和两个平板。 设Y是查询点的纵坐标。

 if Y < Y1 if Y <= Y0 -> the point lies in the upper half plane, outside the triangle; you are done else Y > Y0 -> the point lies in the upper slab else if Y >= Y2 -> the point lies in the lower half plane, outside the triangle; you are done else Y < Y2 -> the point lies in the lower slab 

花费两个比较。 正如你所看到的，快速拒绝是“边界板”以外的点实现的。

或者，您可以在横坐标上提供一个testing，以便快速排除左侧和右侧（ X <= X0' or X >= X2' ）。 这将同时执行一个快速的边界框testing，但是您也需要在横坐标上进行sorting。

最终，您将需要计算给定点相对于界定相关板块（上或下）的三angular形的两边的符号。 testing的forms是：

 ((X - Xi) * (Y - Yj) > (X - Xi) * (Y - Yj)) == ((X - Xi) * (Y - Yk) > (X - Xi) * (Y - Yk)) 

关于i, j, k组合的完整讨论（根据结果的结果，其中有6个）不在本答案的范围内，“作为练习留给读者”。 为了提高效率，它们应该是硬编码的。

如果您认为这个解决scheme是复杂的，那么请注意它主要涉及简单的比较（其中一些可以预先计算），加上6个减法和4个乘法，以防边界框testing失败。 后面的成本是难以打败的，因为在最糟糕的情况下，你无法避免将testing点与两边进行比较（其他答案中的方法成本较低，有些更糟糕，比如15次减法和6次乘法，有时是分裂）。

更新：剪切变换更快

如上所述，您可以使用两个比较快速定位由三个顶点坐标分隔的四个水平条带之一内的点。

您可以select执行一个或两个额外的Xtesting来检查边界框的内部（虚线）。

然后考虑由X'= X - m Y, Y' = Y给出的“剪切”变换，其中m是最高边缘的斜率DX/DY 。 这种转换将使三angular形的这一边垂直。 而且由于你知道你在中间水平的哪一侧，所以就三angular形的一边testing符号就足够了。

假设您预先计算了斜率m ，以及剪切后的三angular形顶点的X'和边的方程系数X = m Y + p ，则在最坏的情况下

• 纵向分类的两个纵坐标比较;
• 可选地用于边界框拒绝的一个或两个横坐标比较;
• 计算X' = X - m Y ;
• 一个或两个与剪切三angular形的横坐标的比较;
• 一个符号testingX >< m' Y + p'相对于剪切三angular形的相关侧。

Answer 12

如果你知道三个顶点的坐标和特定点的坐标，那么你可以得到整个三angular形的面积。 之后，计算三个三angular形区域的面积（一个点是给定的点，另外两个是三angular形的任意两个顶点）。 因此，你会得到三个三angular形的区域。 如果这些区域的总和等于总面积（你之前得到的），那么这个点应该在三angular形内。 否则，这个点不在三angular形内部。 这应该工作。 如果有任何问题，请告诉我。 谢谢。

Answer 13

存在讨厌的边缘条件，其中点恰好在两个相邻三angular形的共同边缘上。 这个点不能在两个三angular形中，也不能在两个三angular形中。 你需要一个任意但一致的方式来分配点。 例如，通过点画一条水平线。 如果该线与右侧三angular形的另一侧相交，则将该点视为在三angular形内。 如果交叉点在左边，则该点在外面。

如果点所在的线是水平的，则使用上方/下方。

如果该点位于多个三angular形的共同顶点上，则使用其中心点形成最小angular度的三angular形。

更多的乐趣：三个点可以在一个直线（零度），例如（0,0） – （0,10） – （0,5）。 在三angular化algorithm中，必须切掉“耳朵”（0,10），产生的“三angular形”是直线的退化情况。

Answer 14

我只是想用一些简单的vectormath来解释Andreas给出的重心坐标解决scheme，这将更容易理解。

1. 面积A被定义为由s * v02 + t * v01给出的任何向量，条件s> = 0且t> = 0。如果三angular形v0，v1，v2内的任何点必须在区域A内。

2. 如果进一步限制s，并且t属于[0，1]。 我们得到包含s * v02 + t * v01的所有向量的区域B，条件s，t属于[0，1]。 值得注意的是，B区的低部分是三angular形v0，v1，v2的镜像。 问题在于如果我们可以给定s和t的某些条件来进一步排除B区的低部分。

3. 假设我们给出一个值s，t在[0，1]中变化。 在下面的图片中，点p在v1v2的边缘。 s * v02 + t * v01中的所有vector沿虚线沿简单vector和。 在v1v2和虚线交叉点p，我们有：

（1-s） | v0v2 | / | v0v2 | = tp | v0v1 | / | v0v1 |

我们得到1 – s = tp，那么1 = s + tp。 如果有任何t> tp，其中1 <s + t其中是双点划线，则该向量在三angular形之外，则任何t <= tp，其中1> = s + t其中单点划线上，向量是三angular内。

那么如果给定[0，1]中的任意s，则对应于t的三angular形内的向量必须满足1> = s + t。

所以最后得到v = s * v02 + t * v01，v在条件s的三angular形内，t，s + t属于[0，1]。 然后转化为点，我们有

p0 = s *（p1-p0）+ t *（p2-p0），其中s，t，s + t在[0,1]

这与Andreas解方程系统p = p0 + s *（p1-p0）+ t *（p2-p0）相同，s，t，s + t属于[0,1]。

Answer 15

在Python中的其他function，比开发者的方法 （至less对我来说）更快，并由CédricDufour解决scheme启发：

 def ptInTriang(p_test, p0, p1, p2): dX = p_test[0] - p0[0] dY = p_test[1] - p0[1] dX20 = p2[0] - p0[0] dY20 = p2[1] - p0[1] dX10 = p1[0] - p0[0] dY10 = p1[1] - p0[1] s_p = (dY20*dX) - (dX20*dY) t_p = (dX10*dY) - (dY10*dX) D = (dX10*dY20) - (dY10*dX20) if D > 0: return ( (s_p >= 0) and (t_p >= 0) and (s_p + t_p) <= D ) else: return ( (s_p <= 0) and (t_p <= 0) and (s_p + t_p) >= D ) 

你可以用下面的方法testing它

 X_size = 64 Y_size = 64 ax_x = np.arange(X_size).astype(np.float32) ax_y = np.arange(Y_size).astype(np.float32) coords=np.meshgrid(ax_x,ax_y) points_unif = (coords[0].reshape(X_size*Y_size,),coords[1].reshape(X_size*Y_size,)) p_test = np.array([0 , 0]) p0 = np.array([22 , 8]) p1 = np.array([12 , 55]) p2 = np.array([7 , 19]) fig = plt.figure(dpi=300) for i in range(0,X_size*Y_size): p_test[0] = points_unif[0][i] p_test[1] = points_unif[1][i] if ptInTriang(p_test, p0, p1, p2): plt.plot(p_test[0], p_test[1], '.g') else: plt.plot(p_test[0], p_test[1], '.r') 

这需要很多的阴谋，但是这个网格在0.0195319652557秒内被testing了0.0844349861145秒的开发者代码 。

最后的代码评论：

 # Using barycentric coordintes, any point inside can be described as: # X = p0.x * r + p1.x * s + p2.x * t # Y = p0.y * r + p1.y * s + p2.y * t # with: # r + s + t = 1 and 0 < r,s,t < 1 # then: r = 1 - s - t # and then: # X = p0.x * (1 - s - t) + p1.x * s + p2.x * t # Y = p0.y * (1 - s - t) + p1.y * s + p2.y * t # # X = p0.x + (p1.x-p0.x) * s + (p2.x-p0.x) * t # Y = p0.y + (p1.y-p0.y) * s + (p2.y-p0.y) * t # # X - p0.x = (p1.x-p0.x) * s + (p2.x-p0.x) * t # Y - p0.y = (p1.y-p0.y) * s + (p2.y-p0.y) * t # # we have to solve: # # [ X - p0.x ] = [(p1.x-p0.x) (p2.x-p0.x)] * [ s ] # [ Y - p0.Y ] [(p1.y-p0.y) (p2.y-p0.y)] [ t ] # # ---> b = A*x ; ---> x = A^-1 * b # # [ s ] = A^-1 * [ X - p0.x ] # [ t ] [ Y - p0.Y ] # # A^-1 = 1/D * adj(A) # # The adjugate of A: # # adj(A) = [(p2.y-p0.y) -(p2.x-p0.x)] # [-(p1.y-p0.y) (p1.x-p0.x)] # # The determinant of A: # # D = (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x) # # Then: # # s_p = { (p2.y-p0.y)*(X - p0.x) - (p2.x-p0.x)*(Y - p0.Y) } # t_p = { (p1.x-p0.x)*(Y - p0.Y) - (p1.y-p0.y)*(X - p0.x) } # # s = s_p / D # t = t_p / D # # Recovering r: # # r = 1 - (s_p + t_p)/D # # Since we only want to know if it is insidem not the barycentric coordinate: # # 0 < 1 - (s_p + t_p)/D < 1 # 0 < (s_p + t_p)/D < 1 # 0 < (s_p + t_p) < D # # The condition is: # if D > 0: # s_p > 0 and t_p > 0 and (s_p + t_p) < D # else: # s_p < 0 and t_p < 0 and (s_p + t_p) > D # # s_p = { dY20*dX - dX20*dY } # t_p = { dX10*dY - dY10*dX } # D = dX10*dY20 - dY10*dX20 

Answer 16

当你确定三angular形是顺时针的时，我需要在“可控环境”中检查三angular形。 于是，我带着佩罗·阿祖尔 （ Perro Azul ）的小伙子，按照coproc的build议对这种情况进行了修改。 也删除了冗余0.5和2的乘法，因为它们只是相互抵消。

http://jsfiddle.net/dog_funtom/H7D7g/

这里是Unity的等效C＃代码：

 public static bool IsPointInClockwiseTriangle(Vector2 p, Vector2 p0, Vector2 p1, Vector2 p2) { var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * px + (p0.x - p2.x) * py); var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * px + (p1.x - p0.x) * py); if (s <= 0 || t <= 0) return false; var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y); return (s + t) < A; } 

Answer 17

假设我使用JavaScript编写的高性能代码（文章如下）：

 function pointInTriangle (p, p0, p1, p2) { return (((p1.y - p0.y) * (px - p0.x) - (p1.x - p0.x) * (py - p0.y)) | ((p2.y - p1.y) * (px - p1.x) - (p2.x - p1.x) * (py - p1.y)) | ((p0.y - p2.y) * (px - p2.x) - (p0.x - p2.x) * (py - p2.y))) >= 0; } 

pointInTriangle（p，p0，p1，p2） – 用于逆时针三angular形

pointInTriangle（p，p0，p1，p2） – 用于顺时针三angular形

看看jsFiddle（包括性能testing），还有一个单独的函数http://jsfiddle.net/z7x0udf7/3/

受此启发： http : //www.phatcode.net/articles.php?id=459

Answer 18

最简单的方法，它适用于所有types的三angular形只是简单地确定P点A，B，C点angular度的angular度。 如果任何angular度大于180.0度，那么它是在外面，如果是180.0，那么它是在圆周上，如果acos欺骗你，小于180.0，那么它在里面。看看理解http：// math-physics -psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

Answer 19

说实话，就像Simon P Steven的答案一样简单，但是这种方法对于是否要包含或不包含三angular形边缘上的点没有明确的控制。

我的方法有点不同，但非常基本。 考虑下面的三angular形;

为了在三angular形中有一个点，我们必须满足三个条件

1. ACEangular度（绿色）应小于ACBangular度（红色）
2. ECBangular度（蓝色）应小于ACBangular度（红色）
3. 当它们的x和y值被应用于| AB |的等式时，点E和点C应该具有相同的符号 线。

在这种方法中，您可以完全控制单独包含或排除边上的点。 所以你可以检查一个点是否在只包含| AC |的三angular形中 边缘例如。

所以我的JavaScript解决scheme如下：

 function isInTriangle(t,p){ function isInBorder(a,b,c,p){ var m = (ay - by) / (ax - bx); // calculate the slope return Math.sign(py - m*px + m*ax - ay) === Math.sign(cy - m*cx + m*ax - ay); } function findAngle(a,b,c){ // calculate the C angle from 3 points. var ca = Math.hypot(cx-ax, cy-ay), // ca edge length cb = Math.hypot(cx-bx, cy-by), // cb edge length ab = Math.hypot(ax-bx, ay-by); // 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)); 

Answer 20

 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); } 

它不能比这更有效率！ 三angular形的每一边都可以有独立的位置和方向，因此需要三个计算：l1，l2和l3确实需要包含2次乘法。 一旦知道了l1，l2和l3，结果就是几个基本的比较和布尔运算。