logo标签列表

使用给定半径的圆覆盖最多点的算法

c++algorithmgeometrypoints
46

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

需要一个算法来确定圆的位置，使其覆盖尽可能多的点。当然，有许多这样的位置，因此算法应该返回其中一个位置。
精度不重要，算法可能会出现小错误。

以下是一个示例图片：
Example

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

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

算法的速度不需要很快，但也不应该太慢（因为我知道一些对这种情况很慢的解决方案）。

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

你在分配点数方面没有任何限制吗？ - Pontus Gagge
这听起来像是一个很棒的 codegolf。 - bobobobo
@bobobobo 我真的不这么认为。相当无聊，没有确切的获胜条件...但是请随意创建这样的问题。 - Oleh Prypin
10个回答
25

经过修订以更好地表达，如下所示：

基本观察：

  • 我假设半径为1，因为这不会改变任何东西。
  • 对于任意两点，存在至多两个它们位于其上的单位圆。
  • 如果您已经有了一个解决问题的圆，您可以将其移动直到其中包含两个给定集合中的点，同时保持相同数量的给定集合内部的点。

算法如下：

  • 对于每一对点，如果它们之间的距离小于2，则计算通过这两点的两个单位圆C1和C2。
  • 计算您的集合中C1和C2内的点数。
  • 取最大值。
假设您在解决问题时已经有了解决方案的圆，您可以将其移动，直到它包含集合中的两个点，同时保持同样数量的集合点在其中。- 我认为这不正确。无论如何，考虑一个（勉强）适合半径为 r 的圆的三角形。三角形的每两个点之间的距离都是 > 2。再考虑两个相互距离 < 2 的非常远离三角形的点。我认为您的算法只会把这两个点作为解决方法。在我看来，您的算法是错误的，它甚至没有在任何地方使用 r。 - IVlad
3
对于任意两点之间距离小于2r的情况，存在两个半径为r的圆可以穿过这两个点。如果两个点恰好相隔2r，则只有一个圆。就这两个点而言，这些圆是“最佳的”：由于这些点位于圆的边缘，所以圆覆盖了最大的额外空间（可能还包括其他点）。迭代所有点对将给出所有至少包含2个点的可能圆。检查这些圆包含的点数，并选择包含点数最多的那个圆。 - DevSolar
这个算法的时间复杂度可以从O(n^3)降低到O(n^2 * mlogn)（其中m是每个测试圆中平均点数）。如果将所有点放入四叉树中，并在测试每个圆时使用它来计算包含的其他点，那么大O的数学计算会变得混乱。但是，通过使用四叉树来识别候选点对，这些点对足够接近以值得进行测试，可以进一步减少时间复杂度。 - Alan
@Alan：平均而言，只有O(n)对点在2r范围内（假设均匀分布），因此它已经小于O（n ^ 3）了。所以你实际上得到了类似O（n ^ 2）的东西。 - Alexandre C.
我想知道如果考虑浮点数的不精确性会发生什么。 - starblue
显示剩余23条评论
9
这是文献中的“磁盘部分覆盖问题”——这应该是您开始搜索的好地方。下面是一篇涵盖可能解决方法的论文，但其中的数学内容比较深奥：磁盘部分覆盖问题的近似算法设计 事实上，这属于计算几何领域，非常有趣但很难入门。deBerg对与该主题相关的各种算法进行了很好的概述。
我认为这种情况下不能使用该算法，因为我只有一个圆。 - Oleh Prypin
在您的情况下，该论文中的“k”为1。 - Joel
5
这里有两个想法：一种O(n)的近似算法和一种O(n^2 log n)的精确（非近似）算法：
快速近似
使用局部敏感哈希。基本上，对每个点进行哈希处理，将其哈希到包含所有附近点的哈希桶中。桶被设置为仅在附近点之间发生冲突 - 与同名哈希表不同，在这里冲突是有用的。保持桶中发生冲突的数量的运行计数，然后将该桶的中心用作您的圆心。
我承认，这是一个快速解释一个第一次听到它并不是很明显的概念。一个类比是询问一群人他们的邮政编码，并使用最常见的邮政编码来确定最大人口的圆。它不是完美的，但是一个很好的快速启发式算法。
就点数而言，它基本上是线性的，并且你可以实时更新数据集，以每个点恒定时间地获取新答案（相对于点数n）。

更多关于 局部敏感哈希算法 或者 我比较喜欢的适用于这种情况的版本 的内容。

优于暴力枚举的确定性方法

思路是：对于每个点，将一个圆的边缘放在该点上，并扫描圆以查看哪个方向包含最多的点。对所有点执行此操作，我们找到全局最大值。

绕点p扫描可以在nlogn时间内完成：（a）找到每个其他点q的角度间隔，使得当我们将圆置于角度θ时，它包含q;（b）排序间隔，以便我们可以在线性时间内绕p进行扫描/扫描。

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

