ForHosting KIT · 開発者向けツール

Quadtree容量計算

Q: 適応的（疎）なQuadtreeも数えますか？

数えません。 本計算は完全に埋まった上限を返します。空領域の再分割を止める疎な木はノードが少ないので、完全木の数字に対して予算を組んでください。

すべての枝が埋まったQuadtreeが、ある深さでどれだけの大きさになるかが分かります。深さ3なら1辺8セル、葉64、内部ノード21、合計85ノードです。ノード用のメモリや最大ズームを決める前の、最悪の場合の見積もりに使えます。ブラウザで無料で使えます。

無料
ブラウザで動作
登録不要
データは端末の外に出ません

無料で実行 API仕様を見る

ご利用方法ウェブAPIメールTelegramアプリ近日

計算例

入力した場合

深さ: 3

結果

分岐係数: 4
レベル: 4
1辺あたりのセル数: 8
葉: 64

完全なQuadtreeは、正方形領域を各段で合同な4子に分割するときの標準的な空間索引です。ゲームの衝突世界、GISタイルピラミッド、ライトプローブ格子、画像圧縮木は、みな同じ骨格を共有します。ノードプールを確保し、GPUバッファを寸法決めし、最大ズームを選ぶ前に、最悪ケースのセンサスが必要です。選んだ深さに葉が何枚あるか、すべての枝が埋まっているときにノードがいくつあるかです。本Quadtree容量計算は、非負の整数深さdを受け取り、根を深さ0とみなし、葉数の4のd乗、幾何級数のノード合計（4のd+1乗マイナス1を3で割った値）、内部ノードの残り、葉格子の各辺の2のd乗セルを返します。

完全なQuadtreeが深さとともに増える仕組み

Quadtreeは正方形、または任意の2次元軸揃え箱を、北西・北東・南西・南東の合同な4象限へ再帰的に分割します。深さdの完全で完全平衡な木では、根が深さ0にあり、すべての内部ノードがちょうど4子を持つため、葉は2のd乗かける2のd乗の規則格子になります。だから葉数はちょうど4のd乗です。

一段深くなるたびにセル数が4倍、つまり木の分岐係数になります。ノード総数は1たす4たす16たす4のd乗という部分幾何級数で、4のd+1乗マイナス1を3で割った値に閉じます。内部ノードはその合計から葉を引いたもので、同等に4のd乗マイナス1を3で割った値です。

深さ0は自明な木で、根が唯一の葉でもあり、一辺1セルです。深さ1は根と4子で、5ノード4葉です。深さ2は21ノード16葉で、多くの衝突系が実際に出荷する最初の規模です。

これらの恒等式は完全に埋まった木を仮定します。空領域の再分割を止める適応Quadtreeはノードが少ないので、本計算が返す数字は予算を組むべき厳密な上限です。最大深さを決める前に必要なのは、まさにそれです。

Quadtree容量の数字が役立つ場面

グラフィックスとエンジンのチームは、2次元ブロードフェーズ、ライトプローブ階層、地形クリップマップの最大分割深さを決めるときにQuadtree容量計算を使います。4のd乗の増え方が速く、一段足すだけで常駐ノードが4倍になりがちだからです。

slippy-mapタイルやBing風quadkeyを発行する地図・GISパイプラインも、指定ズームのディスクキャッシュと配信プレフィックスを寸法決めするために同じセンサスを必要とします。葉格子は2のd乗かける2のd乗で、そのズームのなじみ深いタイル数です。

ブロックのQuadtreeを持つ画像コーデックやテクスチャストリーマは、ノード合計でアリーナを事前確保し、メモリ予算を超える深さ要求を拒否します。検証失敗は残高を消費しません。

深さを文書化範囲に保ち、テストで整数個数を固定すれば、設計文書・継続的インテグレーション予算・エッジワーカー向けに再現可能な計画数字が得られ、自前の空間索引サンドボックスは不要です。

活用例

ゲームとエンジンのノードプール予算

ブロードフェーズまたは地形の最大深さを選び、固定ノードアリーナやGPUバッファを確保する前に nodes と leaves を読んでください。

画像・テクスチャ用Quadtreeアリーナ

ノード合計からブロック木アリーナを事前寸法決めし、4^d 枚の葉がメモリ予算を超える深さは拒否します。

よくある質問

深さ d のQuadtreeの葉は何枚ですか？

根を深さ 0 とする完全なQuadtreeの葉はちょうど 4^d 枚で、格子は 2^d かける 2^d です。depth は 0 から 26 の整数で送ってください。

