如何在iOS地图上高效的显示大量数据

Question

如何在iOS地图上高效的显示大量数据

徐孜琳 · Answer

，所以我们用C语言来构造这个数据结构。为了确保大量的数据不会让用户感到迷惑，所以我们还需要想出一个合并数据的解决方案。最后，为了更好的适应市场，我们需要把app做的更完善一些。
　　完成这个教学后，你将学到这款app的所有核心内容。

　　数据结构
　　首先我们先来分析下数据，搞清我们要如何处理数据。旅馆数据中包含了一系列的坐标点（包括纬度和经度），我们需要根据这些坐标点在地图上进行标注。地图可以任意的拖动并放大缩小，所以我们不需要把所有的点都全部绘制出来，我们只需要绘制可以显示在屏幕上的点。核心问题是：我们需要出显示在屏幕上的所有的点，所以我们要想出一个查找算法，查找存在于一个矩形范围内的所有点。
　　一个简单的解决方式就是遍历所有的点，然后判断（xMin<=x<=xMax并且yMin<=y<=yMax），很不幸，这是一个复杂度为O（N）的算法，显然不适合我们的情况。
　　这儿有个更好的解决方法，就是我们可以利用对称性来减少我们的范围。那么如何能通过的每一次的迭代来减少的范围呢？我们可以在每个区域内都加索引，这样可以有效减少的范围。这种区域索引的方式可以用四叉树来实现，复杂度为O（H）（H是的那个点所在的树的高度）
　　四叉树
　　四叉树是一个数据结构，由一系列的结点（node）构成。每个结点包含一个桶（bucket）跟一个包围框（boundingbox）。每个桶里面有一系列的点（nt）。如果一个点包含在一个外包围框A中，就会被添加到A所在结点的桶（bucket）中。一旦这个结点的桶满了，这个结点就会分裂成四个子结点，每个子节点的包围框分别是当前结点包围框的1/4。分裂之后那些本来要放到当前结点桶中的点就都会放到子容器的桶中。
　　那么我们该如何来对四叉树进行编码呢？
　　我们先来定义基本的结构：
　　typedef struct TBQuadTreeNodeData {
　　double x;
　　double y;
　　void * data;
　　} TBQuadTreeNodeData;
　　TBQuadTreeNodeData TBQuadTreeNodeDataMake( double x, double y, void * data);
　　
　　typedef struct TBBoundingBox {
　　double x0; double y0;
　　double xf; double yf;
　　} TBBoundingBox;
　　TBBoundingBox TBBoundingBoxMake( double x0, double y0, double xf, double yf);
　　
　　typedef struct quadTreeNode {
　　struct quadTreeNode* northWest;
　　struct quadTreeNode* northEast;
　　struct quadTreeNode* southWest;
　　struct quadTreeNode* southEast;
　　TBBoundingBox boundingBox;
　　int bucketCapacity;
　　TBQuadTreeNodeData *nts;
　　int count;
　　} TBQuadTreeNode;
　　TBQuadTreeNode* TBQuadTreeNodeMake(TBBoundingBox boundary, int bucketCapacity);
　　TBQuadTreeNodeData结构包含了坐标点（纬度，经度）。void*data是一个普通的指针，用来存储我们需要的其他信息，如旅馆名跟电话号码。TBBoundingBox代表一个用于范围的长方形，也就是之前谈到(xMin<=x<=xMax&&yMin<=y<=yMax)的那个长方形。左上角是(xMin,yMin)，右下角是(xMax,yMax)。
　　最后，我们看下TBQuadTreeNode结构，这个结构包含了四个指针，每个指针分别指向这个结点的四个子节点。它还有一个外包围框和一个数组（数组中就是那个包含一系列坐标点的桶）。
　　在我们建立完四叉树的同时，空间上的索引也就同时形成了。这是生成四叉树的演示动画。

