6

我正在按照本文中的算法 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));
}

请澄清我的代码。谢谢你。

4

2 回答 2

1

文章对需要做的事情的描述中有一个“错误”：

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

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

true如文章中所述，如果所有三个点从原点（图片的左上角）在相同的“角度方向”上可见，则算法返回。您的图片也准确地显示了它：(0, p)所有粉红色点的矢量如果位于蓝色区域上方，则需要顺时针旋转才能到达三角形；如果它们低于蓝色区域，则矢量需要逆时针移动。

要修复算法，您需要计算向量{(V1-V2), (V1-P)}、{(V2-V3), (V2-P)}和的叉积{(V3-V1), (V3-P)}。看看这篇文章的伪代码。

于 2012-07-08T11:19:08.540 回答
1

我通常使用重心坐标进行这样的数学运算：（考虑 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加起来必须小于 1：

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

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

于 2012-07-08T11:37:44.160 回答