Calculadora de capacidad quadtree
Vea cuánto ocupa un quadtree completamente poblado a una profundidad dada: la profundidad 3 son 8 celdas por lado, 64 hojas, 21 nodos internos y 85 nodos en total. Úselo como presupuesto en el peor caso antes de reservar memoria o fijar un zoom máximo. Gratis en su navegador.
- Gratis
- Funciona en su navegador
- Sin registro
- Sus datos no salen de su equipo
Ejecutar — gratis
Ejemplo resuelto
- Profundidad
- 3
- Factor de ramificación
- 4
- Niveles
- 4
- Celdas por lado
- 8
- Hojas
- 64
Un quadtree completo es el índice espacial por defecto cuando una región cuadrada se divide en cuatro hijos congruentes en cada nivel. Los mundos de colisión de videojuegos, las pirámides de teselas GIS, las retículas de sondas de luz y los árboles de compresión de imagen comparten ese esqueleto. Antes de reservar un depósito de nodos, dimensionar un búfer GPU o elegir un zoom máximo, usted necesita el censo del peor caso: cuántas hojas hay en la profundidad elegida y cuántos nodos existen si cada rama está poblada. Esta calculadora de capacidad de quadtree toma una profundidad entera no negativa d, trata la raíz como profundidad cero y devuelve el recuento exacto de hojas cuatro elevado a d, el total de nodos de la serie geométrica de cuatro elevado a d más uno menos uno entre tres, el resto de nodos internos y las celdas dos elevado a d a cada lado de la malla de hojas.
Cómo crece un quadtree completo con la profundidad
Un quadtree particiona de forma recursiva un cuadrado, o cualquier caja bidimensional alineada a los ejes, en cuatro cuadrantes congruentes: noroeste, noreste, suroeste y sureste. En un árbol completo y perfectamente equilibrado de profundidad d la raíz ocupa la profundidad cero y cada nodo interno tiene exactamente cuatro hijos, de modo que las hojas forman una malla regular de dos elevado a d por dos elevado a d.
Por eso el recuento de hojas es exactamente cuatro elevado a d: cada nivel extra multiplica el número de celdas por cuatro, el factor de ramificación del árbol. El número total de nodos es la serie geométrica parcial uno más cuatro más dieciséis más cuatro elevado a d, que se cierra en cuatro elevado a d más uno menos uno, dividido entre tres. Los nodos internos son ese total menos las hojas, o de forma equivalente cuatro elevado a d menos uno entre tres.
La profundidad cero es el árbol trivial: una sola raíz que es también la única hoja, una celda de lado. La profundidad uno es la raíz más cuatro hijos: cinco nodos y cuatro hojas. La profundidad dos son veintiún nodos y dieciséis hojas, el primer tamaño que muchos sistemas de colisión llegan a publicar.
Estas identidades suponen un árbol totalmente poblado. Los quadtrees adaptativos que dejan de subdividir el espacio vacío usan menos nodos, así que las cifras que devuelve esta calculadora son la cota superior estricta frente a la que usted debe presupuestar. No cuentan punteros de vecino, claves Morton ni bytes de carga: solo la estructura combinatoria, que es exactamente lo que necesita antes de elegir una profundidad máxima.
Dónde un recuento de capacidad de quadtree justifica su valor
Los equipos de gráficos y de motores usan una calculadora de capacidad de quadtree cuando eligen una profundidad máxima de subdivisión para una fase amplia bidimensional, una jerarquía de sondas de luz o un clipmap de terreno, porque cuatro elevado a d crece tan rápido que un nivel extra suele ser un salto de cuatro veces en nodos residentes.
Las tuberías de cartografía y GIS que acuñan teselas slippy-map o quadkeys al estilo Bing necesitan el mismo censo para dimensionar cachés de disco y prefijos de entrega de contenido en un zoom dado: la malla de hojas es dos elevado a d por dos elevado a d, el recuento de teselas habitual en ese zoom.
Los códecs de imagen y los transmisores de texturas que guardan un quadtree de bloques usan el total de nodos para preasignar arenas y para rechazar una profundidad pedida que rebasaría un presupuesto de memoria. La validación fallida no consume saldo. Mantenga la profundidad dentro del rango documentado, fije los recuentos enteros en las pruebas y obtendrá cifras de planificación reproducibles para documentos de diseño, presupuestos de integración continua y workers de borde, sin montar un laboratorio propio de índices espaciales.
Qué puede hacer con ella
Presupuestos de depósito de nodos en juegos y motores
Elija una profundidad máxima de fase amplia o de terreno y lea nodes más leaves antes de reservar un arena fija de nodos o un búfer GPU.
Arenas de quadtree para imagen y textura
Preasigne un arena de árbol de bloques a partir del total de nodos y rechace una profundidad cuyas 4^d hojas rebasarían el presupuesto de memoria.
Preguntas frecuentes
¿Cuántas hojas tiene un quadtree de profundidad d?
Un quadtree completo con la raíz en la profundidad 0 tiene exactamente 4^d hojas, sobre una malla 2^d por 2^d. Envíe depth como entero de 0 a 26.
¿Cómo se calcula el recuento máximo de nodos?
Los nodos son la suma geométrica 1 + 4 + 16 + … + 4^d, que equivale a (4^(d+1) − 1) / 3. Los nodos internos son ese total menos las hojas.
¿Cuenta esto un quadtree adaptativo (disperso)?
No. La calculadora devuelve la cota superior totalmente poblada. Un árbol disperso que deja de subdividir el espacio vacío usa menos nodos; presupueste frente a las cifras del árbol completo.
¿Por qué la profundidad está limitada a 26?
Profundidades mayores perderían precisión entera en los números de JavaScript.
¿Cómo estimo la memoria que necesitará un quadtree?
Multiplique el total de nodos por lo que ocupa un nodo en su propio programa. Los recuentos cubren solo la estructura del árbol, no los enlaces entre vecinos ni los datos de cada nodo, así que una profundidad de 3 supone prever 85 nodos.
Herramientas relacionadas
Para desarrolladores — acceso por API
Todo lo de esta página está disponible por programación. Esta sección es para equipos que quieren integrarlo en sus sistemas; el resto puede usar la herramienta de arriba sin más.
Endpoint de API
¿Prefiere automatizarlo? Un POST autenticado crea la tarea; el resultado llega por webhook o enlace firmado. La misma capacidad también se ejecuta aquí en la web, por email y desde Telegram — y pronto también desde nuestra app.
Llámela desde su 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)Ejemplo de solicitud
{
"depth": 3
}Ejemplo de respuesta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.quadtree_capacity",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}La API es asíncrona: la llamada devuelve un task_id al instante y el resultado llega por webhook. El polling está limitado a 1 req/s por tarea.
Precio
Precio publicado — sin tokens ni créditos inventados. Una tarea fallida no se cobra.
Límites
max_depth | 26 |
Errores
| HTTP | Código | Significado |
|---|---|---|
401 | unauthorized | API key ausente o inválida. |
402 | insufficient_balance | El saldo no cubre el precio de la tarea. |
404 | unknown_type | El tipo de tarea no existe. |
429 | rate_limited | Demasiadas peticiones. Use el webhook en vez de sondear. |
Notas técnicas
Contrato de entrada, recuentos en forma cerrada y tope de profundidad
Ejemplo: la profundidad tres produce ocho celdas de lado, sesenta y cuatro hojas, veintiún nodos internos y ochenta y cinco nodos en total, porque uno más cuatro más dieciséis más sesenta y cuatro es ochenta y cinco. Combine la respuesta con su propio modelo de memoria si cada nodo lleva una carga: multiplique nodes por el tamaño de su estructura para estimar un depósito en el peor caso. Envíe por POST un cuerpo JSON con el campo entero obligatorio depth, también aceptado como d o max_depth: un número entero de cero a veintiséis inclusive. Los campos ausentes, las cadenas vacías, los no enteros, los valores negativos y las profundidades mayores de veintiséis fallan con invalid_input nombrando el campo y no se facturan. En caso de éxito el cuerpo reitera depth y la constante branching_factor cuatro, luego levels igual a la profundidad más uno (el número de capas de nodos desde la raíz hasta las hojas), cells_per_side igual a dos elevado a d, leaves igual a cuatro elevado a d, internal_nodes, nodes y una cadena formula breve que reafirma las dos formas cerradas. Este endpoint no reserva un árbol, no recorre puntos y no emite códigos Morton; solo evalúa las identidades de capacidad para que usted pueda planificar antes de construir.
Dónde un recuento de capacidad de quadtree justifica su valor
Como la implementación es parse puro de nivel A, cada llamada exitosa cuesta el precio base publicado $0.002 sin tokens de modelo ni red saliente.
Casos de integración
Planificación de teselas de mapa y zoom GIS
En el zoom d la malla de hojas es 2^d por 2^d; use leaves y cells_per_side para dimensionar cachés, quadkeys y prefijos CDN.
Preguntas técnicas
¿Cuánto cuesta la calculadora de capacidad de quadtree?
La herramienta del navegador es gratuita. Las peticiones API usan saldo prepago KIT a $0.002 por llamada exitosa; la entrada no válida no se factura.