Quadtree-Kapazitätsrechner

Ein vollständiger Quadtree ist der Standard-Raumindex, wenn eine quadratische Region auf jeder Ebene in vier kongruente Kinder zerlegt wird. Kollisionswelten von Spielen, GIS-Kachelpyramiden, Lichtproben-Gitter und Bildkompressionsbäume teilen dieses Gerüst. Bevor Sie einen Knotenpool anlegen, einen GPU-Puffer dimensionieren oder einen Maximalzoom wählen, brauchen Sie die Worst-Case-Zählung: wie viele Blätter auf der gewählten Tiefe sitzen und wie viele Knoten existieren, wenn jeder Zweig besetzt ist. Dieser Quadtree-Kapazitätsrechner nimmt eine nichtnegative ganzzahlige Tiefe d, behandelt die Wurzel als Tiefe null und liefert die exakte Blattzahl vier hoch d, die Knotensumme der geometrischen Reihe von vier hoch d plus eins minus eins durch drei, den Rest innerer Knoten und die Zellen zwei hoch d an jeder Seite des Blattgitters.

Wie ein vollständiger Quadtree mit der Tiefe wächst

Ein Quadtree zerlegt rekursiv ein Quadrat oder jede zweidimensionale achsenausgerichtete Box in vier kongruente Quadranten: Nordwest, Nordost, Südwest und Südost. In einem vollständigen, perfekt ausgewogenen Baum der Tiefe d sitzt die Wurzel auf Tiefe null und jeder innere Knoten hat genau vier Kinder, sodass die Blätter ein regelmäßiges Gitter von zwei hoch d mal zwei hoch d bilden. Deshalb ist die Blattzahl genau vier hoch d: jede weitere Ebene vervierfacht die Zellenzahl, den Verzweigungsfaktor des Baums.

Die Gesamtzahl der Knoten ist die partielle geometrische Reihe eins plus vier plus sechzehn plus vier hoch d, die sich zu vier hoch d plus eins minus eins, geteilt durch drei, schließt. Innere Knoten sind diese Summe minus die Blätter, gleichwertig vier hoch d minus eins durch drei. Tiefe null ist der triviale Baum: eine einzige Wurzel, die zugleich das einzige Blatt ist, eine Zelle pro Seite.

Tiefe eins ist die Wurzel plus vier Kinder: fünf Knoten und vier Blätter. Tiefe zwei sind einundzwanzig Knoten und sechzehn Blätter, die erste Größe, die viele Kollisionssysteme tatsächlich ausliefern. Diese Identitäten setzen einen vollständig besetzten Baum voraus.

Adaptive Quadtrees, die leeren Raum nicht weiter unterteilen, nutzen weniger Knoten; die Zahlen dieses Rechners sind daher die strikte Obergrenze, gegen die Sie budgetieren sollten. Sie zählen keine Nachbarzeiger, Morton-Schlüssel oder Nutzlastbytes — nur die kombinatorische Struktur, genau das, was Sie brauchen, bevor Sie eine maximale Tiefe wählen.

Wo eine Quadtree-Kapazitätszahl ihren Nutzen zeigt

Grafik- und Engineteams nutzen einen Quadtree-Kapazitätsrechner, wenn sie eine maximale Unterteilungstiefe für eine zweidimensionale Broad-Phase, eine Lichtproben-Hierarchie oder eine Gelände-Clipmap wählen, weil vier hoch d so schnell wächst, dass eine Extraebene oft ein Vierfachsprung bei residenten Knoten ist. Kartografie- und GIS-Pipelines, die Slippy-Map-Kacheln oder Quadkeys im Bing-Stil prägen, brauchen dieselbe Zählung, um Festplatten-Caches und Content-Delivery-Präfixe bei einem gegebenen Zoom zu dimensionieren: das Blattgitter ist zwei hoch d mal zwei hoch d, die vertraute Kachelzahl auf diesem Zoom.

Bildcodecs und Textur-Streamer, die einen Block-Quadtree speichern, nutzen die Knotensumme, um Arenen vorab anzulegen und eine angeforderte Tiefe abzulehnen, die ein Speicherbudget sprengen würde. Fehlgeschlagene Validierung wird nicht berechnet. Halten Sie die Tiefe im dokumentierten Bereich, fixieren Sie die ganzzahligen Zählungen in Tests, und Sie erhalten reproduzierbare Planungszahlen für Entwurfsdokumente, Continuous-Integration-Budgets und Edge-Worker, ohne eine eigene Raumindex-Sandbox aufzubauen.