寻找点集中心以按顺时针排序？

Question

我想对一组点进行顺时针排序以形成一个多边形，但我需要正确的中心点来完成此操作。我尝试了平均值方法，但其中一些点根本没有正确排序。在按顺时针方式排序点时，找到适当的中心的正确方法是什么？

它在凹部分失败了。

谢谢。

这是一张图片： 绿色圆圈是中心。

它应该看起来更像这样：

- jmasterx

---

考虑到多边形只由其点定义且为非凸多边形，我不确定在没有进一步限制的情况下是否存在解法。目前尚不清楚该多边形是否具有唯一性定义。 - Keith

Answer 1

“按顺时针排序”这个概念如果没有预定义的中心点是不明确的。如果你只有一堆需要排序的点，而且事先不知道中心点，那么这个问题通常没有单一的解决方案。该问题有许多替代方案，每个方案都会给出一个不同的多边形作为结果。

此外，仅当多边形属于所谓的星形多边形时，才能找到一个中心点，使您可以通过CW（或CCW）排序重新创建原始多边形。星形多边形的主要特性是可以找到一个多边形内部的点，从该点可以“观察到”整个多边形的内部（我希望“可观察”是清晰的，无需定义）。

如果您的多边形不是星形的，则不存在这样的中心点。因此，通过CW排序无法重新创建原始多边形。

在图片中，您的牛轮廓显然不是一个星形多边形，这意味着您永远无法通过围绕某个中心点对点进行排序来重新创建原始牛轮廓。没有“正确的方法”。这是不可能的。

- AnT stands with Russia

---

那么，哪些算法可以让我得到原始的奶牛呢？ - jmasterx

@Milo：想象一个更简单的多边形，比如一个五角星。如果你抹掉线条，只看点，至少有两种可能的重建方法：一个星形或者两个同心五边形，每个五边形缺少一条边，由两条线连接。抹掉线条会丢失有价值的信息，问题无法可靠地解决。（巧合的是，正如Andrey所说，星星确实适合你已经尝试过的算法，但奶牛不是星星。） - Potatoswatter

@Milo：如果轮廓上的点非常密集地排列（特别是在弯曲部分），那么您可以通过从一个点跳到下一个最近的点来重新创建奶牛。然而，如果点不足够密集，则在某些地方可能会出现错误。在一般情况下，无法从无序点集中重新创建原始轮廓。正如我上面所说，有许多不同的轮廓可以从一组点构建。由于您无法确定哪个是正确的，因此无法重新创建它。 - AnT stands with Russia

图片2是使用一个叫做PhisicsEditor的程序创建的，他们是如何做到的？ - jmasterx

PhisicsEditor可以处理我提供的任何图片。无论如何，感谢您提供的信息 :) - jmasterx

Answer 2

我认为最可靠的策略（除了重新设计程序/系统以避免出现此问题）是尽量减少多边形的总周长。

这不是一个简单的问题，但以下启发式方法应该能够很好地解决：

1. 对于每个点，找到下一个最近的点。这定义了一组可能的连接。
2. 将最长的潜在连接添加到多边形中。
3. 重复1-2，但忽略已经建立的连接和已经有两个连接的点。

这只是一种启发式方法，而不是解决方案。我不确定它是否保证能够产生一个多边形。

- Potatoswatter

Answer 3

以任何一个点为中心，你应该能够确定集合中所有点的距离和角度，并在此之后按角度排序很简单。然而，你选择的中心点将影响排序顺序，因此在选择中心点之前很难知道“正确”的顺序应该是什么。

因此，如果你选择重心作为中心（看起来是个不错的选择），但有些点相对于该点被错误地排序，那么我会说你的排序代码存在问题。或者，如果你对排序顺序有某种期望，但算法没有满足，那么我会说你的假设（排序顺序或中心位置）之一是错误的。

- Caleb

---

请查看我的图片以更深入地了解问题。 - jmasterx

你的排序是正确的。问题在于，你无法通过按角度排序来产生奶牛。 - Caleb

那么，哪些算法可以做到这一点呢？现在我只是从图片本身获取轮廓顶点，但它们是按扫描线顺序排列的。 - jmasterx

看起来你有很多点，所以你可以从任意一个点开始，画一条线到最近的邻居。这不是完美的，但对于这头牛应该可以工作。 - Caleb

Answer 4

请参考重心。也许这就是您正在寻找的内容。

- Shadow