作成者Observable

外観

d3-quadtree ​

四分木は、2次元空間を再帰的に正方形に分割し、各正方形を4つの等しい大きさの正方形に分割します。各々の異なる点は、一意なリーフノードに存在します。一致する点は、連結リストで表されます。四分木は、多体力の計算のためのBarnes–Hut近似、衝突検出、近傍点の検索など、様々な空間演算を高速化できます。

quadtree(data, x, y) ​

ソースコード · 空の範囲とデフォルトのxおよびyアクセッサを使用して、新しい空の四分木を作成します。dataが指定されている場合、指定された反復可能なデータを四分木に追加します。

js
const tree = d3.quadtree(data);

これは次のものと同等です。

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

xとyも指定されている場合、指定された反復可能なデータを四分木に追加する前に、xおよびyアクセッサを指定された関数に設定します。これは次のものと同等です。

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

quadtree.x(x) ​

ソースコード · xが指定されている場合、現在のx座標アクセッサを設定し、四分木を返します。

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

xアクセッサは、ツリーへの追加とツリーからの削除時にデータのx座標を取得するために使用されます。また、検索時に、以前にツリーに追加されたデータの座標に再アクセスするためにも使用されます。したがって、xアクセッサとyアクセッサは一貫性があり、同じ入力に対して同じ値を返す必要があります。

xが指定されていない場合、現在のxアクセッサを返します。

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

xアクセッサのデフォルトは次のとおりです。

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

quadtree.y(y) ​

ソースコード · yが指定されている場合、現在のy座標アクセッサを設定し、四分木を返します。

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

yアクセッサは、ツリーへの追加とツリーからの削除時にデータのy座標を取得するために使用されます。また、検索時に、以前にツリーに追加されたデータの座標に再アクセスするためにも使用されます。したがって、xアクセッサとyアクセッサは一貫性があり、同じ入力に対して同じ値を返す必要があります。

yが指定されていない場合、現在のyアクセッサを返します。

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

yアクセッサのデフォルトは次のとおりです。

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

quadtree.extent(extent) ​

ソースコード · extentが指定されている場合、指定された点[[x0, y0], [x1, y1]]をカバーするように四分木を拡張し、四分木を返します。

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

extentが指定されていない場合、四分木の現在の範囲[[x0, y0], [x1, y1]]を返します。ここで、x0とy0は包含される下限、x1とy1は包含される上限です。四分木に範囲がない場合は、undefinedを返します。

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

範囲は、quadtree.coverまたはquadtree.addを呼び出すことによっても拡張できます。

quadtree.cover(x, y) ​

ソースコード · 指定された点⟨x,y⟩をカバーするように四分木を拡張し、四分木を返します。

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

四分木の範囲が既に指定された点をカバーしている場合、このメソッドは何もしません。四分木に範囲がある場合、指定された点をカバーするように範囲は繰り返し2倍にされます。ルートノードを必要に応じてラップします。四分木が空の場合、範囲は[[⌊x⌋, ⌊y⌋], [⌈x⌉, ⌈y⌉]]に初期化されます。(丸めは、範囲が後で2倍になった場合、既存の象限の境界が浮動小数点誤差のために変化しないようにするために必要です。)

quadtree.add(datum) ​

ソースコード · 指定されたdatumを四分木に追加し、現在のxおよびyアクセッサを使用して座標⟨x,y⟩を取得し、四分木を返します。

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

新しい点が四分木の現在の範囲の外側にある場合、新しい点をカバーするように四分木は自動的に拡張されます。

quadtree.addAll(data) ​

ソースコード · 指定された反復可能なdataを四分木に追加し、各要素の座標⟨x,y⟩を現在のxおよびyアクセッサを使用して取得し、この四分木を返します。

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

これは、quadtree.addを繰り返し呼び出すこととほぼ同等です。

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

ただし、このメソッドでは、最初にdataの範囲を計算してからデータを追加するため、よりコンパクトな四分木になります。

quadtree.remove(datum) ​

ソースコード · 指定されたdatumを四分木から削除し、現在のxおよびyアクセッサを使用して座標⟨x,y⟩を取得し、四分木を返します。

