center - 点簇的中心和轨迹形状

Question

我有一些看起来像这样的点图。

这些点形成的轨迹可以是圆形或椭圆形。显然，上面两张图片中圆形轨道的中心是不同的。

如何找到这些轨道的中心点（圆形/椭圆形）？我想找到作为中心的 (x,y) 坐标，它不必是绘制数据集中的一个点。即，我不想要一个medoid。

编辑：另外，我是否可以找到一个包含大部分这些点的圆/椭圆方程？在椭圆轨道中，我添加了一个椭圆来包围轨道上的点。这些值是通过反复试验计算的。中心也是通过观察该图来计算的。如何以编程方式执行此操作？

Answer 1

最小圆问题，这里有一篇关于最小椭圆问题的论文（提供 PDF 下载）。两者都有 O(N) 算法，并且应该能够提供可以从中获得中心的圆和区域的公式。然而，他们专注于封闭所有的点。要解决该问题，您需要删除一些边界点，您也应该从算法中获得这些边界点。不幸的是，什么是足够好的解决方案取决于您。

一个快速简单的随机解决方案是：

1. 将一组点随机分成 k 组，每组 N/k 个点。
2. 为每组运行最小圆/椭圆算法
3. 对于 k 个集合中的每一个，选择至少 1 个但不再有 m 个边界点从主要点集中移除。
4. 返回步骤 1，t 次。
5. 返回剩余点的圆/椭圆算法的结果。

该算法每次通过都以 O(N) 为代价移除 k 和 mk 个边界点。出于您的目的，您可能希望删除一定百分比的边界点，1-25% 似乎是一个很好的起点。此解决方案假定 k 与 N 相比非常小，否则您将删除太多点。

如果您想重复从最小椭圆中删除一个或全部边界点，重新计算最小椭圆，然后再次删除边界点，则较慢但可能更好的算法很有用。

您可以通过让父节点成为其子节点的最小封闭椭圆的边界点（存储为一组以便于更快移除的点）来实现这一点。边界点的最大数量不应超过 k（我认为椭圆为 9，而圆形为 3）。因此，在 O(k log N) 处从数据结构中删除一个点，因为它需要重新计算最小的圆，对于每个受影响的父级 O(log N)，它是 O(k)。所以从数据结构中移除 m 个点应该是 O(mk log N)。您可能还需要考虑计算每个删除点的椭圆面积，并以 O(Nk log N) 的成本删除每个点，直到只剩下三个点。然后，您可以分析区域数据以确定应该使用什么椭圆。一个简单的结果是简单地使用面积最接近创建的所有椭圆的平均面积的椭圆，但可能并不完全符合您的要求。它也可能太慢，在这种情况下，我建议单次通过更快的算法。

Answer 2

这看起来像一个稳健椭圆拟合的实例。查看这篇论文：鲁棒椭圆和椭球拟合的异常值消除http://arxiv.org/pdf/0910.4610.pdf。

惯性椭圆（惯性椭圆的二维版本http://en.wikipedia.org/wiki/Moment_of_inertia#Inertia_ellipsoid）提供了第一个粗略而简单的解决方案。它的中心只是质心，轴由 2x2 惯性矩阵的特征向量/值给出。