ForHosting KIT · Outils pour développeurs

Calculateur de capacité quadtree

Voyez la taille d'un quadtree entièrement peuplé à une profondeur donnée : la profondeur 3 donne 8 cellules par côté, 64 feuilles, 21 nœuds internes et 85 nœuds au total. Servez-vous-en comme budget du pire cas avant de réserver la mémoire. Gratuit dans votre navigateur.

Gratuit
Fonctionne dans votre navigateur
Sans inscription
Vos données restent sur votre appareil

Lancer gratuitement Voir l’API

Utilisez-le depuis WebAPIE-mailTelegramApp bientôt

Exemple résolu

Si vous saisissez

Profondeur: 3

Vous obtenez

Facteur de branchement: 4
Niveaux: 4
Cellules par côté: 8
Feuilles: 64

Un quadtree complet est l'index spatial par défaut lorsqu'une région carrée se scinde en quatre enfants congruents à chaque niveau. Les mondes de collision de jeux, les pyramides de tuiles GIS, les grilles de sondes lumineuses et les arbres de compression d'image partagent ce squelette. Avant d'allouer un vivier de nœuds, de dimensionner un tampon GPU ou de choisir un zoom maximal, vous avez besoin du recensement du pire cas : combien de feuilles siègent à la profondeur choisie, et combien de nœuds existent si chaque branche est peuplée. Ce calculateur de capacité quadtree prend une profondeur entière non négative d, traite la racine comme profondeur zéro et renvoie le nombre exact de feuilles quatre puissance d, le total de nœuds de la série géométrique de quatre puissance d plus un moins un sur trois, le reste de nœuds internes et les cellules deux puissance d de chaque côté de la grille de feuilles.

Comment un quadtree complet croît avec la profondeur

Un quadtree partitionne de façon récursive un carré, ou toute boîte bidimensionnelle alignée sur les axes, en quatre quadrants congruents : nord-ouest, nord-est, sud-ouest et sud-est. Dans un arbre complet et parfaitement équilibré de profondeur d, la racine occupe la profondeur zéro et chaque nœud interne a exactement quatre enfants, si bien que les feuilles forment une grille régulière de deux puissance d par deux puissance d.

C'est pourquoi le nombre de feuilles vaut exactement quatre puissance d : chaque niveau supplémentaire multiplie le nombre de cellules par quatre, le facteur de branchement de l'arbre. Le nombre total de nœuds est la série géométrique partielle un plus quatre plus seize plus quatre puissance d, qui se referme sur quatre puissance d plus un moins un, divisé par trois. Les nœuds internes sont ce total moins les feuilles, ou de façon équivalente quatre puissance d moins un sur trois.

La profondeur zéro est l'arbre trivial : une seule racine qui est aussi l'unique feuille, une cellule de côté. La profondeur un est la racine plus quatre enfants : cinq nœuds et quatre feuilles. La profondeur deux fait vingt et un nœuds et seize feuilles, la première taille que beaucoup de systèmes de collision livrent réellement.

Ces identités supposent un arbre entièrement peuplé. Les quadtrees adaptatifs qui cessent de subdiviser l'espace vide utilisent moins de nœuds, donc les chiffres renvoyés par ce calculateur sont la borne supérieure stricte contre laquelle vous devez budgéter. Ils ne comptent ni pointeurs de voisin, ni clés Morton, ni octets de charge : seulement la structure combinatoire, précisément ce dont vous avez besoin avant de choisir une profondeur maximale.

Où un chiffre de capacité quadtree justifie son existence

Les équipes graphiques et moteur utilisent un calculateur de capacité quadtree lorsqu'elles choisissent une profondeur maximale de subdivision pour une large phase bidimensionnelle, une hiérarchie de sondes lumineuses ou un clipmap de terrain, parce que quatre puissance d croît si vite qu'un niveau de plus est souvent un saut de quatre fois en nœuds résidents.

Les pipelines cartographiques et GIS qui frappent des tuiles slippy-map ou des quadkeys à la Bing ont besoin du même recensement pour dimensionner caches disque et préfixes de livraison de contenu à un zoom donné : la grille de feuilles est deux puissance d par deux puissance d, le décompte de tuiles habituel à ce zoom. Les codecs d'image et les diffuseurs de textures qui stockent un quadtree de blocs utilisent le total de nœuds pour préallouer des arènes et pour refuser une profondeur demandée qui dépasserait un budget mémoire.

Un échec de validation ne consomme pas le solde. Gardez la profondeur dans la plage documentée, figez les décomptes entiers dans les tests, et vous obtenez des chiffres de planification reproductibles pour documents de conception, budgets d'intégration continue et workers de bord, sans dresser votre propre bac à sable d'index spatial.

Cas d’usage

Budgets de vivier de nœuds pour jeux et moteurs

Choisissez une profondeur maximale de large phase ou de terrain et lisez nodes plus leaves avant d'allouer une arène fixe de nœuds ou un tampon GPU.

Arènes de quadtree pour image et texture

Prédimensionnez une arène d'arbre de blocs à partir du total de nœuds, et refusez une profondeur dont les 4^d feuilles feraient sauter le budget mémoire.

Questions fréquentes