在第二种情况下，您难道没有额外的n乘数来计算覆盖率吗？您仍需要一个额外的循环来计算圆内有多少个点。 - Joric
2
嗨@Joric。简短回答：我认为确实有一个精确的O(n^2 log n)时间复杂度的答案，但是我当时解释得太少了（6.5年前）。固定点p并想象一个单位圆绕着p旋转，与p相切。使用从p到c =圆心的角度theta跟踪圆。对于每个其他点q，我们可以找到角度区间[theta_1，theta_2]，其中q将在圆内（包括边界）。现在，当我们绕圆旋转时，我们可以使用预先计算的[theta_1，theta_2]区间有效地更新哪些点在c中。每个圆更新的平摊时间为O(1)。 - Tyler
@Tyler，你能否提供一些关于摊销分析的参考资料？ - codeR
4
如果您想要简单的解决方案，可以随机取一个位置（x,y），计算圆内的点数并比较前一位置。选取最大值后重复此操作任意次数。为什么会被踩？您听说过蒙特卡罗方法吗？对于海量数据，确定性算法可能需要相当长的时间才能得出结果。
3
“精度不是很重要，算法可能会犯一些小错误。” - mip
合理的时间也是以与给定点数的关系来表达的。例如，O(n^3)表示算法完成所需的时间与点数的立方成正比。 通常，算法的“合理”时间为：多项式（n^3、n^8、n^k）：可以接受；线性（n、3n、(1/9)n、kn，都是n）：很好；对数：非常好。 - maxwellb
好的，我认为你的观点很有道理，所以我没有给你点踩。干杯！ - maxwellb
对于我的情况来说，这个解决方案还不错。 - Oleh Prypin
2
一个好的蒙特卡罗算法可以将误差概率作为某个参数的函数进行限制（例如，在您的情况下是迭代次数）。我在您的解决方案中没有看到任何这样的分析。 - Eyal Schneider
@EyalSchneider 我只是提供了一个大致的想法。可以通过将MC方法与以前的答案编译来改进算法。例如，对于圆形，我会选择位置，这些位置不是完全随机的，而是那些圆边缘和两个点之间存在关联的位置。如果您另外提供一种使用一次对（例如记住它们）的方法，那么您可以估计误差概率随着迭代次数等于平面上所有可以构建圆的对数而渐近地减少到零。 - mip
2
问题在于寻找函数f:R x R -> N的全局最优解。输入为圆心点，输出为该点所包含的集合中点的数量。该函数图像不连续，呈梯形状。
您可以从与集合中的点对应的每个点开始测试函数，按f值递减顺序排序，然后在这些点周围加强搜索（例如沿着螺旋线移动）。
另一种选择是考虑连接集合中任意两个点的线段的所有交点。最优点可能位于其中一个交点上，但其数量可能太多而无法考虑。
您还可以混合选项1和2，并考虑围绕'好的集合点'生成的线段的交点。
总之，除非集合点的数量很少（允许您检查所有交点），否则我认为您不能保证找到最优解（只能得到一个好的解决方案）。
我看到同样的答案总共发布了三次 - 可能是错误。你能删除其中两个吗？ - Suma
点数很少（我刚刚编辑了问题）。但是我不明白一些东西，比如...你怎么能画出一个二元函数的图形？ - Oleh Prypin
好的，你不必画出这个图表，我只是在脑海中想象它...就像这样：http://soft.proindependent.com/doc/manual-en/pics/3D-function-plot-modified.png - Mau
@Mau：点集总是有限的，因为计算机无法处理无限集合。尽管如此，这是一种非线性离散优化问题，是最难的优化问题类之一。与线性或连续优化问题不同，对于这类问题没有已知的良好通用算法。 - Philipp
1
@Philipp 我认为在一般情况下只有线性（非整数）是可处理的。但我们偏离了主题 :-) - Mau
显示剩余3条评论
1

如果精度不重要且算法可能会出现小错误，那么我认为以下内容。

假设 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 的最大值。

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

@BlaXpirit，如果你不知道数学，通过编程也可以实现很多。但是为了有效地解决并理解像你发布的那个任务的解决方案，你应该在数学方面更加优秀。（顺便说一下，Alexey也在使用LaTeX符号来编写数学函数，这与数学无关，但这是你最好了解的事情之一） - P Shved
@Pavel，对于您的不可微分函数，梯度下降算法无法正确工作。 - Alexey Malistov
@Alexey，没错，但否则你会冒着找到一个不是解的点的风险。实际上，我确信（尽管我没有试图证明），对于每个连续函数，都可以构造一个输入，使算法失败得像我们希望的那样糟糕。 - P Shved
1
@Pavel，我也很确定。我在我的回答中以“如果精度不重要，那么...”开头。 - Alexey Malistov
@Alexey，好的，可能我错过了。对于无关的评论感到抱歉。 - P Shved
显示剩余2条评论
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

1

你可以对整个区域进行像素化，然后进入每个点并增加该点周围半径内所有像素的值。具有最高和的像素是不错的选项。

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

0
我可以建议使用密度图吗？找到x和y的最小和最大边界。将x和y边界的范围分成宽度等于你的圆直径的bin。分别计算每个bin中x和y的点的数量。现在，在你的密度图上找到最高排名的x bin与最高排名的y bin之间的交集。
这是一个非常快速的算法，可以快速概括大型数据集，但并不总是准确的。为了提高准确性，您可以将bin切分成越来越小的片段，或者将bin位置向左或向右移动n次，并使用投票系统在试验之间选择出现最频繁的答案。
我有非常小的数据集，而不是大型数据集。因此这里是不正确的。 - Oleh Prypin
-4
不是这样的。你可以有一个以不属于该集合的点为中心的最佳圆。 - Mau
2
你现在做得很好，继续提出有趣的问题吧！ - user177800
1
@BlaXpirit 如果答案不正确，请取消选择它作为被接受的解决方案。 - chollida
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接