43

假设我们有一个平面，上面有一些点。我们还有一个给定半径的圆。

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

这是一个示例图片：
例子

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

输出：
  float cx和float cy- 圆心坐标

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

C++ 代码是首选，但不是强制性的。

4

10 回答 10

23

按照建议，编辑为更好的措辞：

基本观察：

  • 我假设半径是一，因为它不会改变任何东西。
  • 给定任意两点，它们所在的单位圆至多存在两个。
  • 给定一个解决问题的圆，您可以移动它，直到它包含集合中的两个点，同时保持集合中相同数量的点。

那么算法是：

  • 对于每对点，如果它们的距离 < 2，则计算通过它们的两个单位圆 C1 和 C2。
  • 计算你的集合在 C1 和 C2 内的点数
  • 取最大值。
于 2010-07-12T15:08:17.233 回答
8

这是文献中的“磁盘部分覆盖问题”——这应该给你一个开始谷歌搜索的好地方。这是一篇涵盖一种可能解决方案的论文，但在数学上有点密集： 磁盘部分覆盖问题的近似算法设计

事实上，这属于称为计算几何的领域，这很吸引人，但很难站稳脚跟。deBerg 对与该主题相关的各种算法进行了很好的概述。

于 2010-07-12T15:51:50.950 回答
4

如果您想要一些简单的东西，请随机取位置 (x,y)，计算圆内的点数并与之前的位置进行比较。取最大值。随时重复该操作。

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

于 2010-07-12T16:00:24.527 回答
4

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

快速逼近

使用局部敏感散列。基本上，将每个点散列到包含所有附近点的散列桶中。桶的设置使得冲突只发生在附近的点之间——与名称相似的哈希表不同，冲突在这里很有用。保持一个桶中碰撞次数的运行计数，然后使用该桶的中心作为你的圆的中心。

我承认这是对一个概念的快速解释，当你第一次听到它时，它并不是很明显。一个类比是问一群人他们的邮政编码是什么，并使用最常见的邮政编码来确定人口最多的圈子。它并不完美，但它是一种很好的快速启发式方法。

就点数而言，它基本上是线性时间，您可以即时更新数据集，以在每个点的恒定时间（相对于 n = 点数恒定）增量地获得新答案。

更多关于局部敏感散列的一般信息或关于我个人最喜欢的适用于这种情况的版本。

优于蛮力的确定性方法

这个想法是：对于每个点，将一个圆的边缘放在那个点上，然后扫一圈，看看哪个方向包含的点最多。对所有点执行此操作，我们会找到全局最大值。

围绕点 p 的扫描可以通过以下方式在 n log n 时间内完成：(b) 对区间进行排序，以便我们可以在线性时间内围绕 p 行进/扫描。

因此需要 O(n log n) 时间来找到接触固定点 p 的最佳圆，然后将其乘以 O(n) 以执行所有点的检查。总时间为 O(n^2 log n)。

于 2014-10-13T21:45:23.740 回答
2

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

您可以首先在与集合中的一个点对应的每个点中测试函数，通过减小f的值对这些点进行排序，然后围绕这些点加强搜索（例如沿着螺旋线移动）。

另一种选择是考虑连接集合中任何点对的线段的所有交点。我认为您的最佳点将在这些交叉点之一，但它们的数量可能太大而无法考虑。

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

无论如何，除非设定点的数量很少（允许您检查所有交叉点），否则我认为您不能保证找到最佳值（只是一个好的解决方案）。

于 2010-07-12T15:08:54.173 回答
1

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

此外，还有一种称为 K-means 的信息可视化/数据挖掘方法，它可以对给定数据进行聚类。它最终可以与附加功能一起使用，以满足您的目的。

K-Means 的基本算法是：

  1. 将 K 点放入由正在聚类的项目所代表的空间中 - 这些点代表初始组质心
  2. 将每个数据项分配给具有最近质心的组
  3. 分配完所有项目后，通过计算点的平均位置重新计算 K 质心的位置
  4. 重复步骤 2 和 3，直到质心不再移动，或移动很少

添加的功能将是：

  1. 计算位于 K 质心的圆圈内的点数
  2. 选择最适合您的；）

资料来源：
K-means 算法 -林雪平大学
四 叉树 - en.wikipedia.org/wiki/Quadtree

在维基百科上快速搜索，您会找到源代码：en.wikipedia.org/wiki/K-means_clustering

于 2010-07-12T15:34:41.227 回答
0

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

这是一种非常快速的算法，可以快速泛化大型数据集，但它并不总是准确的，为了提高准确性，您可以将 bin 切成越来越小的块，或者将 bin 位置向左或向右移动 n 次，并使用投票系统选择试验之间最常出现的答案。

于 2010-07-12T16:38:49.577 回答
0

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

Letf(x,y)是一个在点 (0,0) 处具有最大值且仅在半径为 R 的圆内的点处有效的函数。例如，f(x,y) = e^{(x^2 + y^2)/ (2 * R^2)}。

让(x_i,y_i)是 点 和E_i(x,y) = f(x - x_i, y - y_i)。

您的问题是找到 的最大值\sum_i E_i(x,y) 替代文字。

您可以使用从每个点开始的梯度下降。

于 2010-07-12T15:15:26.220 回答
0

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

当然，由于舍入误差，您可能会丢失一些好的区域或“幻觉”好的区域。也许您可以尝试先进行粗略的像素化，然后细化有希望的区域。

于 2010-07-12T18:24:41.923 回答
-4

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

于 2010-07-12T14:54:52.190 回答