最大ノード数はどのように求めますか？

ノードは幾何和 1 + 4 + 16 + … + 4^d で、(4^(d+1) − 1) / 3 に等しいです。内部ノードはその合計から葉を引いた値です。

適応的（疎）なQuadtreeも数えますか？

数えません。本計算は完全に埋まった上限を返します。空領域の再分割を止める疎な木はノードが少ないので、完全木の数字に対して予算を組んでください。

Quadtreeに必要なメモリはどう見積もりますか？

ノードの総数に、ご自分のプログラムでの1ノードの大きさを掛けてください。数えるのは木の構造だけで、隣とのつながりや各ノードのデータは含まないため、深さ3なら85ノード分を用意します。

深さが26までに制限されているのはなぜですか？

返すすべての数を、丸めのない正確な整数に保つためです。ノードの数は1段ごとに4倍に増えるので、26を超えると数を正確に表せなくなります。

開発者向け — APIアクセス

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

エンドポイント

POSThttps://api.kit.forhosting.com/dev/quadtree-capacity

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/dev/quadtree-capacity \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"depth":3}'

const res = await fetch("https://api.kit.forhosting.com/dev/quadtree-capacity", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "depth": 3
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/dev/quadtree-capacity",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "depth": 3
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/quadtree-capacity", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"depth":3}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"depth":3}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/quadtree-capacity", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "depth": 3
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "dev.quadtree_capacity",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

料金

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

制限

max_depth 26

エラー

HTTP	コード	意味
`401`	`unauthorized`	APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
`402`	`insufficient_balance`	残高が不足しています。チャージ後に再度お試しください。
`404`	`unknown_type`	指定されたタスクタイプは存在しません。タイプ名を確認してください。
`429`	`rate_limited`	リクエストが多すぎます。しばらく待ってから再度お試しください。

技術的な注記

完全なQuadtreeが深さとともに増える仕組み

近傍ポインタ、Mortonキー、ペイロードバイトは数えず、組合せ構造だけを数えます。

入力契約・閉形式の個数・深さの上限

0から26までの整数です。例：深さ3は一辺8セル、葉64、内部ノード21、合計ノード85です。1+4+16+64が85だからです。構築前の計画のために容量の恒等式だけを評価します。必須の整数フィールド depth を含む JSON を POST してください。別名 d および max_depth も受け付けます。欠落・空文字・非整数・負値・26超は invalid_input でフィールド名を示して失敗し、課金されません。成功時の本文は depth と定数 branching_factor 4 を返し、続けて levels（深さ+1、根から葉までのノード層数）、cells_per_side（2のd乗）、leaves（4のd乗）、internal_nodes、nodes、2つの閉形式を述べる短い formula を含みます。各ノードにペイロードがあるなら、ご自身のメモリモデルと組み合わせ、nodes に構造体サイズを掛けて最悪プールを見積もってください。本エンドポイントは木を確保せず、点を走査せず、Morton符号も出しません。

Quadtree容量の数字が役立つ場面

実装は純parseのティアAのため、成功した各呼び出しはモデルトークンも外向きネットワークもなく、公開の基本料金 $0.002 です。

連携の活用例

地図タイルとGISズームの計画

ズーム d の葉格子は 2^d かける 2^d です。leaves と cells_per_side でキャッシュ、quadkey、CDNプレフィックスを寸法決めします。

技術的な質問

深さが 26 までに制限される理由は何ですか。

深さ 26 では 4^d もノード合計も IEEE-754 の安全整数に収まり、個数はすべて正確です。それより深いと JavaScript の数値で整数精度が失われます。

Quadtree容量計算の料金はいくらですか。

ブラウザツールは無料です。API要求は成功した呼び出しごとに前払いKIT残高から $0.002 です。不正な入力は課金されません。

KITの完全なドキュメントを見る →

Quadtree容量計算

無料で実行

計算例

完全なQuadtreeが深さとともに増える仕組み

Quadtree容量の数字が役立つ場面

活用例

ゲームとエンジンのノードプール予算

画像・テクスチャ用Quadtreeアリーナ

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

お使いのスタックから呼び出す

リクエスト例

レスポンス例

料金

制限

エラー

技術的な注記

完全なQuadtreeが深さとともに増える仕組み

入力契約・閉形式の個数・深さの上限

Quadtree容量の数字が役立つ場面

連携の活用例

地図タイルとGISズームの計画

技術的な質問

ありがとう