c++ - 逆时针排序直线多边形的点

Question

我得到一个直线多边形，它的坐标是给定的。
请向我建议一个逆时针排序的解决方案，这样可以形成一条闭合线。

bool mycomparator(Point p1,Point p2){

    return ((p1.x*p2.y-p2.x*p1.y)>0);

}

void sort_anticlockwise(vector<Point> v){

    sort(v.begin(),v.end(),mycomparator);

}

但这不起作用。
请提供解决方案。

Answer 1

考虑以下多边形：

首先，按 y 坐标对顶点进行排序。在相等的 y 坐标组中，按 x 坐标对顶点进行排序：

如果没有退化顶点，则每组中的顶点数总是偶数。边缘将始终交替。所以0-1之间有边，1-2之间没有边，2-3之间有边，没有边，边等。

存储每个顶点的关联边。例如在地图或适当的结构中。

对垂直边缘执行相同的操作（首先按 x 坐标排序，在组中按 y 坐标排序）。

然后你就有了多边形的所有边。每个顶点现在应该有 2 个关联的边。选择一个顶点并从边到边。这将为您提供折线。如果你发现这条线是顺时针方向的，只需恢复顺序，你就会得到一条 ccw 折线。