algorithm - 如何找到包含用户选择的所有 POI(在指定半径内)的 POI 集群？

Question

我为这个令人费解的标题道歉。不用说，我的搜索关键词用完了，但还没有找到任何我可以研究的主题。

我正在构建一个系统，用户可以在其中选择多个 POI 标准(显示“餐厅”、“加油站”等的复选框)。然后我想在 map 上返回一个位置，该位置在用户选择的每个 POI 的 x 距离内。

假设我有 map 上每个 POI 的信息，找到包含所有指定点的点簇的算法是什么？

一个抽象的描述方式是:假设我有几组网格点。在网格上找到一个半径为 r(固定)的圆，该圆至少包含每个集合中的一个点的算法可能是什么？

如果我能遵循任何帮助或指示，我将不胜感激。

Answer 1

这个问题可以用梯度下降法解决。令 n 为用户选择的 POI(点)数。思路是一直向距离所有n个点最近的点下降。

ita = 0.01; //learning rate.
i=0 ;    // weight decay rate
First start with the mean point p(x,y) of all the points.
while (p is not within from each point || no improvement in p during last iteration).
    let q(x,y) be the farthest point from p.
    update: p(x,y)+= ita*(q(x,y)-p(x,y))/(i*n*x)
return p if exist else NULL if timeout happens.

这就是你想要的。这个算法解决了你的问题。如果您认为最接近所有 n 个点的点将是更好的竞争者，您也可以对其进行修改。

也看到这个，The "All-Pairs Closest Points" Problem .