> [Wiki](Home) ? [[API--中文手冊]] ? [[幾何]] ? **四叉樹** * 如發現翻譯不當或有其他問題可以通過以下方式聯系譯者: * 郵箱：zhang_tianxu@sina.com * QQ群：[D3數據可視化](http://jq.qq.com/?_wv=1027&k=ZGcqYF)205076374，[大數據可視化](http://jq.qq.com/?_wv=1027&k=S8wGMe)436442115 四叉樹是一個二維空間遞歸細分。它使用了平分劃分實現，將每一個塊平分成了四個同等大小的方塊。每個點存在于一個唯一的節點中；如果同一位置包含多個點，那么這多個點中的其中一些點將存儲于內部節點，而非葉子結點。四叉樹可用于加速各種空間操作，例如計算正多邊形的體積的Barnes-Hut近似算法或者沖突檢驗。 # d3.geom.quadtree() 創建一個新的四叉樹工廠使用默認的x訪問器，y訪問器及范圍。返回的函數可以用來從帶有工廠的配置的數據創建任意個四叉樹。 # quadtree(points) 為指定的點數據數組構造一個新的四叉樹，返回新四叉樹的根結點。每一個點的X和Y坐標使用當前x及y訪問器函數確定。通過增量地添加點來建立四叉樹，指定的點數組可以為空，之后點可以隨后添加到返回的根節點；在這種情況下，你必須指定四叉樹的范圍。 四叉樹的每一個結點都有多個屬性。 nodes——按順序排列四個子結點的稀疏數組：top-left, top-right, bottom-left, bottom-right。 leaf ——內部結點與葉子結點的布爾表示。 point ——這個點關聯的節點，如果有的話（可能適用于內部或葉節點）。 X——關聯點的x坐標，如果有的話。 Y——關聯點的y坐標，如果有的話。 返回的根結點也可定義了增加方法add 或者訪問方法visit 。 # root.add(point) 為四叉樹增加指定的新點。 # root.visit(callback) 訪問四叉樹的每個結點，利用參數 {node, x1,y1, x2, y2} 為每個結點調用指定的回調函數，結點按先序遍歷。若調用給定結點的回調函數返回值為真，則表示不能訪問此結點的子結點，否則表示所有子結點均能被訪問。 # quadtree.x([x]) 若設置了x參數，則為四叉樹設置橫坐標訪問器，并返回四叉樹。反之，則返回當前默認的橫坐標訪問器。 function(d) { return d[0]; } 對每一個加入到四叉樹中的點，不管是初始化構造的還是后面新增的，都可以通過參數 {d, i}調用x訪問器，d表示當前點，i表示所有點數組的索引。X訪問器必須返回一個數值，表明給定點的x坐標。如果需要得花，x訪問器也可以被定義為一個常數，而非一個函數。 # quadtree.y([y]) 若設置了y參數，則為四叉樹設置縱坐標訪問器，并返回四叉樹。反之，則返回當前默認的縱坐標訪問器 function(d) { return d[1]; } 對每一個加入到四叉樹中的點，不管是初始化構造的還是后面新增的，都可以通過參數 {d, i}調用y訪問器，d表示當前點，i表示所有點數組的索引。y訪問器必須返回一個數值，表明給定點的y坐標。如果需要得花，y訪問器也可以被定義為一個常數，而非一個函數。 # quadtree.extent([extent]) 若設置了extent參數，則為四叉樹設置范圍，然后返回四叉樹。反之，則返回當前范圍，其默認為空。 當范圍為空時，范圍將會自動掃描輸入點數組自動計算并傳到四叉樹構造器。否則，范圍必須用二維數組[[x0, y0], [x1,y1]]明確定義，x0和y0為范圍的下限，x1和y1為范圍的上限。當從最初為空的節點慢慢構建一個四叉樹，設置范圍是非常必要的。 曼妙征程譯20141127咕嚕校對2014-12-8 20:24:31