在二维空间分拣点的 [英] Sorting of Points in 2D space
问题描述
假设随机点的 P1到P20 散落在一个平面上。
那么有没有什么办法来这些点在任何顺时针或反顺时针排序。
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.
下面的我们不能使用度，因为你可以从图像中多点看可以有相同的程度。 例如，这里的 P4，P5和P13 获得相同的程度。
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.
推荐答案
你说你想要一个有序的结果P1，P2，P13 ...？
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.
在实际意义上说，看看OpenCV中的<一个href="http://opencv.willowgarage.com/documentation/cpp/imgproc_structural_analysis_and_shape_descriptors.html#cv-convexhull"相对=nofollow>文档 - 调用凸形轮廓与顺时针= TRUE 为您提供了一个载体在您希望的顺序分。链接是C ++，但也有C和Python的API的也有。其他包类似于Matlab应该具有相似的功能，因为这是一种常见的几何解决的问题。
In a practical sense, have a look at OpenCV's documentation -- calling convexHull with clockwise=true gives 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.
修改
一旦你得到你的凸包，你可以反复地从外面其折叠，以获得其余各点。当没有更多的像素留在船体内部的迭代将停止。你将不得不设置你崩溃的功能，从而更接近点包括第一，也就是这样，你得到：
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:
而不是
在这两个图中，绿色是原来的凸包，其他颜色都崩溃了的地方。
In both diagrams, green is the original convex hull, the other colors are collapsed areas.
这篇关于在二维空间分拣点的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
