algorithm - 如何选取一个半径内包含最多的散点？

Question

设置示例

在此处提出问题之前，我曾尝试到处寻找问题的解决方案。我的问题是我不太擅长数学或统计学，无法理解任何给定的算法都会对解决方案有所帮助。

在我的例子中，我有一个看起来像散点图的东西。只有一堆随机放置在笛卡尔坐标平面上的点。我希望能够在这个平面上绘制一个具有特定半径的圆。 圆圈必须包含尽可能多的点。

我应该采取什么步骤来计算绘制这个圆的最佳点？

我正在寻找...

我喜欢我必须采取的一组步骤，以便弄清楚我应该在图表上的哪个位置开始绘制(圆的中心点)。如果你有代码，我很擅长破译我不一定知道的语言，但我会用 Lua 编写这个(不幸的是我无法访问 C 部分)。

我真的很想了解该解决方案的工作原理，因此我将不胜感激任何来源或解释。仅供引用，性能极其重要，但此时我正在寻找任何解决方案。

奖金 :)

既然我正在写这篇文章，我想我不妨问问我希望我的代码执行的其他高级功能。但是当我真正踏入大门时，我总能在以后弄清楚这些。

• 离圆心较远的点比离圆心较近的点更接近全权重。权重可以简单地是一个线性函数，如果半径为 10，则距中心 1 仅占总权重的 10%，而距中心 2 仅占总权重的 20%。距离中心恰好 10 处将为您提供 100% 的权重。

• 引入了时间，圆心也是图上的一个点(这个点不属于其他点，不应该和它们一起计算)。圆心以恒定速度移动，您必须选择一个离圆心足够近的点，因为所有点的所有权重都会随时间衰减。所以画圆越快越好。 (这是高度理论化的，我不确定衰变会是什么样子)。

非常感谢您阅读本文并考虑我的问题!我可以提供更多详细信息或回答您可能遇到的任何问题。

Answer 1

有一种可能更快的方法可以找到需要更多数学知识的最佳圆，并延伸到两个精确点中的第一个。

取一个覆盖您感兴趣的区域的网格，并在您绘制点的网格中放置 1，在未绘制点的位置放置 0。您现在需要计算出网格中每个点的分数。您可以通过将网格中每个点的值乘以一个权重来做到这一点，该权重取决于该点与您评分的点的距离，然后对结果求和。这涵盖了您的基本问题(圆圈内点的权重为 1，否则为 0)和您的第一个高级点，其中权重变化更缓慢。

以这种方式看待问题，您有一个需要应用于网格的二维过滤器。应用后，您只需要在结果中找到最高分即可。以明显的方式执行此操作会非常慢，但事实证明，您可以使用快速傅里叶变换加快此类操作的速度，并且您可以获得数学库来计算它。

如果您没有在数学或统计方面进行过练习，那么您将需要对此进行很好的解释 - 恐怕比我能提供的更好。做了很多，但我还没有找到我真正喜欢的解释。你可以看看 http://www.analog.com/static/imported-files/tech_docs/dsp_book_Ch24.pdf ，这也在 http://archive.gamedev.net/archive/reference/programming/features/imageproc/page2.html 中被引用.