java - 判断一个点相对于另一个点是顺时针还是逆时针的算法实际上是如何工作的？

Question

我正在致力于实现 Jarvis 算法(又名礼品包装)。为了确定点 p1 相对于点 p2 是顺时针还是逆时针，我使用以下公式:(y1-qY)(x2-qX) - (x1-qX)(y2-qY ) = n 其中 q 是两点所成角的顶点。如果 n < 0，则点 1 是点 2 的顺时针方向。如果 n > 0，则 point1 是 point2 的逆时针方向。

A) 如果 p1 = (1.5, 34.5)[黄点]，p2 = (1, 2.4)[红点]，且 q = (2.5, 2)[橙点]，则 n = (34.5 - 2)(1 - 2.5) - (1.5 - 2.5)(2.4 - 2) = -48.35

B) 如果 p1 = (6, 2.4)[blue dot] 并且其他一切都保持不变，那么 n6 = (2.4 - 2)(1 - 2.5) - (6 - 2.5)(2.4 - 2) = 大约 -2。

查看点图，蓝点比黄点(相对于红点)更顺时针，但公式表明黄点是最顺时针的点。

我误会了什么？

Answer 1

I am using this formula: (y1-qY)(x2-qX) - (x1-qX)(y2-qY) = n where q is the vertex of the angle formed by the two points. If n < 0, point1 is clockwise of point2. If n > 0, point1 is counter-clockwise of point2.

正确，叉积(=您的公式)的符号是角度的符号。

the formula is indicating that the yellow dot is the most clockwise point

为什么会这样想？不，叉积的大小不(直接)对应于角度的大小。

幸运的是，您不需要角度的大小来找到最顺时针的点，因为最顺时针的点是比其他任何点更顺时针的点:

List<Point> jarvis(List<Point> points) {
    List<Point> hull = new ArrayList<>();
    Point q = Collections.min(points, Comparator.comparing(p -> p.x));
    do {
        hull.add(q);

        Point leftMost = null;
        for (Point p : points) {
            if (p == q) continue;
            if (leftMost == null || left(p,q,leftMost)) {
                leftMost = p;
            }
        }

        q = leftMost;
    } while (q != hull.get(0));
    return null;
}