以给定半径的一个圆覆盖最大点数的算法

让我们想象一下，我们有一架飞机上有一些点。我们还有一个给定半径的圆。

我需要一种算法来确定圆的位置，使其覆盖可能的最大点数。当然，有很多这样的位置，因此算法应返回其中之一。精度并不重要，该算法可能会犯一些小错误。

以下是示例图片： “示例”

输入：int n（n <= 50）–点数；float x[n]和float y[n] –具有点的X和Y坐标的数组；float r–圆的半径。

输出：float cx和float cy –圆心的坐标

该算法的闪电速度不是必需的，但不应太慢（因为我知道这种情况下的一些慢速解决方案）。

首选C ++代码，但不是必须的。

19
投票

根据建议编辑为更好的措辞：

基本观察：

然后是算法：

-4
投票

这是著名的K-最近点算法。在这里描述：http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf

6
投票

这是文献中的“磁盘部分覆盖问题”-应该为您提供了一个开始进行谷歌搜索的好地方。这是一篇介绍一个可能解决方案的论文，但是从数学上讲有点紧张：Approximation Algorithms Design for Disk Partial Covering Problem

事实上，这属于称为计算几何的领域，虽然很有趣，但是可能很难站稳脚跟。deBerg很好地概述了与该主题相关的各种算法。

5
投票

[如果您想要简单的东西，则取随机位置（x，y），计算圆内的点数，然后与先前的位置进行比较。以最大。随时重复操作。

为什么要投票？听说过蒙特卡洛方法吗？实际上，对于大量的点，确定性算法可能无法在合理的时间内完成。

2
投票

问题又回到寻找函数f :R x R -> N的global最优值。 f的输入是圆的中心点，其值当然是集合中包含点的数量。该函数的图形将是不连续的，类似于阶梯。

您可以通过在与集合中某个点相对应的每个点中测试功能，通过减小f的值来对这些点进行排序，然后加强对这些点的搜索（例如，沿着螺旋运动）。] >

另一种选择是考虑连接集合中任意对点的线段的all

交点。我认为您的optimal点将在这些交叉点之一，但它们的数量可能太大而无法考虑。

您还可以混合选项1和2，并考虑从“良好设定点”周围的点生成的线段的交点。

无论如何，除非设定点的数量少（允许您检查所有交叉点），否则我不会认为

您可以保证找到最佳值（只是一个好的解决方案）。

1
投票

乍一看，我想说一个四叉树解决方案。

1
投票

[这里有两个想法：O（n）近似算法和O（n ^ 2 log n）精确（非近似）算法：

0
投票

如果确实精度不重要，并且算法可能会犯一些小错误，那么我认为以下内容。

0
投票

我可以建议密度图吗？找到x和y的最小和最大范围。将x和y边界的范围划分为宽度等于圆直径的bin。分别计算x和y在每个bin中的点数。现在，在密度图上找到排名最高的x bin与排名最高的y bin之间的交集。

0
投票

您可以对整个区域进行像素化，然后转到每个点，并增加该点周围半径圆内所有像素的值。总和最高的像素是不错的选择。