15

有很多不好的方法可以做我想做的事,但这似乎是“必须有更好的方法”的案例之一。

我在显示许多注释的 iPhone 应用程序中使用 MKMapView。假设美国各州的每个城镇都有一个注释进行概念性讨论,因此屏幕上有大量注释。当用户缩小地图时,这些注释开始相互挤压,直到它们重叠并且变得难以单独挑选出来。

我想做的是,以特定的注释密度(比如当任何注释重叠时),将这些注释合并为一个注释,表明它包含许多子注释(一些视觉指示器说,“放大你会看到更多的注释”)。

我可以在批注视图上调用 CGRectIntersectsRect ,但使用它似乎是一个 N^2 问题——我必须为每个批注迭代每个批注。考虑这个伪代码:

FOR firstAnnotationView IN allAnnotationViews
   FOR 所有AnnotationViews 中的第二个AnnotationView
       IF CGRectIntersectsRect(firstAnnotationView.frame, secondAnnotationView.frame)
           // 找到两个重叠的注解,合并它们
       万一
   ENDFOR
ENDFOR

您可以看到为什么这会很慢,并且每次放大或缩小地图时都必须运行它!

那么,你们将如何检测地图中的重叠注释,并以精通性能的方式智能地整合它们呢?

4

3 回答 3

1

you search for something like this, aren't you?

http://www.cocoanetics.com/parts/dtclustermaker/

于 2010-12-18T20:05:50.163 回答
1

我会根据经度/纬度对您的注释进行分类,然后使用这些分类进行合并。基本思想看起来像这样:

#include <vector>

float minLongitude = 180.0f;
float maxLongitude = -180.0f;
float longitudeBinSize = 0.1; // Degrees
float minLatitude = -90.0f;
float maxLatitude = 90.0f;
float latitudeBinSize = 0.1; // Degrees
int numBinColumns = int((maxLongitude - minLongitude) / longitudeBinSize);
int numBinRows = int((maxLatitude - minLatitude) / latitudeBinSize);

void calcBinCoords(float longitude, float latitude, int &column, int &row) {
    column = int((latitude - minLatitude) / latitudeBinSize);
    row = int((longitude - minLongitude) / longitudeBinSize);
}

typedef std::vector<AnnotationView *> AnnotationViews;

void binAnnotations(NSArray *annotationViews, std::vector<AnnotationViews> &binnedAnnotations) {
    binnedAnnotations.clear();
    binnedAnnotations.resize(numBinColumns * numBinRows);
    for (AnnotationView *annotationView in annotationViews) {
        int column, row;
        calcBinCoords(annotationView.longitude, annotationView.latitude, column, row);
        binnedAnnotations[row * numBinColumns + column].push_back(annotationView);
    }
}

longitudeBinSize 和 latitudeBinSize 的值将是您在合并时打算搜索的最大距离。一旦所有东西都在箱中,那么您的搜索问题只涉及在相邻箱中的值列表中搜索候选者。此外,由于您将在合并期间扫描阵列,您实际上只需要为您处理的每个 bin 检查三个相邻的 bin - (column+1,row) 处的 bin,(column,row+1 处的 bin ),以及 (column+1,row+1) 处的 bin。

您可以使用 NSMutableArrays 而不是 std::vector 作为垃圾箱,但听起来您有大量项目要处理,我怀疑 std::vector 会更快。不过,这只是我的偏好,甚至可能不在乎。如果你使用 ObjC 而不是 ObjC++ 那么你当然不能使用 std::vector 。

于 2010-11-24T21:15:47.287 回答
0

您可以使用Geohash对注释进行分区。这将在尝试“合并”您的注释时减少搜索空间。

于 2010-12-15T12:13:36.093 回答