，所以我們用C語言來構(gòu)造這個(gè)數(shù)據(jù)結(jié)構(gòu)。為了確保大量的數(shù)據(jù)不會(huì)讓用戶感到迷惑，所以我們還需要想出一個(gè)合并數(shù)據(jù)的解決方案。最后，為了更好的適應(yīng)市場(chǎng)，我們需要把a(bǔ)pp做的更完善一些?！　⊥瓿蛇@個(gè)教學(xué)后，你將學(xué)到這款app的所有核心內(nèi)容?！　?shù)據(jù)結(jié)構(gòu)　　首先我們先來分析下數(shù)據(jù)，搞清我們要如何處理數(shù)據(jù)。旅館數(shù)據(jù)中包含了一系列的坐標(biāo)點(diǎn)（包括緯度和經(jīng)度），我們需要根據(jù)這些坐標(biāo)點(diǎn)在地圖上進(jìn)行標(biāo)注。地圖可以任意的拖動(dòng)并放大縮小，所以我們不需要把所有的點(diǎn)都全部繪制出來，我們只需要繪制可以顯示在屏幕上的點(diǎn)。核心問題是：我們需要出顯示在屏幕上的所有的點(diǎn)，所以我們要想出一個(gè)查找算法，查找存在于一個(gè)矩形范圍內(nèi)的所有點(diǎn)?！　∫粋€(gè)簡(jiǎn)單的解決方式就是遍歷所有的點(diǎn)，然后判斷（xMin<=x<=xMax并且yMin<=y<=yMax），很不幸，這是一個(gè)復(fù)雜度為O（N）的算法，顯然不適合我們的情況。　　這兒有個(gè)更好的解決方法，就是我們可以利用對(duì)稱性來減少我們的范圍。那么如何能通過的每一次的迭代來減少的范圍呢？我們可以在每個(gè)區(qū)域內(nèi)都加索引，這樣可以有效減少的范圍。這種區(qū)域索引的方式可以用四叉樹來實(shí)現(xiàn)，復(fù)雜度為O（H）（H是的那個(gè)點(diǎn)所在的樹的高度）　　四叉樹　　四叉樹是一個(gè)數(shù)據(jù)結(jié)構(gòu)，由一系列的結(jié)點(diǎn)（node）構(gòu)成。每個(gè)結(jié)點(diǎn)包含一個(gè)桶（bucket）跟一個(gè)包圍框（boundingbox）。每個(gè)桶里面有一系列的點(diǎn)（nt）。如果一個(gè)點(diǎn)包含在一個(gè)外包圍框A中，就會(huì)被添加到A所在結(jié)點(diǎn)的桶（bucket）中。一旦這個(gè)結(jié)點(diǎn)的桶滿了，這個(gè)結(jié)點(diǎn)就會(huì)分裂成四個(gè)子結(jié)點(diǎn)，每個(gè)子節(jié)點(diǎn)的包圍框分別是當(dāng)前結(jié)點(diǎn)包圍框的1/4。分裂之后那些本來要放到當(dāng)前結(jié)點(diǎn)桶中的點(diǎn)就都會(huì)放到子容器的桶中?！　∧敲次覀?cè)撊绾蝸韺?duì)四叉樹進(jìn)行編碼呢？　　我們先來定義基本的結(jié)構(gòu)：　　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結(jié)構(gòu)包含了坐標(biāo)點(diǎn)（緯度，經(jīng)度）。void*data是一個(gè)普通的指針，用來存儲(chǔ)我們需要的其他信息，如旅館名跟電話號(hào)碼。TBBoundingBox代表一個(gè)用于范圍的長(zhǎng)方形，也就是之前談到(xMin<=x<=xMax&&yMin<=y<=yMax)的那個(gè)長(zhǎng)方形。左上角是(xMin,yMin)，右下角是(xMax,yMax)?！　∽詈螅覀兛聪耇BQuadTreeNode結(jié)構(gòu)，這個(gè)結(jié)構(gòu)包含了四個(gè)指針，每個(gè)指針分別指向這個(gè)結(jié)點(diǎn)的四個(gè)子節(jié)點(diǎn)。它還有一個(gè)外包圍框和一個(gè)數(shù)組（數(shù)組中就是那個(gè)包含一系列坐標(biāo)點(diǎn)的桶）。　　在我們建立完四叉樹的同時(shí)，空間上的索引也就同時(shí)形成了。這是生成四叉樹的演示動(dòng)畫。　　下面的代碼準(zhǔn)確描述了以上動(dòng)畫的過程：　　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 ;　　}　　現(xiàn)在我們已經(jīng)完成了四叉樹的構(gòu)造，我們還需要在四叉樹上進(jìn)行區(qū)域范圍并返回TBQuadTreeNodeData結(jié)構(gòu)。以下是區(qū)域范圍的演示動(dòng)畫，在淺藍(lán)區(qū)域內(nèi)的是所有的標(biāo)注點(diǎn)。當(dāng)標(biāo)注點(diǎn)被到在指定的區(qū)域范圍內(nèi)，則會(huì)被標(biāo)注為綠色?！　∫韵率谴a：　　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);　　}　　用四叉樹這種結(jié)構(gòu)可以進(jìn)行快速的。在一個(gè)包含成百上千條數(shù)據(jù)的數(shù)據(jù)庫中，可以以60fps的速度上百條數(shù)據(jù)?！　∮寐灭^數(shù)據(jù)來填充四叉樹　　旅館的數(shù)據(jù)來自于POIplaza這個(gè)網(wǎng)站，而且已經(jīng)格式化成csv文件。我們要從硬盤中讀取出數(shù)據(jù)并對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)換，最后用數(shù)據(jù)來填充四叉樹?！　?chuàng)建四叉樹的代碼在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);　　}　　現(xiàn)在我們用iPhone上預(yù)加載的數(shù)據(jù)創(chuàng)建了一個(gè)四叉樹。接下來我們將處理app的下一個(gè)部分：合并數(shù)據(jù)（clustering）?！　『喜?shù)據(jù)（clustering）　　現(xiàn)在我們有了一個(gè)裝滿旅館數(shù)據(jù)的四叉樹，可以用來解決合并數(shù)據(jù)的問題了。首先，讓我們來探索下合并數(shù)據(jù)的原因。我們合并數(shù)據(jù)是因?yàn)槲覀儾幌胍驗(yàn)閿?shù)據(jù)過于龐大而使用戶迷惑。實(shí)際上有很多種方式可以解決這個(gè)問題。GoogleMaps根據(jù)地圖的縮放等級(jí)（zoomlevel）來顯示搜索結(jié)果數(shù)據(jù)中的一部分?jǐn)?shù)據(jù)。地圖放的越大，就越能清晰的看到更細(xì)節(jié)的標(biāo)注，直到你能看到所有有效的標(biāo)注。我們將采用這種合并數(shù)據(jù)的方式，只顯示出來旅館的個(gè)數(shù)，而不在地圖上顯示出所有的旅館信息。　　最終呈現(xiàn)的標(biāo)注是一個(gè)中心顯示旅館個(gè)數(shù)的小圓圈。實(shí)現(xiàn)的原理跟如何把圖片縮小的原理差不多。我們先在地圖上畫一個(gè)格子。每個(gè)格子中包含了很多個(gè)小單元格，每個(gè)小單元格中的所有旅館數(shù)據(jù)合并出一個(gè)標(biāo)注。然后通過每個(gè)小單元格中所有旅館的坐標(biāo)值的平均值來決定合并后這個(gè)標(biāo)注的坐標(biāo)值。