d3-quadtree

Fork ↗︎

一個 四叉樹 會遞迴地將二維空間分割成正方形，並將每個正方形分割成四個大小相等的正方形。每個不同的點都存在於一個唯一的葉子 節點 中；重合的點會以連結串列表示。四叉樹可以加速各種空間運算，例如用於計算多體力的 巴恩斯-哈特近似法、碰撞偵測和搜尋附近點。

quadtree(data, x, y)

原始碼 · 建立一個新的、空的四叉樹，其 範圍 為空，且 x 和 y 存取器為預設值。如果指定了 data，則將指定的資料可迭代物件 新增 到四叉樹中。

const tree = d3.quadtree(data);

這等於

const tree = d3.quadtree().addAll(data);

如果 x 和 y 也已指定，則在將指定的可迭代資料新增至四叉樹之前，將 x 和 y 存取器設定為指定的函數，等於

const tree = d3.quadtree().x(x).y(y).addAll(data);

quadtree.x(x)

原始碼 · 如果已指定 x，則設定目前的 x 座標存取器並傳回四叉樹。

const tree = d3.quadtree().x((d) => d.x);

x 存取器用於在 新增 至樹狀結構和從樹狀結構中 移除 時，衍生資料的 x 座標。在 尋找 時也會使用，以重新存取先前新增至樹狀結構的資料座標；因此，x 和 y 存取器必須一致，給定相同的輸入時傳回相同的值。

如果未指定 x，則傳回目前的 x 存取器。

tree.x() // (d) => d.x

x 存取器的預設值為

function x(d) {
  return d[0];
}

quadtree.y(y)

原始碼 · 如果已指定 y，則設定目前的 y 座標存取器並傳回四叉樹。

const tree = d3.quadtree().y((d) => d.y);

y 存取器用於在 新增 至樹狀結構和從樹狀結構中 移除 時，衍生資料的 y 座標。在 尋找 時也會使用，以重新存取先前新增至樹狀結構的資料座標；因此，x 和 y 存取器必須一致，給定相同的輸入時傳回相同的值。

如果未指定 y，則傳回目前的 y 存取器。

tree.y() // (d) => d.y

y 存取器的預設值為

function y(d) {
  return d[1];
}

quadtree.extent(extent)

原始碼 · 如果已指定 extent，則將四叉樹擴充為 覆蓋 指定的點 [[x0, y0], [x1, y1]]，並傳回四叉樹。

const tree = d3.quadtree().extent([[0, 0], [1, 1]]);

如果未指定 extent，則傳回四叉樹目前的範圍 [[x0, y0], [x1, y1]]，其中 x0 和 y0 為包含的下限，x1 和 y1 為包含的上限，或者如果四叉樹沒有範圍，則傳回未定義。

tree.extent() // [[0, 0], [2, 2]]

範圍也可以透過呼叫 quadtree.cover 或 quadtree.add 來擴展。

quadtree.cover(x, y)

原始碼 · 擴展四叉樹以涵蓋指定的點 ⟨x,y⟩，並傳回四叉樹。

const tree = d3.quadtree().cover(0, 0).cover(1, 1);

如果四叉樹的範圍已經涵蓋指定的點，此方法不會執行任何動作。如果四叉樹有範圍，範圍會重複加倍以涵蓋指定的點，必要時會包裝 根 節點；如果四叉樹是空的，範圍會初始化為範圍 [[⌊x⌋, ⌊y⌋], [⌈x⌉, ⌈y⌉]]。（必須進行捨入，以便如果範圍稍後加倍，現有象限的邊界不會因為浮點數錯誤而改變。）

quadtree.add(datum)

原始碼 · 將指定的 datum 加入四叉樹，使用目前的 x 和 y 存取器來推導其座標 ⟨x,y⟩，並傳回四叉樹。

const tree = d3.quadtree().add([0, 0]);

如果新點在四叉樹目前的 範圍 外，四叉樹會自動擴展為 涵蓋 新點。

quadtree.addAll(data)

原始碼 · 將指定的 data 可迭代物件加入四叉樹，使用目前的 x 和 y 存取器來推導每個元素的座標 ⟨x,y⟩，並傳回此四叉樹。

const tree = d3.quadtree().addAll([[0, 0], [1, 2]]);

這大約等於重複呼叫 quadtree.add

for (let i = 0, n = data.length; i < n; ++i) {
  quadtree.add(data[i]);
}

不過，此方法會產生一個更緊湊的四叉樹，因為會先計算 data 的範圍，然後再加入資料。

quadtree.remove(datum)

原始碼 · 從四叉樹中移除指定的 datum，使用目前的 x 和 y 存取器來推導其座標 ⟨x,y⟩，並傳回四叉樹。

tree.remove(data[0]);

如果指定的 datum 不存在於此四叉樹中（由與 datum 的嚴格相等性決定，且與計算出的位置無關），此方法不會執行任何動作。

