Wat is een Quad Tree?

Een quad tree, soms quadtree, Q-boom of QT, is informatica term die verwijst naar een werkwijze voor het ordenen van gegevens in vier kwadranten. Databases gebruiken soms quad bomen te slaan en vinden hun platen. Deze organisatiestructuur werkt bijzonder goed naar een bepaald of pixel in een tweedimensionaal beeld te vinden.

De quad boom enigszins volgt de boom datastructuur vaak gebruikt in de informatica. De normale structuur datastructuur lijkt op een omgekeerde boom, waar een ouder knooppunt boven in de boom heeft een of meer kinderen knooppunten aangesloten. Elk ander knooppunt op de boom heeft één ouder knooppunt en kan een willekeurig aantal kinderen knooppunten, met inbegrip van nul hebben.

In tegenstelling tot een normale boom datastructuur, een quad boomstructuur vereist dat elke interne knoop hebben precies vier kinderen knooppunten. Als illustratie van de meeste quad boomstructuren, zie je een node die vier kinderen heeft knooppunten opknoping van het, met lijnen aansluiten van de bovenliggende node met zijn kinderen knooppunten. De afbeelding kan doorgaan met vier kinderen nodes opknoping uit elk van de oorspronkelijke vier kinderen nodes.

Andere tijden, zal de illustratie van een quad boom een ​​regio of vierkant zijn. Wanneer de regio zijn maximale capaciteit voor gegevensopslag bereikt, wordt het verdeeld in vier kwadranten. Normaal gesproken, de regio's en de kwadranten zijn pleinen, hoewel ze kunnen worden rechthoeken of andere vormen, ook.

Een quad boom is een goede datastructuur voor het organiseren van pixels in een foto en voor het organiseren van computer graphics. Het beeld kan worden onderverdeeld in kwadranten en elk kwadrant kan worden onderverdeeld in vier. Dit kan steeds opnieuw worden herhaald totdat u het niveau van de individuele pixels te bereiken. Als een kwadrant bevat pixels die allemaal dezelfde kleur zijn, maar er is geen reden om het kwadrant verder te verdelen.

Hoewel de gegevens opgeslagen in een quad boomstructuur veel opslagruimte in vergelijking met andere methodes voor gegevens voor computer graphics kan vereisen, quad boomstructuur heeft verscheidene voordelen. Ten eerste kunt u de gehele foto of afbeelding in een enkele stap te verwijderen door de root node, die al zijn kinderen knooppunten ontruimt,. Ten tweede, kunt u snel de resolutie in een foto te verminderen door simpelweg het opruimen van de uiteindelijke niveau van kinderen knooppunten. Dit zal daardoor de hoeveelheid opslagruimte vereist verminderen. Tenslotte vinden van een bepaald gebied van de fotografie voor het manipulatie zocht quad boomstructuur.

Quad bomen worden in enkele andere gevallen, ook inclusief ruimtelijke indexering. Hoewel quad bomen beperkt tot tweedimensionale beelden, die een driedimensionaal beeld kan een soortgelijke structuur volgen, genoemd octree, dat de onderverdeling van een kubus in acht kinderen.