Finding center of a set of points to sort them clockwise?

I want to sort a vector of points in clockwise order to form a polygon but I need the proper center to do so. I have tried the averages method, but开发者_如何学编程 a few of the points did not sort correctly at all. What is the correct way to find the center that will work when sorting points in a clockwise manner?

It is failing on the concave parts

Thanks

Here is a picture:

The green circle is the center.

It should look more like this:

---

The notion of "sorting in clockwise order" is not well-defined if you don't have a pre-defined center point.

If all you have is just a bunch of points that you need to sort and you don't know the center in advance, then the problem does not generally have a single solution. The problem has many alternative solutions, each of which will give you a different polygon as the result.

Moreover, finding a center that would allow you to re-create the original polygon by CW (or CCW) sorting is only possible for a special class of polygons: so called star-shaped polygons. The main property of star-shaped polygon is that it is possible to find a point inside the polygon from which the entire interior of the polygon is "observable" (I hope it is clear without definition what "observable" means).

If your polygon is not star-shaped, then such center point simply does not exist. And, for this reason, it is not possible to re-create the original polygon by CW sorting.

Your cow contour in the picture is obviously not a star-shaped polygon, which means that you will never be able to re-create the original cow contour by sorting the points around some center, any center. There's no "correct way". It is not possible.

---

I think the most reliable strategy (aside from redesigning your program/system so this problem doesn't arise in the first place) is to minimize the total perimeter of the polygon.

This isn't an easy problem, but here is a heuristic that should work well:

1. For each point, find the next closest point. This defines a set of potential connections.
2. Add the longest potential connection to the polygon.
3. Repeat 1-2, but ignore connections that have already been made and points that already have two connections.

This is only a heuristic, not a solution. I'm not sure that it's even guaranteed to produce a polygon.

---

Taking any point as the center, you should be able to determine the distance and angle to all the points in the set, and sorting by angle is simple after that. However, the point that you choose as the center will influence the sort order, so it's hard to know what the "correct" order should be until you choose a point as the center.

So, if you chose the centroid as the center (seems like a good choice), but some points are sorted incorrectly relative to that point, then I'd say that there's a problem in your sorting code. Alternately, if you had an expectation about the sort order that wasn't met by your algorithm, then I'd say that one of your assumptions (sort order or center location) was incorrect.

---

Refer Barycenter. May be this is what u r looking for