Calcolatore di capacità quadtree
Veda quanto diventa grande un quadtree completamente popolato a una data profondità: la profondità 3 dà 8 celle per lato, 64 foglie, 21 nodi interni e 85 nodi in totale. Lo usi come budget nel caso peggiore prima di riservare memoria o scegliere uno zoom massimo. Gratis nel suo browser.
- Gratis
- Funziona nel suo browser
- Senza registrazione
- I suoi dati restano sul dispositivo
Esegui gratis nel browser
Esempio risolto
- Profondità
- 3
- Fattore di ramificazione
- 4
- Livelli
- 4
- Celle per lato
- 8
- Foglie
- 64
Un quadtree completo è l'indice spaziale predefinito quando una regione quadrata si divide in quattro figli congruenti a ogni livello. I mondi di collisione dei giochi, le piramidi di tessere GIS, le griglie di sonde luminose e gli alberi di compressione delle immagini condividono quello scheletro. Prima di riservare un deposito di nodi, dimensionare un buffer GPU o scegliere uno zoom massimo, Lei ha bisogno del censimento del caso peggiore: quante foglie siedono alla profondità scelta e quanti nodi esistono se ogni ramo è popolato. Questo calcolatore di capacità del quadtree accetta una profondità intera non negativa d, tratta la radice come profondità zero e restituisce il conteggio esatto di foglie quattro elevato a d, il totale di nodi della serie geometrica di quattro elevato a d più uno meno uno su tre, il resto di nodi interni e le celle due elevato a d su ciascun lato della griglia di foglie.
Come un quadtree completo cresce con la profondità
Un quadtree partiziona in modo ricorsivo un quadrato, o qualsiasi scatola bidimensionale allineata agli assi, in quattro quadranti congruenti: nord-ovest, nord-est, sud-ovest e sud-est. In un albero completo e perfettamente bilanciato di profondità d la radice occupa la profondità zero e ogni nodo interno ha esattamente quattro figli, così le foglie formano una griglia regolare di due elevato a d per due elevato a d.
Per questo il conteggio delle foglie è esattamente quattro elevato a d: ogni livello in più moltiplica il numero di celle per quattro, il fattore di ramificazione dell'albero. Il numero totale di nodi è la serie geometrica parziale uno più quattro più sedici più quattro elevato a d, che si chiude in quattro elevato a d più uno meno uno, diviso tre. I nodi interni sono quel totale meno le foglie, o in modo equivalente quattro elevato a d meno uno su tre.
La profondità zero è l'albero banale: una sola radice che è anche l'unica foglia, una cella di lato. La profondità uno è la radice più quattro figli: cinque nodi e quattro foglie. La profondità due sono ventuno nodi e sedici foglie, la prima dimensione che molti sistemi di collisione pubblicano davvero.
Queste identità presuppongono un albero interamente popolato. I quadtree adattivi che smettono di suddividere lo spazio vuoto usano meno nodi, quindi le cifre restituite da questo calcolatore sono il limite superiore stretto rispetto al quale Lei deve preventivare. Non contano puntatori di vicini, chiavi Morton né byte di carico: solo la struttura combinatoria, che è esattamente ciò di cui ha bisogno prima di scegliere una profondità massima.
Dove un dato di capacità del quadtree dimostra il proprio valore
I team di grafica e di motori usano un calcolatore di capacità del quadtree quando scelgono una profondità massima di suddivisione per una broad-phase bidimensionale, una gerarchia di sonde luminose o un clipmap del terreno, perché quattro elevato a d cresce così in fretta che un livello in più è spesso un salto di quattro volte nei nodi residenti.
Le pipeline cartografiche e GIS che coniano tessere slippy-map o quadkey in stile Bing necessitano dello stesso censimento per dimensionare cache su disco e prefissi di consegna dei contenuti a un dato zoom: la griglia di foglie è due elevato a d per due elevato a d, il conteggio familiare di tessere a quello zoom. I codec di immagine e gli streamer di texture che memorizzano un quadtree di blocchi usano il totale di nodi per preallocare arene e per rifiutare una profondità richiesta che supererebbe un budget di memoria.
La convalida fallita non consuma il saldo. Mantenga la profondità nell'intervallo documentato, fissi i conteggi interi nei test e otterrà cifre di pianificazione riproducibili per documenti di progetto, budget di integrazione continua e worker di bordo, senza allestire un laboratorio proprio di indici spaziali.
Casi d'uso
Budget del deposito nodi per giochi e motori
Scelga una profondità massima di broad-phase o di terreno e legga nodes più leaves prima di allocare un'arena fissa di nodi o un buffer GPU.
Arene di quadtree per immagine e texture
Predimensioni un'arena di albero a blocchi dal totale di nodi e rifiuti una profondità le cui 4^d foglie sforerebbero il budget di memoria.
Domande frequenti
Quante foglie ha un quadtree di profondità d?
Un quadtree completo con la radice alla profondità 0 ha esattamente 4^d foglie, su una griglia 2^d per 2^d. Invii depth come intero da 0 a 26.
Come si calcola il conteggio massimo dei nodi?
I nodi sono la somma geometrica 1 + 4 + 16 + … + 4^d, pari a (4^(d+1) − 1) / 3. I nodi interni sono quel totale meno le foglie.
Questo conta un quadtree adattivo (sparso)?
No. Il calcolatore restituisce il limite superiore interamente popolato. Un albero sparso che smette di suddividere lo spazio vuoto usa meno nodi; faccia il budget rispetto alle cifre dell'albero completo.
Perché la profondità è limitata a 26?
Profondità maggiori perderebbero precisione intera nei numeri JavaScript.
Come stimo la memoria che servirà a un quadtree?
Moltiplichi il totale dei nodi per lo spazio occupato da un nodo nel suo programma. I conteggi coprono solo la struttura dell'albero, non i collegamenti tra vicini né i dati di ogni nodo, quindi una profondità di 3 significa prevedere 85 nodi.
Strumenti correlati
Per sviluppatori — accesso via API
Tutto quello che vedi in questa pagina è disponibile anche via API. Questa sezione è per i team che vogliono integrarlo nei propri sistemi; chi non ne ha bisogno può semplicemente usare lo strumento qui sopra.
Endpoint
Autenticazione con Bearer token: un POST mette in coda l'attività e il risultato arriva via webhook o link firmato.
Chiamala dal tuo 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)Esempio di richiesta
{
"depth": 3
}Esempio di risposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.quadtree_capacity",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L'API è asincrona: ricevi subito un task_id e puoi fare polling fino a 1 richiesta al secondo.
Prezzi
Prezzo pubblicato, senza token né crediti. Se l'attività fallisce, non paghi.
Limiti
max_depth | 26 |
Errori
| HTTP | Codice | Significato |
|---|---|---|
401 | unauthorized | Chiave API mancante o non valida: controlla l'header Authorization. |
402 | insufficient_balance | Credito esaurito: ricarica per continuare a eseguire attività. |
404 | unknown_type | Tipo di attività sconosciuto: controlla il campo type della richiesta. |
429 | rate_limited | Troppe richieste in poco tempo: rallenta e riprova tra qualche secondo. |
Note tecniche
Contratto di ingresso, conteggi in forma chiusa e tetto di profondità
Esempio: la profondità tre produce otto celle di lato, sessantaquattro foglie, ventuno nodi interni e ottantacinque nodi in totale, perché uno più quattro più sedici più sessantaquattro fa ottantacinque. Abbini la risposta al proprio modello di memoria se ogni nodo porta un carico: moltiplichi nodes per la dimensione della Sua struct per stimare un deposito nel caso peggiore. Invii tramite POST un corpo JSON con il campo intero obbligatorio depth, accettato anche come d o max_depth: un intero da zero a ventisei incluso. Campi assenti, stringhe vuote, non interi, valori negativi e profondità oltre ventisei falliscono con invalid_input indicando il campo e non vengono fatturati. In caso di successo il corpo ribadisce depth e la costante branching_factor quattro, poi levels pari alla profondità più uno (il numero di strati di nodi dalla radice alle foglie), cells_per_side pari a due elevato a d, leaves pari a quattro elevato a d, internal_nodes, nodes e una breve stringa formula che riafferma le due forme chiuse. Questo endpoint non alloca un albero, non attraversa punti e non emette codici Morton; valuta solo le identità di capacità perché Lei possa pianificare prima di costruire.
Dove un dato di capacità del quadtree dimostra il proprio valore
Poiché l'implementazione è parse puro di livello A, ogni chiamata riuscita costa il prezzo base pubblicato $0.002 senza token di modello né rete in uscita.
Casi di integrazione
Pianificazione delle tessere mappa e dello zoom GIS
Allo zoom d la griglia di foglie è 2^d per 2^d; usi leaves e cells_per_side per dimensionare cache, quadkey e prefissi CDN.
Domande tecniche
Quanto costa il calcolatore di capacità del quadtree?
Lo strumento nel browser è gratuito. Le richieste API usano il saldo prepagato KIT a $0.002 per chiamata riuscita; un input non valido non viene fatturato.