quadtree.removeAll(data)

原始碼 · 從四叉樹中移除指定的 data，使用目前的 x 和 y 存取器來推導其座標 ⟨x,y⟩，並傳回四叉樹。

tree.removeAll(data);

如果指定的資料不存在於此四叉樹中（由與 datum 的嚴格相等性決定，且與計算出的位置無關），將會忽略它。

quadtree.copy()

const t1 = d3.quadtree(data);
const t2 = t1.copy();

原始碼 · 傳回 quadtree 的副本。傳回 quadtree 中的所有 節點 都是 quadtree 中對應節點的相同副本；然而，quadtree 中的任何資料都是透過參照共用，而非複製。

quadtree.root()

原始碼 · 傳回 quadtree 的根 節點。

tree.root() // [{…}, empty × 2, {…}]

quadtree.data()

原始碼 · 傳回 quadtree 中所有資料的陣列。

tree.data() // [[0, 0], [1, 2]]

quadtree.size()

原始碼 · 傳回 quadtree 中資料的總數。

tree.size() // 2

quadtree.find(x, y, radius)

原始碼 · 傳回最接近位置 ⟨x,y⟩ 的資料，並具有指定的搜尋 radius。如果未指定 radius，則預設為無限大。

tree.find(0.000, 0.000) // 

如果搜尋區域內沒有資料，則傳回未定義。

tree.find(10, 10, 1) // undefined

quadtree.visit(callback)

原始碼 · 以先序遍歷的方式拜訪 quadtree 中的每個 節點，並針對每個節點呼叫指定的 callback，其參數為 node、x0、y0、x1、y1，其中 node 為正在拜訪的節點，⟨x0, y0⟩ 為節點的下限，⟨x1, y1⟩ 為上限，並傳回 quadtree。（假設正 x 為右方，正 y 為下方，這通常是 Canvas 和 SVG 的情況，⟨x0, y0⟩ 為左上角，⟨x1, y1⟩ 為右下角；然而，座標系統是任意的，因此更正式地說，x0 <= x1 且 y0 <= y1。）

如果 callback 對給定的節點傳回 true，則不會拜訪該節點的子節點；否則，會拜訪所有子節點。這可以用於快速拜訪樹狀結構的特定部分，例如使用 Barnes–Hut 近似 時。不過請注意，子象限總是按照兄弟順序拜訪：左上、右上、左下、右下。在 搜尋 等情況下，按照特定順序拜訪兄弟節點可能會更快。

舉例來說，以下會拜訪四叉樹並傳回矩形範圍 [xmin, ymin, xmax, ymax] 內的所有節點，忽略不可能包含任何此類節點的象限

function search(quadtree, xmin, ymin, xmax, ymax) {
  const results = [];
  quadtree.visit((node, x1, y1, x2, y2) => {
    if (!node.length) {
      do {
        let d = node.data;
        if (d[0] >= xmin && d[0] < xmax && d[1] >= ymin && d[1] < ymax) {
          results.push(d);
        }
      } while (node = node.next);
    }
    return x1 >= xmax || y1 >= ymax || x2 < xmin || y2 < ymin;
  });
  return results;
}

quadtree.visitAfter(callback)

來源 · 以後序拜訪方式拜訪四叉樹中的每個 節點，對每個節點呼叫指定的 callback，並提供引數 node、x0、y0、x1、y1，其中 node 是正在拜訪的節點，⟨x0、y0⟩ 是節點的下界，⟨x1、y1⟩ 是上界，並傳回四叉樹。（假設正 x 在右邊，正 y 在下方，這通常是 Canvas 和 SVG 的情況，⟨x0、y0⟩ 是左上角，⟨x1、y1⟩ 是右下角；不過，座標系統是任意的，因此更正式的說法是 x0 <= x1 且 y0 <= y1。）傳回 root。

四叉樹節點

四叉樹的內部節點表示為從左到右、從上到下的稀疏四元素陣列

• 0 - 左上象限（如果有的話）。
• 1 - 右上象限（如果有的話）。
• 2 - 左下象限（如果有的話）。
• 3 - 右下象限（如果有的話）。

如果子象限是空的，則可能是未定義的。

葉節點表示為具有下列屬性的物件

• data - 與此點相關聯的資料，傳遞給 quadtree.add。
• next - 如果有，此葉節點中的下一個資料。

length 屬性可用於區分葉節點和內部節點：對於葉節點，它是未定義的，對於內部節點，它是 4。例如，若要遍歷葉節點中的所有資料

if (!node.length) do console.log(node.data); while (node = node.next);

當點在四叉樹中時，不得修改點的 x 和 y 座標。若要更新點的位置，請移除點，然後重新將其新增到新位置的四叉樹。或者，您可以完全捨棄現有的四叉樹，並從頭開始建立新的四叉樹；如果許多點已移動，這可能會更有效率。