排序逆时针直线多边形的点 [英] Sort Anticlockwise the points of rectilinear polygon

问题描述

我给直线多边形的坐标给出。
请建议我的溶液进行排序逆时针，以使得可以形成一个封闭的线

I am given a rectilinear polygon whose coordinates are given.
Please suggest to me a solution to sort anticlockwise, such that a closed line can be formed.

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);

}

不过，这是行不通的。照片 请提供一个解决方案。

But this is not working.
Please provide a solution.

推荐答案

考虑下面的多边形：

首先，y坐标命令你的顶点。在平等的y坐标排序顶点按组x坐标：

First, order your vertices by y-coordinate. In groups of equal y-coordinate sort the vertices by x-coordinate:

总是会有一个偶数各组顶点的，如果没有简并顶点。边将始终交替。因此，有2-3间0-1之间的边缘，1-2之间没有封边，不封边，不封边，不封边等。

There will always be an even number of vertices in each group if there are no degenerate vertices. Edges will always alternate. So there is an edge between 0-1, no edge between 1-2, edge between 2-3, no edge, edge etc.

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

Store the associated edges for each vertex. E.g. in a map or in an appropriate structure.

做同样的垂直边缘（由第一类X坐标，在组排序y坐标）。

Do the same for vertical edges (first sort by x-coordinate, in the groups sort by y-coordinate).

然后你有多边形的所有边。每个顶点现在应该有2相关的边缘。选择一个顶点并从边缘到边缘。这会给你的折线。如果您发现该行是顺时针方向，只是恢复的顺序，你会得到一个CCW折线。

Then you have all edges of the polygon. Each vertex should now have 2 associated edges. Pick one vertex and go from edge to edge. This will give you the polyline. If you find that the line is in clockwise direction, just revert the order and you'll get a ccw polyline.

这篇关于排序逆时针直线多边形的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！