实现“检查点是否在三角形内”算法时出现了Bug

Question

我正在按照这篇文章中的算法1来检查点是否在三角形内。这是我的代码：

//========================================================================================================================//
// Methods
//========================================================================================================================//

private float getPerpDotProduct(final PointF p1, final PointF p2) {
    return p1.x * p2.y - p1.y * p2.x;
}

private boolean isInside(final PointF pPoint) { 
    final float c1 = this.getPerpDotProduct(this.mA, pPoint);
    final float c2 = this.getPerpDotProduct(this.mB, pPoint);
    final float c3 = this.getPerpDotProduct(this.mC, pPoint);

    return ((c1 >= 0 && c2 >= 0 & c3 >= 0) || (c1 <= 0 && c2 <= 0 && c3 <= 0));
}

这是我的测试：

青色区域：我给出的真实三角形。

粉色区域：三角形“内部”。

蓝色区域：三角形“外部”。

编辑：

这是我的新代码，用于向量计算：

private PointF getVector(final PointF pPoint1, final PointF pPoint2) {
    return new PointF(pPoint2.x - pPoint1.x, pPoint2.y - pPoint1.y);
}

private float getPerpDotProduct(final PointF p1, final PointF p2) {
    return p1.x * p2.y - p1.y * p2.x;
}

private boolean isInside(final PointF pPoint) { 
    final float c1 = this.getPerpDotProduct(getVector(this.mA, this.mB), getVector(this.mA, pPoint));
    final float c2 = this.getPerpDotProduct(getVector(this.mB, this.mC), getVector(this.mB, pPoint));
    final float c3 = this.getPerpDotProduct(getVector(this.mC, this.mA), getVector(this.mC, pPoint));

    return ((c1 > 0 && c2 > 0 & c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0));
}

请帮我澄清一下我的代码，谢谢。

- Luke Vo

---

尝试在你的返回语句中用文章中所做的方式将 >= 替换为 >，并将 <= 替换为 <。 - giorashc

Answer 1

文章中的描述有一个“错误”：

计算所有三个点V1、V2、V3与测试点P的perpDotProduct/crossproduct

应该是“计算所有三个向量与指向测试点P的向量的perpDotProduct/crossproduct”。

正如文章中所解释的那样，如果所有三个点从原点（图片左上角）处具有相同的“角度方向”，则算法将返回true。您的图片也很清楚地显示了这一点：对于所有粉色点，向量(0, p)需要顺时针旋转才能到达三角形，如果它们在蓝色区域上方；如果它们在蓝色区域下方，则向量需要逆时针移动。

要修复算法，您需要计算向量{(V1-V2), (V1-P)}、{(V2-V3), (V2-P)}和{(V3-V1), (V3-P)}的叉积。请参阅this article以获取伪代码。

- Sergey Kalinichenko

---

我根据你的建议修改了我的代码，但现在所有的点都被认为是三角形外部的。我做错了什么吗？我之前阅读了你提供的文章，但它很令人困惑。我不知道那篇文章中的CrossProduct和DotProduct函数返回或接受哪种类型。你能解释一下吗？ - Luke Vo

抱歉，我的代码中有一个拼写错误，现在它可以工作了。非常感谢 :) - Luke Vo

@W.N. 没问题！我在ideone上测试了一个实现，它可以工作。我猜你现在不需要它了，但是这里还是有的 :) - Sergey Kalinichenko

Answer 2

我通常使用重心坐标来进行计算，具体如下： （考虑4个点，其中p1、p2、p3是三角形的顶点，p4是您想要检查的点： 将(p1,p3)视为向量p1->p3）

dot00 = (p1,p3).(p1,p3)
dot01 = (p1,p3).(p1,p2)
dot02 = (p1,p3).(p1,p4)
dot11 = (p1,p2).(p1,p2)
dot12 = (p1,p2).(p1,p4)


inverseDenominator = (1 / (dot00*dot11 - dot01*dot01)

u = (dot11 * dot02 - dot01*dot12) * inverseDenominator
v = (dot00 * dot12 - dot01*dot02) * inverseDenominator

现在我们已经计算出重心坐标，验证就很简单了，如果P4位于三角形（P1，P2，P3）内，则u和v必须都为正数，并且它们加起来必须小于一：

u >= 0 && v >= 0 && u + v < 1 

这是我在写论文时学习如何做的文章：http://www.blackpawn.com/texts/pointinpoly/default.html（你会发现变量名称有相似之处 :p）

- fmsf

---

谢谢。我之前也读过这篇文章，但是因为没有接受过相关的教育，所以不知道它是如何工作的。不过我尝试了一下实现这个解决方案，结果成功了 :) 谢谢 :) - Luke Vo