參考：http://blog.csdn.net/zhouxuguang236/article/details/12312099
原博客地址還有c＋＋源碼。。。
四叉樹索引的基本思想是將地理空間遞歸劃分為不同層次的樹結構。它將已知范圍的空間等分成四個相等的子空間，如此遞歸下去，直至樹的層次達到一定深度或者滿足某種要求后停止分割。四叉樹的結構比較簡單，并且當空間數據對象分布比較均勻時，具有比較高的空間數據插入和查詢效率，因此四叉樹是GIS中常用的空間索引之一。常規四叉樹的結構如圖所示，地理空間對象都存儲在葉子節點上，中間節點以及根節點不存儲地理空間對象。
?
?
四叉樹示意圖
?
四叉樹對于區域查詢，效率比較高。但如果空間對象分布不均勻，隨著地理空間對象的不斷插入，四叉樹的層次會不斷地加深，將形成一棵嚴重不平衡的四叉樹，那么每次查詢的深度將大大的增多，從而導致查詢效率的急劇下降。
?
本節將介紹一種改進的四叉樹索引結構。四叉樹結構是自頂向下逐步劃分的一種樹狀的層次結構。傳統的四叉樹索引存在著以下幾個缺點：
(1)空間實體只能存儲在葉子節點中，中間節點以及根節點不能存儲空間實體信息，隨著空間對象的不斷插入，最終會導致四叉樹樹的層次比較深，在進行空間數據窗口查詢的時候效率會比較低下。
(2)同一個地理實體在四叉樹的分裂過程中極有可能存儲在多個節點中，這樣就導致了索引存儲空間的浪費。
(3)由于地理空間對象可能分布不均衡，這樣會導致常規四叉樹生成一棵極為不平衡的樹，這樣也會造成樹結構的不平衡以及存儲空間的浪費。
相應的改進方法，將地理實體信息存儲在完全包含它的最小矩形節點中，不存儲在它的父節點中，每個地理實體只在樹中存儲一次，避免存儲空間的浪費。首先生成滿四叉樹，避免在地理實體插入時需要重新分配內存，加快插入的速度，最后將空的節點所占內存空間釋放掉。改進后的四叉樹結構如下圖所示。四叉樹的深度一般取經驗值4-7之間為最佳。
?
圖改進的四叉樹結構
?
為了維護空間索引與對存儲在文件或數據庫中的空間數據的一致性，作者設計了如下的數據結構支持四叉樹的操作。
(1)四分區域標識
分別定義了一個平面區域的四個子區域索引號，右上為第一象限0，左上為第二象限1，左下為第三象限2，右下為第四象限3。
typedef enum
{
??????UR = 0,// UR第一象限
??????UL = 1,?// UL為第二象限
??????LL = 2,?// LL為第三象限
??????LR = 3??// LR為第四象限
}QuadrantEnum;
(2)空間對象數據結構
空間對象數據結構是對地理空間對象的近似，在空間索引中，相當一部分都是采用MBR作為近似。
/*空間對象MBR信息*/
typedef struct SHPMBRInfo
{
??????int nID;???????//空間對象ID號
??????MapRect Box;????//空間對象MBR范圍坐標
}SHPMBRInfo;
nID是空間對象的標識號，Box是空間對象的最小外包矩形（MBR）。
(3)四叉樹節點數據結構
四叉樹節點是四叉樹結構的主要組成部分，主要用于存儲空間對象的標識號和MBR，也是四叉樹算法操作的主要部分。
/*四叉樹節點類型結構*/
typedef struct QuadNode
{
??????MapRect????????????Box;???????????????????//節點所代表的矩形區域
??????int????????????????nShpCount;????????//節點所包含的所有空間對象個數
??????SHPMBRInfo* pShapeObj;??????????//空間對象指針數組
??????int?????????nChildCount;????????????//子節點個數
??????QuadNode?*children[4];?????????????//指向節點的四個孩子
}QuadNode;
Box是代表四叉樹對應區域的最小外包矩形，上一層的節點的最小外包矩形包含下一層最小外包矩形區域；nShpCount代表本節點包含的空間對象的個數；pShapeObj代表指向空間對象存儲地址的首地址，同一個節點的空間對象在內存中連續存儲；nChildCount代表節點擁有的子節點的數目；children是指向孩子節點指針的數組。
?
?參考：http://blog.csdn.net/zhouxuguang236/article/details/12312099
四叉樹原理
四叉樹是種很直接的空間索引技術。在四叉樹中，每個節點表示覆蓋了部分進行索引的空間的邊界框，根節點覆蓋了整個區域。每個節點要么是葉節點，有包含一個或多個索引點的列表，沒有孩子。要么是內部節點，有四個孩子，每個孩子對應將區域沿兩根軸對半分得到的四個象限中的一個，四叉樹也因此得名。
圖1??? 展示四叉樹是怎樣劃分索引區域的 來源：維基百科
將數據插入四叉樹很簡單：從根節點開始，判斷你的數據點屬于哪個象限。遞歸到相應的節點，重復步驟，直到到達葉節點，然后將該點加入節點的索引點列表中。如果列表中的元素個數超出了預設的最大數目，則將節點分裂，將其中的索引點移動到相應的子節點中去。
圖2??? 四叉樹的內部結構
查詢四叉樹時從根節點開始，檢查每個子節點看是否與查詢的區域相交。如果是，則遞歸進入該子節點。當到達葉節點時，檢查點列表中的每一個項看是否與查詢區域相交，如果是則返回此項。
注意四叉樹是非常規則的，事實上它是一種字典樹，因為樹節點的值不依賴于插入的數據。因此我們可以用直接的方式給節點編號：用二進制給每個象限編號（左上是00，右上是10等等?譯者注：第一個比特位為0表示在左半平面，為1在右半平面。第二個比特位為0表示在上半平面，為1在下半平面），任一節點的編號是由從根開始，它的各祖先的象限號碼串接而成的。在這個編號系統中，圖2中右下角節點的編號是1101。
如果我們定義了樹的最大深度，不需通過樹就可以計算數據點所在節點的編號：只要把節點的坐標標準化到適當的整數區間中（比如32位整數），然后把轉化后x, y坐標的比特位交錯組合。每對比特指定了假想的四叉樹中的一個象限。
?
?
如何在iOS地圖上高效的顯示大量數據
參考：http://blog.163.com/l1_jun/blog/static/143863882013111651737708/
