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