首页 文章

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

提问于
浏览 次
35

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

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

这是一个示例图片：

Example

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

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

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

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

c++ algorithm circle points

10 回答

  • 0

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

    基本观察：

    • 我假设半径为1，因为它不会改变任何东西 .

    • 给出任意两点，它们至多存在两个单位圆 .

    • 给出问题的解决方案圈，你可以移动它直到它包含你的集合中的两个点，同时保持你的集合中的相同点数 .

    然后算法是：

    • 对于每对点，如果它们的距离<2，则计算通过它们的两个单位圆C1和C2 .

    • 计算C1和C2内的集合点数

    • 拿最大值

    回复于
  • -4

    这是文献中的"disk partial covering problem" - 应该给你一个开始谷歌搜索的好地方 . 这是一篇涵盖一种可能解决方案的论文，但它在数学上有点激烈：http://www.utdallas.edu/~edsha/papers/bin/ISPAN04_cover.pdf

    事实上，这属于称为计算几何的领域，这很有吸引力，但很难获得立足点 . 德伯格对与该主题相关的各种算法有一个很好的概述 .

    回复于
  • 5

    如果你想要简单的东西，采取随机位置（x，y），计算圆内的点数并与之前的位置进行比较 . 取最大值 . 您可以随时重复操作 .

    为什么地狱投票？有没有听过蒙特卡罗的方法？实际上对于大量的点，确定性算法可能无法在合理的时间内完成 .

    回复于
  • 6

    问题又回到了找到函数f :R x R -> N 的全局最优 . f的输入是圆的中心点，当然，该值是该组中包含的点的数量 . 功能图将是不连续的，阶梯式的 .

    您可以从对应于集合中某点的每个点测试函数开始，通过减小f的值来对点进行排序，然后加强围绕这些点的搜索（例如沿螺旋线移出） .

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

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

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

    回复于
  • 1

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

    此外，还有一种名为K-means的信息可视化/数据挖掘方法，它可以生成给定数据的集群 . 它最终可以与附加功能一起使用，以满足您的目的 .

    K-Means的基本算法是：

    • 将K点放入由聚类项目表示的空间中 - 这些点表示初始组质心

    • 将每个数据项分配给具有最接近质心的组

    • 指定了所有项目后，通过计算点的平均位置重新计算K质心的位置

    • 重复步骤2和3，直到质心不再移动或移动很少

    添加的功能将是：

    • 计算位于K质心的圆内点数

    • 选择最适合你的那个;）

    资料来源：
    K均值算法 - Linköping University
    四叉树 - en.wikipedia.org/wiki/Quadtree

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

    回复于
  • 0

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

    Fast approximation 使用局部敏感散列 . 基本上，将每个点哈希到包含所有附近点的哈希桶 . 设置桶以便仅在附近点之间发生冲突 - 与类似命名的哈希表不同，冲突在这里很有用 . 保持桶中碰撞次数的运行计数，然后使用该桶的中心作为圆的中心 .

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

    它基本上是点数的线性时间，你可以动态更新你的数据集，以每个点的恒定时间逐渐获得新的答案（相对于n =点的常数） .

    更多关于locality-sensitive hashes in general或关于my personal favorite version that would work in this case .

    Better-than-brute-force deterministic approach

    这个想法是：对于每个点，将圆的边缘放在该点上并扫过圆圈以查看哪个方向包含最多的点 . 为所有点执行此操作，我们找到全局最大值 .

    围绕点p的扫描可以在n log n时间内通过以下方式完成：（a）找到每个其他点q的角度间隔，使得当我们将圆放置在角度θ时，则它包含q; （b）对间隔进行排序，以便我们可以在线性时间内围绕p进行行进/扫描 .

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

    回复于
  • 2

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

    设 f(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)
    alt text
    的最大值 .

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

    回复于
  • 1

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

    这是一种非常快速的算法，可以快速推广大型数据集，但并不总是准确的，为了提高准确性，您可以将垃圾箱切成更小更小的片段，或者将垃圾箱位置向左或向右移动n次，并使用投票系统选择试验之间最常出现的答案 .

    回复于
  • 0

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

    当然，由于舍入错误，您可能会失去一些好的区域或“幻觉”好的区域 . 也许你可以尝试先进行粗略的像素化，然后改进有前景的区域 .

    回复于
  • 18

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

    回复于

相关问题