Combien de feuilles possède un quadtree de profondeur d ?

Un quadtree complet dont la racine est à la profondeur 0 a exactement 4^d feuilles, sur une grille 2^d par 2^d. Envoyez depth comme entier de 0 à 26.

Comment calcule-t-on le nombre maximal de nœuds ?

Les nœuds sont la somme géométrique 1 + 4 + 16 + … + 4^d, égale à (4^(d+1) − 1) / 3. Les nœuds internes sont ce total moins les feuilles.

Cela compte-t-il un quadtree adaptatif (creux) ?

Non. Le calculateur renvoie la borne supérieure entièrement peuplée. Un arbre creux qui cesse de subdiviser l'espace vide utilise moins de nœuds ; budgétez contre les chiffres de l'arbre complet.

Pourquoi la profondeur est-elle limitée à 26 ?

Des profondeurs plus grandes perdraient la précision entière dans les nombres JavaScript.

Comment estimer la mémoire dont un quadtree aura besoin ?

Multipliez le nombre total de nœuds par la taille d'un nœud dans votre propre programme. Les comptes ne couvrent que la structure de l'arbre, ni les liens entre voisins ni les données de chaque nœud : une profondeur de 3 impose de prévoir 85 nœuds.

Outils associés

Pour les développeurs — accès API

Tout sur cette page est disponible par programmation. Cette section s'adresse aux équipes qui veulent l'intégrer à leurs systèmes ; les autres peuvent simplement utiliser l'outil ci-dessus.

Endpoint

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

Authentification par jeton Bearer : un seul POST met la tâche en file d’attente, et le résultat vous parvient par webhook ou lien signé.

Appeler depuis votre stack

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)

Exemple de requête

{
  "depth": 3
}

Exemple de réponse

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

L’API est asynchrone : chaque appel renvoie un task_id immédiatement, puis vous interrogez l’état à raison d’une requête par seconde.

Tarifs

par requête$0.002

Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.

Limites

max_depth 26

Erreurs

HTTP	Code	Signification
`401`	`unauthorized`	Clé API absente ou invalide : vérifiez l’en-tête Authorization.
`402`	`insufficient_balance`	Solde insuffisant : rechargez votre compte pour lancer cette tâche.
`404`	`unknown_type`	Type de tâche inconnu : vérifiez le champ type de votre requête.
`429`	`rate_limited`	Trop de requêtes : ralentissez la cadence, puis réessayez.

Notes techniques

Contrat d'entrée, décomptes en forme close et plafond de profondeur

Exemple : la profondeur trois donne huit cellules de côté, soixante-quatre feuilles, vingt et un nœuds internes et quatre-vingt-cinq nœuds au total, parce que un plus quatre plus seize plus soixante-quatre égale quatre-vingt-cinq. Associez la réponse à votre propre modèle mémoire si chaque nœud porte une charge : multipliez nodes par la taille de votre structure pour estimer un vivier au pire cas. Ce point d'accès n'alloue pas d'arbre, ne parcourt pas de points et n'émet pas de codes Morton ; il n'évalue que les identités de capacité afin que vous puissiez planifier avant de construire. Envoyez par POST un corps JSON avec le champ entier obligatoire depth, aussi accepté comme d ou max_depth : un entier de zéro à vingt-six inclus. Les champs manquants, les chaînes vides, les non-entiers, les valeurs négatives et les profondeurs au-dessus de vingt-six échouent avec invalid_input en nommant le champ et ne sont pas facturés. En cas de succès le corps répète depth et la constante branching_factor quatre, puis levels égal à la profondeur plus un (le nombre de couches de nœuds de la racine aux feuilles), cells_per_side égal à deux puissance d, leaves égal à quatre puissance d, internal_nodes, nodes et une courte chaîne formula qui réaffirme les deux formes closes.

Où un chiffre de capacité quadtree justifie son existence

Parce que l'implémentation est parse pur de palier A, chaque appel réussi coûte le prix de base publié $0.002 sans jetons de modèle ni réseau sortant.

Cas d'intégration

Planification des tuiles carte et du zoom GIS

Au zoom d la grille de feuilles fait 2^d par 2^d ; servez-vous de leaves et de cells_per_side pour dimensionner caches, quadkeys et préfixes CDN.

Questions techniques

Combien coûte le calculateur de capacité quadtree ?

L'outil navigateur est gratuit. Les requêtes API utilisent le solde prépayé KIT à $0.002 par appel réussi ; une entrée invalide n'est pas facturée.

Consulter la documentation complète du KIT →

Lancer gratuitement

Exemple résolu

Comment un quadtree complet croît avec la profondeur

Où un chiffre de capacité quadtree justifie son existence

Cas d’usage

Budgets de vivier de nœuds pour jeux et moteurs

Arènes de quadtree pour image et texture

Questions fréquentes

Outils associés

Pour les développeurs — accès API

Endpoint

Appeler depuis votre stack

Exemple de requête

Exemple de réponse

Tarifs

Limites

Erreurs

Notes techniques

Contrat d'entrée, décomptes en forme close et plafond de profondeur

Où un chiffre de capacité quadtree justifie son existence

Cas d'intégration

Planification des tuiles carte et du zoom GIS

Questions techniques

merci