如何判断多边形顶点的顺序是顺时针还是逆时针？

Question

具体问题是：

n lines, each line containing two integers. The i-th line contains xi, yi — the i-th vertex of the polygon in clockwise or counterclockwise order. Note that it is possible that more than two vertices appear in a side, such as the follow picture:

Now you need to judge that the vertices's order of polygon is clockwise or counterclockwise?

c++代码为：

struct Node
{
    int x, y;

    Node operator-(Node node) const
    {
        Node t;
        t.x = x - node.x;
        t.y = y - node.y;
        return t;
    }

    int operator*(Node node) const // I konow this is Cross-Product
    {
        return x * node.y - y * node.x;
    }
}node[1000];

 for (int i = 0; i < n; i++)
     scanf("%d %d", &node[i].x, &node[i].y);

 int tmp = 0;

 node[n].x = node[0].x, node[n].y = node[0].y;

 for (int i = 0; i < n; i++)
     tmp += (node[i] * node[i + 1]);

 if (tmp > 0)
        it is counterclockwise order;

但是我看不懂代码，谁能证明一下？

Answer 1

shoelace formula 将给出任何多边形的方向面积。因此，通过检查其符号，您可以确定方向。您的代码确实计算了两倍的面积，但由于符号是最重要的，所以这无关紧要。

如何判断多边形顶点的顺序是顺时针还是逆时针？

How to judge that the vertices's order of polygon is clockwise or counterclockwise?

c++

algorithm

math

computational-geometry