二维空间中的点排序
假设随机点P1 到P20散布在平面上。 那么有什么方法可以按顺时针或逆时针对这些点进行排序。 
这里我们不能使用度数，因为你可以从图像中看到很多点可以具有相同的程度。 例如，这里P4、P5和P13获得相同的程度。
Suppose random points P1 to P20 scattered in a plane.
Then is there any way to sort those points in either clock-wise or anti-clock wise.
Here we can’t use degree because you can see from the image many points can have same degree.
E.g, here P4,P5 and P13 acquire the same degree.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果您的图片在点之间具有实际距离，您可能只需随机选择一个点（例如
P1），然后始终选择最近的未访问过的邻居作为下一个点即可。旅行推销员，有点像。If your picture has realistic distance between the points, you might get by with just choosing a point at random, say
P1, and then always picking the nearest unvisited neighbour as your next point. Traveling Salesman, kind of.你是说你想要一个有序的结果 P1, P2, ... P13 吗？
如果是这种情况，您需要找到点的凸包。沿着船体的圆周走一圈就会给出所需点的顺序。
从实际意义上讲，请查看 OpenCV 的文档 - - 使用
顺时针= true调用convexHull会给你一个按照你想要的顺序的点向量。该链接适用于 C++，但也有 C 和 Python API。其他软件包（如 Matlab）应该具有类似的功能，因为这是一个常见的需要解决的几何问题。编辑
一旦获得凸包，您可以迭代地从外部折叠它以获得剩余的点。当船体内不再有像素时，迭代就会停止。您必须设置折叠函数，以便首先包含较近的点，即您得到：
而不是：
在这两个图中，绿色是原始凸包，其他颜色是折叠区域。
Are you saying you want an ordered result P1, P2, ... P13?
If that's the case, you need to find the convex hull of the points. Walking around the circumference of the hull will then give you the order of the points that you need.
In a practical sense, have a look at OpenCV's documentation -- calling
convexHullwithclockwise=truegives you a vector of points in the order that you want. The link is for C++, but there are C and Python APIs there as well. Other packages like Matlab should have a similar function, as this is a common geometrical problem to solve.EDIT
Once you get your convex hull, you could iteratively collapse it from the outside to get the remaining points. Your iterations would stop when there are no more pixels left inside the hull. You would have to set up your collapse function such that closer points are included first, i.e. such that you get:
and not:
In both diagrams, green is the original convex hull, the other colors are collapsed areas.
找到这些点中最右边的点（
O(n)）并按相对于该点的角度排序 (O(nlog(n))）。这是格雷厄姆凸包算法的第一步，因此是一个非常常见的过程。
编辑：实际上，这是不可能的，因为点的多边形表示（即输出顺序）不明确。上面的算法仅适用于凸多边形，但它也可以扩展到星形多边形（您需要选择不同的“参考点”）。
您需要更准确地定义您实际想要的顺序。
Find the right-most of those points (in
O(n)) and sort by the angle relative to that point (O(nlog(n))).It's the first step of graham's convex-hull algorithm, so it's a very common procedure.
Edit: Actually, it's just not possible, since the polygonal representation (i.e. the output-order) of your points is ambiguous. The algorithm above will only work for convex polygons, but it can be extended to work for star-shaped polygons too (you need to pick a different "reference-point").
You need to define the order you actually want more precisely.