　　下面的代码准确描述了以上动画的过程：
　　void TBQuadTreeNodeSubdivide(TBQuadTreeNode* node)
　　{
　　TBBoundingBox box = node->boundingBox;
　　
　　double xMid = (box.xf + box.x0) /
2.0;
　　double yMid = (box.yf + box.y0) /
2.0;
　　
　　TBBoundingBox northWest = TBBoundingBoxMake(box.x0, box.y0, xMid, yMid);
　　node->northWest = TBQuadTreeNodeMake(northWest, node->bucketCapacity);
　　
　　TBBoundingBox northEast = TBBoundingBoxMake(xMid, box.y0, box.xf, yMid);
　　node->northEast = TBQuadTreeNodeMake(northEast, node->bucketCapacity);
　　
　　TBBoundingBox southWest = TBBoundingBoxMake(box.x0, yMid, xMid, box.yf);
　　node->southWest = TBQuadTreeNodeMake(southWest, node->bucketCapacity);
　　
　　TBBoundingBox southEast = TBBoundingBoxMake(xMid, yMid, box.xf, box.yf);
　　node->southEast = TBQuadTreeNodeMake(southEast, node->bucketCapacity);
　　}
　　
　　bool TBQuadTreeNodeInsertData(TBQuadTreeNode* node, TBQuadTreeNodeData data)
　　{
　　// Bail if our coordinate is not in the boundingBox
　　if (!TBBoundingBoxContainsData(node->boundingBox, data)) {
　　return false ;
　　}
　　
　　// Add the coordinate to the nts array
　　if (node->count < node->bucketCapacity) {
　　node->nts[node->count++] = data;
　　return true ;
　　}
　　
　　// Check to see if the current node is a leaf, if it is, split
　　if (node->northWest == NULL) {
　　TBQuadTreeNodeSubdivide(node);
　　}
　　
　　// Traverse the tree
　　if (TBQuadTreeNodeInsertData(node->northWest, data)) return true ;
　　if (TBQuadTreeNodeInsertData(node->northEast, data)) return true ;
　　if (TBQuadTreeNodeInsertData(node->southWest, data)) return true ;
　　if (TBQuadTreeNodeInsertData(node->southEast, data)) return true ;
　　
　　return false ;
　　}
　　现在我们已经完成了四叉树的构造，我们还需要在四叉树上进行区域范围并返回TBQuadTreeNodeData结构。以下是区域范围的演示动画，在浅蓝区域内的是所有的标注点。当标注点被到在指定的区域范围内，则会被标注为绿色。
　　以下是代码：
　　typedef void (^TBDataReturnBlock)(TBQuadTreeNodeData data);
　　
　　void TBQuadTreeGatherDataInRange(TBQuadTreeNode* node, TBBoundingBox range, TBDataReturnBlock block)
　　{
　　// If range is not contained in the node's boundingBox then l
　　if (!TBBoundingBoxIntersectsBoundingBox(node->boundingBox, range)) {
　　return ;
　　}
　　
　　for ( int i = 0; i < node->count; i++) {
　　// Gather nts contained in range
　　if (TBBoundingBoxContainsData(range, node->nts[i])) {
　　block(node->nts[i]);
　　}
　　}
　　
　　// Bail if node is leaf
　　if (node->northWest == NULL) {
　　return ;
　　}
　　
　　// Otherwise traverse down the tree
　　TBQuadTreeGatherDataInRange(node->northWest, range, block);
　　TBQuadTreeGatherDataInRange(node->northEast, range, block);
　　TBQuadTreeGatherDataInRange(node->southWest, range, block);
　　TBQuadTreeGatherDataInRange(node->southEast, range, block);
　　}
　　用四叉树这种结构可以进行快速的。在一个包含成百上千条数据的数据库中，可以以60fps的速度上百条数据。
　　用旅馆数据来填充四叉树
　　旅馆的数据来自于POIplaza这个网站，而且已经格式化成csv文件。我们要从硬盘中读取出数据并对数据进行转换，最后用数据来填充四叉树。
　　创建四叉树的代码在TBCoordinateQuadTree类中：
　　typedef struct TBHotelInfo {
　　char * hotelName;
　　char * hotelPhoneNumber;
　　} TBHotelInfo;
　　
　　TBQuadTreeNodeData TBDataFromLine(NSString *line)
　　{
　　// Example line:
　　
　　
　　NSArray *components = [line componentsSeparatedByString:@ "," ];
　　double latitude = [components[1] doubleValue];
　　double longitude = [components[0] doubleValue];
　　
　　TBHotelInfo* hotelInfo = malloc( sizeof (TBHotelInfo));
　　
　　NSString *hotelName = [components[2] stringByTrimmingCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]];
　　hotelInfo->hotelName = malloc( sizeof ( char ) * hotelName.length + 1);
　　strncpy(hotelInfo->hotelName, [hotelName UTF8String], hotelName.length + 1);
　　
　　NSString *hotelPhoneNumber = [[components lastObject] stringByTrimmingCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]];
　　hotelInfo->hotelPhoneNumber = malloc( sizeof ( char) * hotelPhoneNumber.length + 1);
　　strncpy(hotelInfo->hotelPhoneNumber, [hotelPhoneNumber UTF8String], hotelPhoneNumber.length + 1);
　　
　　return TBQuadTreeNodeDataMake(latitude, longitude, hotelInfo);
　　}
　　
　　- ( void )buildTree
　　{
　　NSString *data = [NSString stringWithContentsOfFile:[[NSBundle mainBundle] pathForResource:@ "USA-HotelMotel" ofType:@"csv" ] encoding:NSASCIIStringEncoding error:nil];
　　NSArray *lines = [data componentsSeparatedByString:@ "\n" ];
　　
　　NSInteger count = lines.count - 1;
　　
　　TBQuadTreeNodeData *dataArray = malloc( sizeof(TBQuadTreeNodeData) * count);
　　for (NSInteger i = 0; i < count; i++) {
　　dataArray[i] = TBDataFromLine(lines[i]);
　　}
　　
　　TBBoundingBox world = TBBoundingBoxMake(19, -166, 72, -53);
　　_root = TBQuadTreeBuildWithData(dataArray, count, world, 4);
　　}
　　现在我们用iPhone上预加载的数据创建了一个四叉树。接下来我们将处理app的下一个部分：合并数据（clustering）。
　　合并数据（clustering）
　　现在我们有了一个装满旅馆数据的四叉树，可以用来解决合并数据的问题了。首先，让我们来探索下合并数据的原因。我们合并数据是因为我们不想因为数据过于庞大而使用户迷惑。实际上有很多种方式可以解决这个问题。GoogleMaps根据地图的缩放等级（zoomlevel）来显示搜索结果数据中的一部分数据。地图放的越大，就越能清晰的看到更细节的标注，直到你能看到所有有效的标注。我们将采用这种合并数据的方式，只显示出来旅馆的个数，而不在地图上显示出所有的旅馆信息。
　　最终呈现的标注是一个中心显示旅馆个数的小圆圈。实现的原理跟如何把图片缩小的原理差不多。我们先在地图上画一个格子。每个格子中包含了很多个小单元格，每个小单元格中的所有旅馆数据合并出一个标注。然后通过每个小单元格中所有旅馆的坐标值的平均值来决定合并后这个标注的坐标值。

如何在iOS地图上高效的显示大量数据

相关文章

相关热门问答