如何确定一个点是否在二维三角形中?

Is there an easy way to determine if a point is inside a triangle? It's 2D, not 3D.

是否有一种简单的方法来确定一个点是否在一个三角形中?2 d,3 d。

22 个解决方案

#1

In general, the simplest (and quite optimal) algorithm is checking on which side of the half-plane created by the edges the point is.

通常，最简单(也是最优)的算法是检查由边创建的半平面的哪一面。

Here's some high quality info in this topic on GameDev, including performance issues.

这里有一些关于GameDev的高质量信息，包括性能问题。

And here's some code to get you started:

这里有一些代码可以让你开始:

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

#2

Solve the following equation system:

求解如下方程系统:

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

The point p is inside the triangle if 0 <= s <= 1 and 0 <= t <= 1 and s + t <= 1.

点p在三角形中如果0 <= s <= 1和0 <= t <= 1, s + t <= 1。

s,t and 1 - s - t are called the barycentric coordinates of the point p.

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

#3

I agree with Andreas Brinck, barycentric coordinates are very convenient for this task. Note that there is no need to solve an equation system every time: just evaluate the analytical solution. Using Andreas' notation, the solution is:

我同意Andreas Brinck的观点，重心坐标对于这个任务非常方便。注意，没有必要每次都解一个方程系统:只要对解析解求值即可。使用Andreas的表示法，解决方案是:

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

where Area is the (signed) area of the triangle:

面积的三角形的面积(签名):

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

Just evaluate s, t and 1-s-t. The point p is inside the triangle if and only if they are all positive.

只是评估s t和1-s-t。三角形内的p点是当且仅当他们都是积极的。

EDIT: Note that the above expression for the area assumes that the triangle node numbering is counter-clockwise. If the numbering is clockwise, this expression will return a negative area (but with correct magnitude). The test itself (s>0 && t>0 && 1-s-t>0) doesn't depend on the direction of the numbering, however, since the expressions above that are multiplied by 1/(2*Area) also change sign if the triangle node orientation changes.

编辑:注意该区域的上述表达式假定三角形节点编号是逆时针的。如果编号是顺时针的，这个表达式将返回一个负值区域(但大小是正确的)。但是，测试本身并不依赖于编号的方向，因为上面的表达式乘以1/(2*面积)也会随着三角形节点方向的改变而改变。

EDIT 2: For an even better computational efficiency, see coproc's comment below (which makes the point that if the orientation of the triangle nodes (clockwise or counter-clockwise) is known beforehand, the division by 2*Area in the expressions for s and t can be avoided). See also Perro Azul's jsfiddle-code in the comments under Andreas Brinck's answer.

编辑2:为了获得更好的计算效率，请参阅下面的coproc的评论(这说明如果预先知道三角形节点的朝向(顺时针或逆时针方向)，那么在s和t的表达式中就可以避免2*区域的划分)。在Andreas Brinck的回答下的评论中也可以看到Perro Azul的jsfiddle-code。

#4

I wrote this code before a final attempt with Google and finding this page, so I thought I'd share it. It is basically an optimized version of Kisielewicz answer. I looked into the Barycentric method also but judging from the Wikipedia article I have a hard time seeing how it is more efficient (I'm guessing there is some deeper equivalence). Anyway, this algorithm has the advantage of not using division; a potential problem is the behavior of the edge detection depending on orientation.

在最后一次尝试使用谷歌并找到这个页面之前，我编写了这段代码，所以我想我要分享它。它基本上是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;}

In words, the idea is this: Is the point s to the left of or to the right of both the lines AB and AC? If true, it can't be inside. If false, it is at least inside the "cones" that satisfy the condition. Now since we know that a point inside a trigon (triangle) must be to the same side of AB as BC (and also CA), we check if they differ. If they do, s can't possibly be inside, otherwise s must be inside.

换句话说，它的意思是:点s在AB和AC的左边还是右边?如果是真的，它不可能在里面。如果为假，则至少在满足条件的“视锥”内。既然我们知道三角形中的一个点必须与BC(和CA)在AB的同一边，我们就来检查它们是否不同。如果它们在里面，s不可能在里面，否则s一定在里面。