js
tree.remove(data[0]);

指定されたdatumがこの四分木に存在しない場合（datumとの厳密な等号で判定され、計算された位置とは無関係）、このメソッドは何もしません。

quadtree.removeAll(data) ​

ソースコード · 指定されたdataを四分木から削除し、それらの座標⟨x,y⟩を現在のxおよびyアクセッサを使用して取得し、四分木を返します。

js
tree.removeAll(data);

指定されたdatumがこの四分木に存在しない場合（datumとの厳密な等号で判定され、計算された位置とは無関係）、無視されます。

quadtree.copy() ​

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

ソースコード · 四分木の複製を返します。返された四分木のすべてのノードは、四分木の対応するノードの同一の複製です。ただし、四分木のデータは参照によって共有され、複製されません。

quadtree.root() ​

ソースコード · 四分木のルートノードを返します。

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

quadtree.data() ​

ソースコード · 四分木内のすべてのデータの配列を返します。

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

quadtree.size() ​

ソースコード · クアドツリー内のデータの総数を返します。

js
tree.size() // 2

quadtree.find(x, y, radius) ​

ソースコード · 指定された検索radius（半径）を用いて、位置⟨x,y⟩に最も近いデータムを返します。radiusが指定されていない場合、無限大になります。

js
tree.find(0.000, 0.000) //

検索範囲内にデータムがない場合は、undefinedを返します。

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

quadtree.visit(callback) ​

ソースコード · 前順走査でクアドツリー内の各ノードを巡回し、指定されたcallbackを各ノードに対して引数node、x0、y0、x1、y1で呼び出します。ここで、nodeは巡回中のノード、⟨x0, y0⟩はノードの下限、⟨x1, y1⟩は上限です。クアドツリーを返します。（通常、CanvasやSVGのように正のxが右、正のyが下を向いていると仮定すると、⟨x0, y0⟩は左上の角、⟨x1, y1⟩は右下の角になります。ただし、座標系は任意なので、より正式にはx0 <= x1かつy0 <= y1です。）

特定のノードに対してcallbackがtrueを返す場合、そのノードの子ノードは巡回されません。それ以外の場合は、すべての子ノードが巡回されます。Barnes–Hut近似を使用する場合など、ツリーの一部のみをすばやく巡回するために使用できます。ただし、子クアドラントは常に兄弟順（左上、右上、左下、右下）で巡回されます。検索などでは、特定の順序で兄弟を巡回する方が高速になる場合があります。

例として、以下はクアドツリーを巡回し、矩形範囲[xmin, ymin, xmax, ymax]内のすべてのノードを返し、そのようなノードを含まない可能性のあるクアドを無視します。

js
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⟩は上限です。クアドツリーを返します。（通常、CanvasやSVGのように正のxが右、正のyが下を向いていると仮定すると、⟨x0, y0⟩は左上の角、⟨x1, y1⟩は右下の角になります。ただし、座標系は任意なので、より正式にはx0 <= x1かつy0 <= y1です。）rootを返します。

クアドツリーノード ​

クアドツリーの内部ノードは、左から右、上から下に疎な4要素配列として表されます。

  • 0 - 左上のクアドラント（存在する場合）。
  • 1 - 右上のクアドラント（存在する場合）。
  • 2 - 左下のクアドラント（存在する場合）。
  • 3 - 右下のクアドラント（存在する場合）。

空の場合は、子クアドラントが未定義になる場合があります。

リーフノードは、以下のプロパティを持つオブジェクトとして表されます。

  • data - この点に関連付けられたデータ（quadtree.addに渡されたもの）。
  • next - このリーフ内の次のデータム（存在する場合）。

lengthプロパティを使用して、リーフノードと内部ノードを区別できます。リーフノードの場合は未定義で、内部ノードの場合は4です。たとえば、リーフノード内のすべてのデータを反復処理するには

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

点がクアドツリー内にある間は、点のx座標とy座標を変更しないでください。点の位置を更新するには、削除してから、新しい位置にクアドツリーに追加します。または、既存のクアドツリーを完全に破棄して、最初から新しいクアドツリーを作成することもできます。多くの点が移動している場合は、この方が効率的です。