点在三角形中的测试

同侧技术

检查点是否在三角形中的一种常见方法是，找到将点连接到三角形三个顶点中每个顶点的向量，并求出这些向量之间的角度之和。如果角度之和为2*pi，则该点位于三角形内，否则不在三角形内。它起作用，但速度很慢。这篇文章解释了一个更快更简单的方法。

首先，原谅那些讨厌的颜色。我真的很抱歉。诚实。

好的，ABC形成一个三角形，里面所有的点都是黄色的。AB线、BC线和CA线各将空间分成两半，其中一个两半完全位于三角形之外。这就是我们要利用的。

要使某一点位于A B C三角形内，它必须位于AB下方、BC左侧和AC右侧。如果其中任何一项测试失败，我们可以提前返回。

但是，我们如何判断一个点是否在一条直线的正确一侧？很高兴你这么问。

如果取[B-A]和[p-A]的叉积，就会得到一个指向屏幕外的向量。另一方面，如果取[B-A]和[p'-A]的叉积，就会得到一个指向屏幕的向量。啊哈！事实上，如果从A到A B线上方的任何点，将向量与[B-A]交叉，得到的向量将指向屏幕之外，而使用AB线下方的任何点，将得到指向屏幕的向量。所以，我们要做的就是用叉积来区分一条直线的哪一边是一个点。

剩下的唯一问题是：我们如何知道叉积的结果应该指向哪个方向？因为三角形可以在三维空间中以任何方式定向，所以没有一个可以比较的设定值。相反，我们需要的是一个参考点——一个我们知道的位于直线某一侧的点。对于我们的三角形，这只是第三个点C。

 

因此，[B-A]与[p-A]不在同一方向的任何点p，与[B-A]与[C-A]不在三角形内。如果叉积确实指向同一个方向，那么我们也需要用其他线来测试p。如果点在AB和C的同一侧，也在BC和A的同一侧，在CA和B的同一侧，则它在三角形中。

 

实现这一点很容易。我们将生成一个函数，告诉我们两个点是否在一条直线的同一侧，并让三角形函数中的实际点为每条边调用这个函数。

function SameSide(p1,p2, a,b)
    cp1 = CrossProduct(b-a, p1-a)
    cp2 = CrossProduct(b-a, p2-a)
    if DotProduct(cp1, cp2) >= 0 then return true
    else return false

function PointInTriangle(p, a,b,c)
    if SameSide(p,a, b,c) and SameSide(p,b, a,c)
        and SameSide(p,c, a,b) then return true
    else return false

它简单，有效，没有平方根，弧余弦，或奇怪的投影轴确定的污秽。

 

重心技术

上述方法的优点是理解起来非常简单，因此一旦你读了它，你就应该能够永远记住它，并在任何时候对它进行编码，而不必再引用任何东西。只是-嘿，这个点必须和不在这条线上的三角形点在同一条线上。

好吧，还有一个方法在概念上同样简单，但执行速度更快。缺点是涉及到更多的数学知识，但一旦你看到它解决了，就应该没问题了。

记住三角形的三个点定义了空间中的一个平面。选择其中一个点，我们可以将平面上的所有其他位置视为相对于该点。我们用A——它将是我们在平面上的原点。现在我们需要的是基向量，这样我们就可以给出平面上所有位置的坐标值。我们将选取三角形的两条边，它们分别与A，（C-A）和（B-A）相接触。现在我们只要从A开始沿着C-A走一段距离，然后再沿着B-A方向走一段距离，就可以到达平面上的任何一点。

考虑到这一点，我们现在可以把平面上的任何一点描述为

  P = A + u * (C - A) + v * (B - A)

注意，如果u或v<0，那么我们走错了方向，一定在三角形之外。另外，如果u或v>1，那么我们在一个方向上走得太远，并且在三角形之外。最后，如果u+v>1，那么我们再次越过BC边，离开三角形。

给定u和v，我们可以用上面的方程很容易地计算出P点，但是我们怎样才能逆着方向，从给定的P点计算出u和v点呢？该学数学了！

   P = A + u * (C - A) + v * (B - A)       // Original equation
    (P - A) = u * (C - A) + v * (B - A)     // Subtract A from both sides
    v2 = u * v0 + v * v1                    // Substitute v0, v1, v2 for less writing
    
    // We have two unknowns (u and v) so we need two equations to solve
    // for them.  Dot both sides by v0 to get one and dot both sides by
    // v1 to get a second.
    (v2) . v0 = (u * v0 + v * v1) . v0
    (v2) . v1 = (u * v0 + v * v1) . v1

    // Distribute v0 and v1
    v2 . v0 = u * (v0 . v0) + v * (v1 . v0)
    v2 . v1 = u * (v0 . v1) + v * (v1 . v1)

    // Now we have two equations and two unknowns and can solve one 
    // equation for one variable and substitute into the other.  Or
    // if you're lazy like me, fire up Mathematica and save yourself
    // some handwriting.
    Solve[v2.v0 == {u(v0.v0) + v(v1.v0), v2.v1 == u(v0.v1) + v(v1.v1)}, {u, v}]
    u = ((v1.v1)(v2.v0)-(v1.v0)(v2.v1)) / ((v0.v0)(v1.v1) - (v0.v1)(v1.v0))
    v = ((v0.v0)(v2.v1)-(v0.v1)(v2.v0)) / ((v0.v0)(v1.v1) - (v0.v1)(v1.v0))

// Compute vectors        
v0 = C - A
v1 = B - A
v2 = P - A

// Compute dot products
dot00 = dot(v0, v0)
dot01 = dot(v0, v1)
dot02 = dot(v0, v2)
dot11 = dot(v1, v1)
dot12 = dot(v1, v2)

// Compute barycentric coordinates
invDenom = 1 / (dot00 * dot11 - dot01 * dot01)
u = (dot11 * dot02 - dot01 * dot12) * invDenom
v = (dot00 * dot12 - dot01 * dot02) * invDenom

// Check if point is in triangle
return (u >= 0) && (v >= 0) && (u + v < 1)

本文概述的算法遵循实时碰撞检测中描述的技术之一。你也可以在*和MathWorld上找到更多关于重心坐标的信息。