给定一个在地图上的各个点MKMapView包含可变数量的注释（
[mapView annotations]MKMapRectMKMapRectWorldMKAnnotation
示例场景：
*咖啡查找器：确定地图的哪个区域有最多星巴克
* K9 统计：确定地图的哪个区域拥有最多可卡犬
“区域”可以是设置的矩形大小或由注释块确定，我不一定关心。谢谢你的帮助！
问问题
717 次
1 回答
2
您会发现相关问题很有帮助。
还要看看 K-means_algorithm
K-means_algorithm
如果您有 N 个注释并且想要分成 K 个部分，您可以使用 K-means-algorithm 找到每个 K 个部分的中心（这将满足某些标准。例如，最小化簇内平方和）。一旦你有中心找出中心和离中心最远的注释之间的距离，它将给出你感兴趣的区域的半径。K-means_algorithm 有多种变体，您可以根据性能和实现的难易程度选择任何一种。
编辑：我没有实现以下，但认为肯定会给出解决方案之一
如果您对范围 5-10 没问题，则可以有多种解决方案。所以我们会找到解决方案之一。
1-假设您有（N = 100）个注释，并且想要其中（P = 15）个注释最密集。
2-然后我们将N个注释随机分成K = N / P组（这里K = 7）
3- 使用 K-means 算法，最终我们将有 K 个可以区分为单独实体的组。
4-这些 K 组将具有最小“簇内平方和”的属性。
5-如果您想节省计算时间，您可以将最集中组的定义放宽为最小“簇内平方和”，而不是由它们限制的区域。
6- 从获得的 K 组中选择一个满足您的标准的组。
7-如果要坚持最小面积（最大浓度）定义，那么您将需要进行大量计算
一种。首先确定给定组的边界注释，这本身就是一个巨大的问题。
湾。计算每个多边形的面积，看看哪个最少。不复杂但计算要求高）
EDIT2：
我尽我所能，最后认为这个问题属于专业数学网站。我在这里问了你的问题，从答案中，你可以在这里得到讨论这个问题和解决方案 的论文。他们讨论的问题是给定N个点，找到凸包面积最小的K个点。
于 2012-01-24T08:38:40.553 回答