Calculadora de capacidade quadtree
Veja o tamanho de uma quadtree totalmente preenchida em determinada profundidade: a profundidade 3 dá 8 células por lado, 64 folhas, 21 nós internos e 85 nós no total. Use como orçamento de pior caso antes de reservar memória ou escolher um zoom máximo. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
Exemplo resolvido
- Profundidade
- 3
- Fator de ramificação
- 4
- Níveis
- 4
- Células por lado
- 8
- Folhas
- 64
Uma quadtree completa é o índice espacial padrão quando uma região quadrada se divide em quatro filhos congruentes em cada nível. Mundos de colisão de jogos, pirâmides de tiles GIS, grades de sondas de luz e árvores de compressão de imagem compartilham esse esqueleto. Antes de reservar um pool de nós, dimensionar um buffer GPU ou escolher um zoom máximo, você precisa do censo do pior caso: quantas folhas existem na profundidade escolhida e quantos nós existem se cada ramo estiver povoado. Esta calculadora de capacidade de quadtree recebe uma profundidade inteira não negativa d, trata a raiz como profundidade zero e devolve a contagem exata de folhas quatro elevado a d, o total de nós da série geométrica de quatro elevado a d mais um menos um sobre três, o restante de nós internos e as células dois elevado a d em cada lado da grade de folhas.
Como uma quadtree completa cresce com a profundidade
Uma quadtree particiona de forma recursiva um quadrado, ou qualquer caixa bidimensional alinhada aos eixos, em quatro quadrantes congruentes: noroeste, nordeste, sudoeste e sudeste. Em uma árvore completa e perfeitamente equilibrada de profundidade d a raiz ocupa a profundidade zero e cada nó interno tem exatamente quatro filhos, de modo que as folhas formam uma grade regular de dois elevado a d por dois elevado a d.
Por isso a contagem de folhas é exatamente quatro elevado a d: cada nível extra multiplica o número de células por quatro, o fator de ramificação da árvore. O número total de nós é a série geométrica parcial um mais quatro mais dezesseis mais quatro elevado a d, que se fecha em quatro elevado a d mais um menos um, dividido por três. Os nós internos são esse total menos as folhas, ou de forma equivalente quatro elevado a d menos um sobre três.
A profundidade zero é a árvore trivial: uma única raiz que também é a única folha, uma célula de lado. A profundidade um é a raiz mais quatro filhos: cinco nós e quatro folhas. A profundidade dois são vinte e um nós e dezesseis folhas, o primeiro tamanho que muitos sistemas de colisão de fato publicam.
Essas identidades pressupõem uma árvore totalmente povoada. Quadtrees adaptativas que param de subdividir o espaço vazio usam menos nós, então as cifras que esta calculadora devolve são o limite superior estrito contra o qual você deve orçar. Elas não contam ponteiros de vizinho, chaves Morton nem bytes de carga: só a estrutura combinatória, que é exatamente o que você precisa antes de escolher uma profundidade máxima.
Onde um recenseamento de capacidade de quadtree justifica o seu valor
Equipes de gráficos e de engines usam uma calculadora de capacidade de quadtree quando escolhem uma profundidade máxima de subdivisão para uma broad-phase bidimensional, uma hierarquia de sondas de luz ou um clipmap de terreno, porque quatro elevado a d cresce tão rápido que um nível extra costuma ser um salto de quatro vezes em nós residentes.
Pipelines de mapeamento e GIS que cunham tiles slippy-map ou quadkeys no estilo Bing precisam do mesmo censo para dimensionar caches de disco e prefixos de entrega de conteúdo em um zoom dado: a grade de folhas é dois elevado a d por dois elevado a d, a contagem familiar de tiles nesse zoom. Codecs de imagem e streamers de textura que armazenam uma quadtree de blocos usam o total de nós para pré-alocar arenas e para recusar uma profundidade pedida que excederia um orçamento de memória.
Validação falha não consome saldo. Mantenha a profundidade dentro da faixa documentada, fixe as contagens inteiras nos testes e você obtém números de planejamento reproduzíveis para documentos de design, orçamentos de integração contínua e workers de borda, sem montar um laboratório próprio de índices espaciais.
Casos de uso
Orçamentos de pool de nós em jogos e engines
Escolha uma profundidade máxima de broad-phase ou de terreno e leia nodes mais leaves antes de alocar uma arena fixa de nós ou um buffer GPU.
Arenas de quadtree para imagem e textura
Pré-dimensione uma arena de árvore de blocos a partir do total de nós e recuse uma profundidade cujas 4^d folhas estourariam o orçamento de memória.
Perguntas frequentes
Quantas folhas tem uma quadtree de profundidade d?
Uma quadtree completa com a raiz na profundidade 0 tem exatamente 4^d folhas, sobre uma grade 2^d por 2^d. Envie depth como inteiro de 0 a 26.
Como se calcula a contagem máxima de nós?
Os nós são a soma geométrica 1 + 4 + 16 + … + 4^d, que equivale a (4^(d+1) − 1) / 3. Os nós internos são esse total menos as folhas.
Isso conta uma quadtree adaptativa (esparsa)?
Não. A calculadora devolve o limite superior totalmente povoado. Uma árvore esparsa que para de subdividir o espaço vazio usa menos nós; orce contra as cifras da árvore completa.
Por que a profundidade está limitada a 26?
Profundidades maiores perderiam precisão inteira nos números de JavaScript.
Como estimo a memória que uma quadtree vai precisar?
Multiplique o total de nós pelo tamanho de um nó no seu próprio programa. As contagens cobrem só a estrutura da árvore, não ligações entre vizinhos nem os dados de cada nó, então profundidade 3 significa reservar espaço para 85 nós.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
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)Exemplo de requisição
{
"depth": 3
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.quadtree_capacity",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Limites
max_depth | 26 |
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
Contrato de entrada, contagens em forma fechada e teto de profundidade
Exemplo: a profundidade três produz oito células de lado, sessenta e quatro folhas, vinte e um nós internos e oitenta e cinco nós no total, porque um mais quatro mais dezesseis mais sessenta e quatro é oitenta e cinco. Combine a resposta com o seu próprio modelo de memória se cada nó carregar uma carga: multiplique nodes pelo tamanho da sua struct para estimar um pool no pior caso. Envie via POST um corpo JSON com o campo inteiro obrigatório depth, também aceito como d ou max_depth: um número inteiro de zero a vinte e seis inclusive. Campos ausentes, strings vazias, não inteiros, valores negativos e profundidades acima de vinte e seis falham com invalid_input nomeando o campo e não são cobrados. Em caso de sucesso o corpo reitera depth e a constante branching_factor quatro, depois levels igual à profundidade mais um (o número de camadas de nós da raiz até as folhas), cells_per_side igual a dois elevado a d, leaves igual a quatro elevado a d, internal_nodes, nodes e uma string formula curta que reafirma as duas formas fechadas. Este endpoint não aloca uma árvore, não percorre pontos e não emite códigos Morton; só avalia as identidades de capacidade para que você possa planejar antes de construir.
Onde um recenseamento de capacidade de quadtree justifica o seu valor
Como a implementação é parse puro de nível A, cada chamada bem-sucedida custa o preço base publicado US$ 0,002 sem tokens de modelo e sem rede de saída.
Casos de integração
Planejamento de tiles de mapa e zoom GIS
No zoom d a grade de folhas é 2^d por 2^d; use leaves e cells_per_side para dimensionar caches, quadkeys e prefixos CDN.
Perguntas técnicas
Quanto custa a calculadora de capacidade de quadtree?
A ferramenta do navegador é gratuita. Pedidos API usam saldo pré-pago KIT a US$ 0,002 por chamada bem-sucedida; entrada inválida não é cobrada.