algorithm - 如何选择半径中包含的最多散点？

Question

设置示例

在在这里询问之前，我已经尝试到处寻找问题的解决方案。我的问题是我不太擅长数学或统计学，以了解任何给定的算法都会对解决方案有所帮助。

在我的示例中，我有一个看起来像散点图的东西。只有一堆点随机放置在笛卡尔坐标平面上。我希望能够在这个平面上绘制一个具有特定半径的圆。圆圈必须包含尽可能多的点。

我应该采取哪些步骤来计算绘制这个圆的最佳点？

我在寻找...

我想要一组我必须采取的步骤，以便找出我应该在图表上的哪个位置开始绘制（圆的中心点）。如果你有代码，我很擅长破译我不一定知道的语言，但我会用 Lua 写这个（不幸的是我无法访问 C 部分）。

我真的很想了解该解决方案的工作原理，因此我将不胜感激任何来源或解释。仅供参考，性能非常重要，但我目前正在寻找任何解决方案。

奖金 ：）

既然我正在写这篇文章，我想我不妨问问我希望我的代码执行的其他高级功能。但是当我真正踏入大门时，我总能弄清楚这些。

• 离圆心较远的点比离圆心更近的点更接近全重。权重可以简单地是一个线性函数，如果半径为 10，则距中心 1 仅是全权重的 10%，距中心 2 仅是全权重的 20%。距离中心正好 10 度会给你 100% 的重量。

• 引入了时间，圆的中心也是图上的一个点（这个点不是其他点的一部分，不应与它们一起计算）。圆的中心以恒定的速度移动，您必须选择一个足够靠近中心的点，因为所有点的所有权重都会随着时间的推移而衰减。所以画圆的速度越快越好。（这是高度理论化的，我不确定衰变会是什么样子）。

非常感谢您阅读本文并考虑我的问题！我可以提供其他详细信息或回答您可能有的任何问题。

Answer 1

有一种可能更快的方法来找到需要更多数学的最佳圆，并延伸到两个精确点中的第一个。

取一个覆盖您感兴趣的区域的网格，并将 1 放在该网格中，在您绘制了一个点的地方，将 0 放在您没有绘制的地方。您现在需要计算网格中每个点的分数。您可以通过将网格中每个点的值乘以权重来做到这一点，该权重取决于该点与您正在评分的点之间的距离，然后将结果相加。这涵盖了您的基本问题（圆圈内的点的权重为 1，否则为 0）和您的第一个高级点，其中权重逐渐变化。

以这种方式查看问题，您需要将其应用于网格的二维过滤器。应用后，您只需要找到结果中的最高得分点即可。这样做显然会很慢，但事实证明，您可以使用快速傅里叶变换加速这种事情，并且您可以使用数学库来计算它。

如果您没有在数学或统计方面进行过练习，那么您将需要对此进行很好的解释-恐怕比我所能提供的要好。它做了很多，但我还没有找到我真正喜欢的解释。您可以查看http://www.analog.com/static/imported-files/tech_docs/dsp_book_Ch24.pdf，它也在http://archive.gamedev.net/archive/reference/programming/features/imageproc中被引用/page2.html。

Answer 2

这将需要大量的计算/数据，但您可以检查每个点以查看这些点是否在那里。不是真正的数学，但它的工作原理......也不是很快。

我不知道您使用什么引擎来测试您的代码，但我使用的是 LOVE2D。我强烈推荐它，如果不是为了让你的解决方案可视化的游戏制作。您可以使用其他东西，这只是个人喜好。如果您对任何 LOVE 功能有疑问，请访问love2d 网站上的 wiki。

function love.load() 
    points = { { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) } }

    circles = {}
    for i = 0, love.graphics.getWidth() do
        for ii = 0, love.graphics.getHeight() do
            table.insert( circles, { hits = check_points( i, ii, 20, points ), x = i, y = ii } )
        end
    end
    circs = { { circles[1].hits, circles[1].x, circles[1].y } }
    largest = circs[1][1]

    for i = 1, #circles do
        if circles[i].hits >= largest then
            if circles[i].hits > largest then 
                circs = nil
                circs = {}
                table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
                largest = circs[1][1]
            elseif circles[i].hits == largest then
                local distance = math.sqrt( ( circles[i].x - circs[#circs][2] ) ^ 2 + ( circles[i].y - circs[#circs ][3] ) ^ 2 )
                if distance > 40 then
                    table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
                    largest = circs[1][1]
                end 
            end
        end
    end
end

function love.draw() 
    love.graphics.setColor( 255, 0, 0 )
    for i = 1, #circs do
        love.graphics.circle( 'fill', circs[i][2], circs[i][3], 20 )
    end
    love.graphics.setColor( 255, 255, 255 )
    for i = 1, #points do
        love.graphics.circle( 'fill', points[i][1], points[i][2], 1 )
    end
end

function check_points( x, y, r, ... )
    local hits = 0
    local p = ...
    for i = 1, #p do
        local distance = math.sqrt( ( x - p[i][1] ) ^ 2 + ( y - p[i][2] ) ^ 2 )
        if distance <= r then
            hits = hits + 1
        end
    end
    return hits
end

如果有人有更好、更省时的解决方案，我想知道。我调查了一些事情，但没有任何真正的工作。

请注意，这个获得了所有可能的分组，而不是圆圈。如果要获取所有圈子，请删除

elseif circles[i].hits == largest then
    local distance = math.sqrt( ( circles[i].x - circs[#circs][2] ) ^ 2 + ( circles[i].y - circs[#circs ][3] ) ^ 2 )
    if distance > 40 then
        table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
        largest = circs[1][1]
    end 
end

并将其替换为

else
    table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
    largest = circs[1][1]
end

如果你只想得到第一个或最后一个，你可以取出整个

if circles[i].hits >= largest then
    if circles[i].hits > largest then 
        circs = nil
        circs = {}
        table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
        largest = circs[1][1]
    elseif circles[i].hits == largest then
        local distance = math.sqrt( ( circles[i].x - circs[#circs][2] ) ^ 2 + ( circles[i].y - circs[#circs ][3] ) ^ 2 )
        if distance > 40 then
            table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
            largest = circs[1][1]
       end 
   end
end

并简单地替换它

if circles[i].hits >= largest then 
    circs = nil
    circs = {}
    table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
    largest = circs[1][1]
end

大于或等于将使您获得最后一个，大于或等于将使您获得第一个。你可以建立更多的东西，比如让它选择中间的圆圈而不是左边的圆圈，或者类似的东西。但同样，这并不是真正的算法，更像是一种“扫描和检查”之类的东西。它总是得到最佳解决方案，虽然......

您还可以更改 for 循环以在 .5 或 .25 或其他内容中进行迭代。你得到的越小，你得到的越精确，但也需要更多的时间。