，所以我們用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）來顯示搜索結果數據中的一部分數據。地圖放的越大，就越能清晰的看到更細節的標注，直到你能看到所有有效的標注。我們將采用這種合并數據的方式，只顯示出來旅館的個數，而不在地圖上顯示出所有的旅館信息。　　最終呈現的標注是一個中心顯示旅館個數的小圓圈。實現的原理跟如何把圖片縮小的原理差不多。我們先在地圖上畫一個格子。每個格子中包含了很多個小單元格，每個小單元格中的所有旅館數據合并出一個標注。然后通過每個小單元格中所有旅館的坐標值的平均值來決定合并后這個標注的坐標值。