找到一组点的中心并按顺时针顺序对它们进行排序？
我想按顺时针顺序对点向量进行排序以形成多边形，但我需要正确的中心才能做到这一点。我尝试过平均法，但有些点根本没有正确排序。以顺时针方式对点进行排序时，找到有效中心的正确方法是什么？
它在凹面部分失败了，
谢谢，
这是一张图片： 
绿色圆圈是中心。
它应该看起来更像这样： 
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:
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果没有预定义的中心点，“按顺时针顺序排序”的概念就没有明确定义。
如果你所拥有的只是一堆需要排序的点并且你事先不知道中心，那么问题通常没有单一的解决方案。该问题有许多替代解决方案，每个解决方案都会为您提供不同的多边形结果。
此外，找到一个允许您通过 CW（或 CCW）排序重新创建原始多边形的中心仅适用于特殊类别的多边形：所谓的 星形 多边形。星形多边形的主要属性是可以在多边形内部找到一个点，从该点可以“观察到”多边形的整个内部（我希望在没有定义的情况下清楚“可观察”的含义）。
如果您的多边形不是星形，那么这样的中心点根本不存在。并且，由于这个原因，不可能通过 CW 排序重新创建原始多边形。
图片中你的牛轮廓显然不是星形多边形，这意味着你永远无法通过对某个中心、任何中心周围的点进行排序来重新创建原始的牛轮廓。没有“正确的方法”。这是不可能的。
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:
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