二维空间中点的分类

假设随机点P1到P20分散在一个平面上。然后有什么办法来排序这些点在时钟明智或反时钟明智。 enter image description here 二维空间中点的分类

这里我们不能使用程度，因为你可以从图像中看到很多点可以拥有相同的程度。例如，这里P4，P5和P13获得相同的程度。

2011-02-01 Pritesh

你是说你想要一个有序的结果P1，P2，... P13？

如果是这样，您需要找到convex hull的点数。然后沿着船体的周围行走，然后给你你需要的点的顺序。

从实际意义上看，OpenCV的documentation - 调用convexHull与clockwise=true为您提供了所需顺序的点向量。链接用于C++，但也有C和Python API。像Matlab这样的其他软件包应该有类似的功能，因为这是一个常见的几何问题需要解决。

编辑

一旦你得到你的凸包，你可以反复地从外面折叠它以获得剩余点。当船体内没有剩余像素时，您的迭代将停止。你将不得不设置你的合拢功能，从而更接近点被首次列入，即，使得您可以：

enter image description here

，而不是：

enter image description here

在这两个图中，绿色是原始凸包，其他颜色都是折叠区域。

2011-02-01 10:55:11 misha

不，我只有20点，这是P1到P20和它的x和y值，它并没有按顺序意味着从P1到P20那些散落在飞机周围，我想要的是让这些点顺序从P1到P20或从P20到P1。谢谢.......... – Pritesh 2011-02-01 10:59:38

那么，为什么是凸包**不是**你想要什么？ – misha 2011-02-01 11:05:31

如果你的照片在点之间有实际的距离，你可能会随机选择一个点，比如P1，然后总是选择最近的未被访问的邻居作为你的下一个点。旅行推销员，那种。

2011-02-01 11:03:38

找到这些点中最右边的点（在O(n)）并按相对于该点的角度排序（O(nlog(n))）。

这是格雷厄姆凸包算法的第一步，所以这是一个非常普遍的过程。

编辑：实际上，这是不可能的，因为你的点的多边形表示（即输出顺序）是不明确的。上面的算法只适用于凸多边形，但它也可以扩展为用于星形多边形（您需要选择不同的“参考点”）。

您需要更准确地定义您实际需要的顺序。

2011-02-01 11:03:51 ltjax

回答