用一个给定半径的圆覆盖最大点数的算法 [英] Algorithm to cover maximal number of points with one circle of given radius

问题描述

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

Let's imagine we have a plane with some points on it. We also have a circle of given radius.

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

I need an algorithm that determines such position of the circle that it covers maximal possible number of points. Of course, there are many such positions, so the algorithm should return one of them.
Precision is not important and the algorithm may do small mistakes.

这是一个示例图片:

Here is an example picture:

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

Input:
  int n (n<=50) – number of points;
  float x[n] and float y[n] – arrays with points' X and Y coordinates;
  float r – radius of the circle.

输出:
  float cx 和 float cy –圆心坐标

Output:
  float cx and float cy – coordinates of the circle's center

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

Lightning speed of the algorithm is not required, but it shouldn't be too slow (because I know a few slow solutions for this situation).

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

C++ code is preferred, but not obligatory.

推荐答案

按照建议修改为更好的措辞:

Edited to better wording, as suggested :

基本观察:

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

那么算法是:

• 对于每一对点，如果它们的距离是 <2，计算通过它们的两个单位圆C1和C2.
• 计算你的集合在 C1 和 C2 内的点数
• 尽最大努力.

这篇关于用一个给定半径的圆覆盖最大点数的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！