ios - 如何确定 MKMapRect 中 MKAnnotation 对象最集中的区域？

Question

给定一个 MKMapView，它包含 map 上不同点的可变数量的注释([mapView annotations])和 MKMapRect 值MKMapRectWorld，如何确定 map 上最集中于 MKAnnotation 对象(可能是彼此最接近的 5-15 个注释)的区域？

示例场景:

* Coffee finder:确定 map 上星巴克最多的区域

* K9 统计:确定 map 上哪个区域的可卡犬最多

“区域”可以是设置的矩形大小或由注释 block 确定，我不一定关心。感谢您的帮助!

Answer 1

你会发现related question有帮助。

另请查看 K-means_algorithm

K-means_algorithm

如果您有 N 个注释并想分成 K 个部分，您可以使用 K 均值算法找到 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- 如果要坚持最小面积(最大浓度)定义，那么您将需要进行大量计算

一个。首先确定给定组的边界注释，这本身就是一个巨大的问题。

计算每个多边形的 are 并查看哪个最少。不复杂但计算要求高)

EDIT2:

我尽我所能，最后认为这道题属于专业数学网站。我问了你的问题here从答案中，您可以获得讨论此问题和解决方案的论文 here .他们讨论的问题是给定N个点，找出面积为convex hull的K个点是最小的。