c++ - Sort Anticlockwise the points of rectilinear polygon

Question

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.

Answer 1

Consider the following polygon:

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

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.

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

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.