Some keywords in the calculations are line half-planes and the determinant (2x2 cross product). Perhaps a more pedagogical way is probably to think of it as a point being inside iff it's to the same side (left or right) to each of the lines AB, BC and CA. The above way seemed a better fit for some optimization however.

计算中的一些关键字是线半平面和行列式(2x2外积)。也许一种更有教育性的方法是把它看作是iff的一个点它在AB、BC和CA每一行的同一边(左或右)。

#5

C# version of the barycentric method posted by andreasdr and Perro Azul. Note that the area calculation can be avoided if s and t have opposite signs. I verified correct behavior with a pretty thorough unit test.

由andreasdr和Perro Azul发布的barycentric方法的c#版本。注意，如果s和t有相反的符号，可以避免计算面积。我用一个非常全面的单元测试来验证正确的行为。

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) * p.X + (p0.X - p2.X) * p.Y;    var t = p0.X * p1.Y - p0.Y * p1.X + (p0.Y - p1.Y) * p.X + (p1.X - p0.X) * p.Y;    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;}

_[edit]
^{accepted suggested modification by @Pierre; see comments}

[编辑]@Pierre建议修改;看到评论

#6

A simple way is to:

一个简单的方法是:

find the vectors connecting the point to each of the triangle's three vertices and sum the angles between those vectors. If the sum of the angles is 2*pi then the point is inside the triangle.

找出将点与三角形的三个顶点连接起来的向量，并将这些向量之间的夹角相加。如果角的和是2*，那么这个点在三角形内。

Two good sites that explain alternatives are:

有两个很好的网站可以解释替代方案:

blackpawn and wolfram

blackpawn和wolfram

#7

Java version of barycentric method:

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

The above code will work accurately with integers, assuming no overflows. It will also work with clockwise and anticlockwise triangles. It will not work with collinear triangles (but you can check for that by testing det==0).

上面的代码将在没有溢出的情况下准确地处理整数。它也适用于顺时针和逆时针三角形。它不会与共线三角形(但您可以通过测试det==0来检查)。

The barycentric version is fastest if you are going to test different points with the same triangle.

如果要用相同的三角形测试不同的点，那么重心版本是最快的。

The barycentric version is not symmetric in the 3 triangle points, so it is likely to be less consistent than Kornel Kisielewicz's edge half-plane version, because of floating point rounding errors.

在3个三角点上，以重心为中心的版本是不对称的，因此，由于浮点数舍入误差，它可能不像Kornel Kisielewicz的边缘半平面版本那样一致。

Credit: I made the above code from Wikipedia's article on barycentric coordinates.

我在*关于重心坐标的文章中编写了上述代码。

#8

By using the analytic solution to the barycentric coordinates (pointed out by Andreas Brinck) and:

利用解析解的重心坐标(由Andreas Brinck指出)和:

• not distributing the multiplication over the parenthesized terms
• 不将乘法分布在括号内的项上
• avoiding computing several times the same terms by storing them
• 通过存储这些术语，可以避免多次使用相同的术语
• reducing comparisons (as pointed out by coproc and Thomas Eding)
• 减少比较(如coproc和Thomas Eding所指出)

one can minimize the number of "costy" operations:

可以将“costy”操作的数量最小化:

function ptInTriangle(p, p0, p1, p2) {    var dX = p.x-p2.x;    var dY = p.y-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;}

(code can be pasted in Perro Azul jsfiddle)

(代码可以粘贴在Perro Azul jsfiddle)

Leading to:

导致:

• variable "recalls": 30
• 变量的“回忆说”:30
• variable storage: 7
• 变量存储:7
• additions: 4
• 补充:4
• substractions: 8
• 减法:8
• multiplications: 6
• 乘法:6
• divisions: none
• 部门:没有
• comparisons: 4
• 比较:4

This compares quite well with Kornel Kisielewicz solution (25 recalls, 1 storage, 15 substractions, 6 multiplications, 5 comparisons), and might be even better if clockwise/counter-clockwise detection is needed (which takes 6 recalls, 1 addition, 2 substractions, 2 multiplications and 1 comparison in itself, using the analytic solution determinant, as pointed out by rhgb).

