1

我正在编写 Quick Hull 算法，其中包括检查一个点是否位于三角形内。为此，我创建了以下两个函数，如果点在内部，则返回 true，否则返回 false。

但是，从某种意义上说，结果是出乎意料的，有些点被正确分类，有些则没有，我无法弄清楚问题所在。有人可以帮我验证我写的代码是否正确。方法是我使用向量来确定一个点是否与三角形每条边的顶点位于同一侧。代码是：

public boolean ptInside(Point first, Point last, Point mx, Point cur) {
        boolean b1 = pointInside(first, last, mx, cur);
        boolean b2 = pointInside(last, mx, first, cur);
        boolean b3 = pointInside(first, mx, last, cur);
        return b1 && b2 && b3;

    }

    public boolean pointInside(Point first, Point last, Point mx, Point cur) {
        int x1 = last.xCo - first.xCo;
        int y1 = last.yCo - first.yCo;
        int x2 = mx.xCo - first.xCo;
        int y2 = mx.yCo - first.yCo;
        int x3 = cur.xCo - first.xCo;
        int y3 = cur.yCo - first.yCo;
        int cross1 = x1 * y2 - x2 * y1;
        int cross2 = x1 * y3 - x3 * y1;
        if (cross1 * cross2 > 0)
            return true;
        else
            return false;

    }
4

2 回答 2

6

我会简单地创建一个多边形，并使用它的contains(Point)方法。为什么要重新发明轮子？

于 2012-09-25T12:44:25.907 回答
1

您计算 b3 的点数排序不正确。您需要保持 (first, last, mx) 的循环顺序。否则，您已经颠倒了计算的意义。

于 2012-09-25T16:26:48.200 回答