如何找到包含用户选择的所有poi的poi集群(在指定的半径内)?

Question

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

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

假设我有地图上所有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个点的点是更好的竞争者，你也可以修改它。

也看到这个，"所有对最近点"问题