这种比较很好与Kornel Kisielewicz解决方案(25回忆说,1存储、15减法6乘法,5的比较),甚至可能是更好的如果需要顺时针/逆时针检测(以6回忆说,1,2减法,2次乘法和1比较,使用解析解行列式,rhgb所指出的)。

#9

What I do is precalculate the three face normals,

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

• in 3D by cross product of side vector and the face normal vector.

  在三维中，通过边向量与面法向量的外积。

• in 2D by simply swapping components and negating one,

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

then inside/outside for any one side is when a dot product of the side normal and the vertex to point vector, change sign. Repeat for other two (or more) sides.

然后在任何一边的内/外是当边的点积和顶点对点的向量，改变符号。重复其他两个(或更多)面。

Benefits:

好处:

• a lot is precalculated so great for multiple point testing on same triangle.

  对于同一个三角形上的多个点测试来说，很多都是预先计算好的。

• early rejection of common case of more outside than inside points. (also if point distribution weighted to one side, can test that side first.)

  早期拒绝常见的情况多于内部的点。(如果把点分布加权到一边，可以先测试那一边。)

#10

Here is an efficient Python implementation:

这是一种有效的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-s-t>0))

and an example output:

和一个示例输出:

#11

If you are looking for speed, here is a procedure that might help you.

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

Sort the triangle vertices on their ordinates. This takes at worst three comparisons. Let Y0, Y1, Y2 be the three sorted values. By drawing three horizontals through them you partition the plane into two half planes and two slabs. Let Y be the ordinate of the query point.

对它们的坐标上的三角形顶点进行排序。这是最坏的三种比较。y y y y y是三个排序后的值。通过画三个水平面，你把平面分成两个半平面和两个平板。设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 slabelse    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

Costs two more comparisons. As you see, quick rejection is achieved for points outside of the "bounding slab".

两个比较成本。正如您所看到的，对于“边界板”之外的点可以实现快速拒绝。

Optionally, you can supply a test on the abscissas for quick rejection on the left and on the right (X <= X0' or X >= X2'). This will implement a quick bounding box test at the same time, but you'll need to sort on the abscissas too.

可选地，您可以在横坐标上提供一个测试，以便在左边和右边快速拒绝(X <= X0'或X >= X2')。这将同时实现一个快速的边界框测试，但是您也需要对横坐标进行排序。

Eventually you will need to compute the sign of the given point with respect to the two sides of the triangle that delimit the relevant slab (upper or lower). The test has the form:

最后，你需要计算给定的点的符号，在三角形的两边，将相关的板(上或下)分隔开。测试形式为:

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

The complete discussion of i, j, k combinations (there are six of them, based on the outcome of the sort) is out of the scope of this answer and "left as an exercise to the reader"; for efficiency, they should be hard-coded.

关于i、j、k组合的完整讨论(根据这类结果有六种组合)超出了这个答案的范围，“留给读者作为练习”;为了提高效率，它们应该被硬编码。

If you think that this solution is complex, observe that it mainly involves simple comparisons (some of which can be precomputed), plus 6 subtractions and 4 multiplies in case the bounding box test fails. The latter cost is hard to beat as in the worst case you cannot avoid comparing the test point against two sides (no method in other answers has a lower cost, some make it worse, like 15 subtractions and 6 multiplies, sometimes divisions).

如果您认为这个解决方案很复杂，那么请注意，它主要涉及简单的比较(其中一些可以预先计算)，加上6个减法和4个相乘，以防边界框测试失败。后者的成本很难被打败，因为在最坏的情况下，你无法避免将测试点与两边进行比较(在其他答案中，没有一种方法的成本更低，有些方法更糟，比如15减去6乘以，有时是除法)。

UPDATE:Faster with a shear transform

更新:通过剪切变换速度更快

As explained just above, you can quickly locate the point inside one of the four horizontal bands delimited by the three vertex ordinates, using two comparisons.

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

You can optionally perform one or two extra X tests to check insideness to the bounding box (dotted lines).

您可以选择执行一个或两个额外的X测试来检查边界框的内部情况(虚线)。

Then consider the "shear" transform given by X'= X - m Y, Y' = Y, where m is the slope DX/DY for the highest edge. This transform will make this side of the triangle vertical. And since you know on what side of the middle horizontal you are, it suffices to test the sign with respect to a single side of the triangle.

然后考虑X'= X - m Y, Y' = Y的“剪切”变换，其中m为最前沿的斜率DX/DY。这个变换将使三角形的这条边垂直。既然你知道在水平中间的哪一边，它就足以对三角形的单侧进行符号测试了。

Assuming you precomputed the slope m, as well as the X' for the sheared triangle vertices and the coefficients of the equations of the sides as X = m Y + p, you will need in the worst case

假设你预先计算了斜率m，以及剪切三角形顶点的X'以及等式两边的系数X = m Y + p，在最坏的情况下你将需要

• two ordinate comparisons for vertical classification;
• 垂直分类的两个纵坐标比较;
• optionally one or two abscissa comparisons for bounding box rejection;
• 可选的一个或两个横坐标比较的包围盒拒绝;
• computation of X' = X - m Y;
• X' = X - m Y的计算;
• one or two comparisons with the abscissas of the sheared triangle;
• 与剪切三角形的剪刀进行一或两个比较;
• one sign test X >< m' Y + p' against the relevant side of the sheared triangle.
• 一个符号测试X >< m' Y + p'针对剪切三角形的相关边。

#12

If you know the co-ordinates of the three vertices and the co-ordinates of the specific point, then you can get the area of the complete triangle. Afterwards, calculate the area of the three triangle segments (one point being the point given and the other two being any two vertices of the triangle). Thus, you will get the area of the three triangle segments. If the sum of these areas are equal to the total area (that you got previously), then, the point should be inside the triangle. Otherwise, the point is not inside the triangle. This should work. If there are any issues, let me know. Thank you.

如果你知道三个顶点的坐标和特定点的坐标，那么你就可以得到整个三角形的面积。然后，计算三个三角形部分的面积(一个点表示给定的点，另两个点表示三角形的任意两个顶点)。因此，你会得到三个三角形部分的面积。如果这些面积的和等于总面积(你之前得到的)，那么这个点应该在三角形内。否则，点不在三角形内。这应该工作。如果有什么问题，请告诉我。谢谢你。

#13

Other function in python, faster than Developer's method (for me at least) and inspired by Cédric Dufour solution:

python中的其他函数，比开发人员的方法(至少对我来说)要快，并且受到Cedric Dufour解决方案的启发:

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  )

You can test it with:

你可以用:

X_size = 64Y_size = 64ax_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')

It takes a lot to plot, but that grid is tested in 0.0195319652557 seconds against 0.0844349861145 seconds of Developer's code.

绘图需要花费很多时间，但是这个网格的测试时间是0.0195319652557秒，而开发人员代码的测试时间是0.0844349861145秒。

Finally the code comment:

最后,代码注释:

# 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

#14

There are pesky edge conditions where a point is exactly on the common edge of two adjacent triangles. The point cannot be in both, or neither of the triangles. You need an arbitrary but consistent way of assigning the point. For example, draw a horizontal line through the point. If the line intersects with the other side of the triangle on the right, the point is treated as though it is inside the triangle. If the intersection is on the left, the point is outside.

有一些令人讨厌的边缘条件，其中一个点恰好在两个相邻三角形的共边上。点不能同时在两个三角形中，也不能同时在两个三角形中。您需要一种任意但一致的方式来分配点。例如，在这个点上画一条水平线。如果这条线与右边三角形的另一边相交，这个点就被当作它在三角形里面。如果交点在左边，点在外面。

If the line on which the point lies is horizontal, use above/below.

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

If the point is on the common vertex of multiple triangles, use the triangle with whose center the point forms the smallest angle.

如果点在多个三角形的公共顶点上，则使用以该点为中心的三角形形成最小的角。

More fun: three points can be in a straight line (zero degrees), for example (0,0) - (0,10) - (0,5). In a triangulating algorithm, the "ear" (0,10) must be lopped off, the "triangle" generated being the degenerate case of a straight line.

更有趣的是:三个点可以在一条直线上(0,0)-(0,10)-(0,5)。在三角剖分算法中，必须将“ear”(0,10)砍掉，生成的“三角形”是直线的简并情况。

#15

I just want to use some simple vector math to explain the barycentric coordinates solution which Andreas had given, it will be way easier to understand.

我只是想用一些简单的向量数学来解释Andreas给出的重心坐标解，它会更容易理解。

1. Area A is defined as any vector given by s * v02 + t * v01, with condition s >= 0 and t >= 0. If any point inside the triangle v0, v1, v2, it must be inside Area A.
2. 面积A定义为s * v02 + t * v01给出的任意向量，条件为s >= 0, t >= 0。如果三角形v0, v1, v2中的任意一点，它一定在A区域内。

2. If further restrict s, and t belongs to [0, 1]. We get Area B which contains all vectors of s * v02 + t * v01, with condition s, t belongs to [0, 1]. It is worth to note that the low part of the Area B is the mirror of Triangle v0, v1, v2. The problem comes to if we can give certain condition of s, and t, to further excluding the low part of Area B.
3. 如果进一步限制s, t属于[0,1]。我们得到面积B它包含所有的向量s * v02 + t * v01，条件是s t属于[0,1]值得注意的是面积B的低端是三角形v0 v1 v2的镜像。问题来了，如果我们能给出s和t的一定条件，进一步排除面积B的低部分。

3. Assume we give a value s, and t is changing in [0, 1]. In the following pic, point p is on the edge of v1v2. All the vectors of s * v02 + t * v01 which are along the dash line by simple vector sum. At v1v2 and dash line cross point p, we have:
4. 假设我们给出一个值s, t在[0,1]中变化。在下面的图中，点p在v1v2的边缘。所有s * v02 + t * v01的向量沿着虚线通过简单的向量和。在v1v2和虚线交点p处，我们有:

(1-s)|v0v2| / |v0v2| = tp|v0v1| / |v0v1|

(1-s)|v0v2| / |v0v2| = tp|v0v1| / |v0v1|。

we get 1 - s = tp, then 1 = s + tp. If any t > tp, which 1 < s + t where is on the double dash line, the vector is outside the triangle, any t <= tp, which 1 >= s + t where is on single dash line, the vector is inside the triangle.

我们得到1 - s = tp，然后1 = s + tp。如果任意t > tp, 1 < s + t在双虚线上，向量在三角形外，任意t <= tp, 1 >= s + t在单虚线上，向量在三角形内。

Then if we given any s in [0, 1], the corresponding t must meet 1 >= s + t, for the vector inside triangle.

如果我们在[0,1]中给出任何s，对应的t必须满足1 >= s + t，对于三角形中的向量。

So finally we get v = s * v02 + t * v01, v is inside triangle with condition s, t, s+t belongs to [0, 1]. Then translate to point, we have

最后得到v = s * v02 +t * v01, v是在三角形内的条件s t s+t属于[0,1]。然后转换到点，我们有

p - p0 = s * (p1 - p0) + t * (p2 - p0), with s, t, s + t in [0, 1]

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

which is the same as Andreas' solution to solve equation systemp = p0 + s * (p1 - p0) + t * (p2 - p0), with s, t, s + t belong to [0, 1].

这与Andreas的解方程systemp = p0 + s * (p1 - p0) + t * (p2 - p0)相同，其中s、t、s + t属于[0,1]。

#16

I needed point in triangle check in "controlable environment" when you're absolutely sure that triangles will be clockwise. So, I took Perro Azul's jsfiddle and modified it as suggested by coproc for such cases; also removed redundant 0.5 and 2 multiplications because they're just cancel each other.

当你确定三角形是顺时针的时候，我需要在“可控制的环境”中进行三角检查。所以我拿了Perro Azul的jsfiddle，按照coproc的建议进行修改;也去掉了多余的0。5和2乘因为它们互相抵消了。

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

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

Here is equivalent C# code for 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) * p.x + (p0.x - p2.x) * p.y);    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);    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;}

#17

Supposedly high-performance code which I adapted in JavaScript(article below):

我在JavaScript中修改的所谓高性能代码(文章如下):

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

pointInTriangle (p, p0, p1, p2) - for counter-clockwise triangles

尖三角形(p, p0, p1, p2)——用于逆时针三角形

pointInTriangle (p, p0, p1, p2) - for clockwise triangles

尖三角形(p, p0, p1, p2) -对于顺时针三角形

Look in jsFiddle (performance test included), there's also winding checking in a separate functionhttp://jsfiddle.net/z7x0udf7/3/

看看jsFiddle(包括性能测试)，还有一个单独的functionhttp://jsfiddle.net/z7x0udf7/3/

Inspired by this:http://www.phatcode.net/articles.php?id=459

灵感来自于:http://www.phatcode.net/articles.php?id=459

#18

The easiest way and it works with all types of triangles is simply determine the angles of the P point A, B , C points angles. If any of the angles are bigger than 180.0 degree then it is outside, if 180.0 then it is on the circumference and if acos cheating on you and less than 180.0 then it is inside.Take a look for understanding http://math-physics-psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

对于所有类型的三角形来说，最简单的方法就是确定P点A B C点的角度。如果任何一个角大于180度，那么它在外面，如果是180度，那么它在圆周上如果acos欺骗你，小于180度，那么它在里面。去了解一下http://math- physical - psychologology.blogspot.hu/2015/01/earlish -that at-point is.html

#19

Honestly it is as simple as Simon P Steven's answer however with that approach you don't have a solid control on whether you want the points on the edges of the triangle to be included or not.

老实说，这很简单，就像西蒙·P·史蒂文的答案一样，但是用这种方法你不能确定你是否想要包含三角形边缘上的点。

My approach is a little different but very basic. Consider the following triangle;

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

In order to have the point in the triangle we have to satisfy 3 conditions

为了得到三角形中的点我们必须满足三个条件

1. ACE angle (green) should be smaller than ACB angle (red)
2. ACE角(绿色)小于ACB角(红色)
3. ECB angle (blue) should be smaller than ACB angle (red)
4. ECB角(蓝色)应小于ACB角(红色)
5. Point E and Point C shoud have the same sign when their x and y values are applied to the equation of the |AB| line.
6. 点E和C点应该有相同的标志当他们的x和y值应用于AB | |线的方程。

In this method you have full control to include or exclude the point on the edges individually. So you may check if a point is in the triangle including only the |AC| edge for instance.

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

So my solution in JavaScript would be as follows;

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

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

It can not be more efficient than this! Each side of a triangle can have independent position and orientation, hence three calculations: l1, l2 and l3 are definitely needed involving 2 multiplications each. Once l1, l2 and l3 are known, result is just a few basic comparisons and boolean operations away.

没有比这更有效的了!三角形的每边都可以有独立的位置和方向，因此需要进行三次计算:l1、l2和l3，每一次都需要做两次乘法。一旦已知l1、l2和l3，结果就只是一些基本的比较和布尔运算。

#21

Since there's no JS answer :

因为没有JS回答:

function triangleContains(ax, ay, bx, by, cx, cy, x, y) {    let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)    return  det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) > 0 &&            det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) > 0 &&            det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) > 0 }

I'm using here the same method as described above: a point is inside ABC if he is respectively on the "same" side of each line AB, BC, CA.

我在这里使用的方法和上面描述的一样:如果一个点分别在AB、BC、CA这条线的“同一”边，那么它就在ABC内部。

#22

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

almost perfect Cartesian coordinates converted from barycentricare exported within *v (x) and *w (y) doubles.Both export doubles should have a * char before in every case, likely: *v and *wCode can be used for the other triangle of a quadrangle too. Hereby signed wrote only triangle abc from the clockwise abcd quad.

在*v (x)和*w (y)两倍的范围内，几乎完美的笛卡尔坐标转换。两个导出双精度浮点数在任何情况下都应该有一个* char，很可能:*v和*wCode也可以用于一个四边形的另一个三角形。特此签名，只从顺时针abcd四轴写了三角形abc。

A---B|..\\.o|  |....\\.| D---C 

the o point is inside ABC trianglefor testing with with second triangle call this function CDA direction, and results should be correct after *v=1-*v; and *w=1-*w; for the quadrangle

o点在ABC三角内部，用第二个三角形进行测试，称为函数CDA方向，在*v=1-*v后，结果应该是正确的;* w = 1 - * w;的四边形