Drzewo czwórkowe
Sign in to savethumb|300px|A point-region quadtree with point data. Bucket capacity 1. thumb|300x300px|Quadtree compression of an image step by step. Left shows the compressed image with the tree bounding boxes while the right shows just the compressed image A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a
In the Vinony graph
Vinony's link graph records 142 inbound references to Drzewo czwórkowe, and connects out to B-tree, tree and binary space partitioning.
It is catalogued under topics including Database index techniques, Geometric data structures and Rectangular subdivisions.
Vinony links it to 15 Wikipedia language editions.
Key facts
- Data structure.name
- Quadtree
- Data structure.type
- Tree
- Data structure.invented_by
- Raphael Finkel and J.L. Bentley
- Data structure.invented_year
- 1974
via Wikipedia infobox
Wikidata facts
- Instance of
- data structure
- Subclass of
- spatial index
- Image
- Point quadtree.svg
Show 2 more facts
- Commons category
- Quadtrees
- maintained by WikiProject
- WikiProject Mathematics
Sources (2)
via Wikidata · CC0
Article · Polski
Drzewo czwórkowe (ang. quadtree) – struktura danych będąca drzewem, używana do podziału dwuwymiarowej przestrzeni na mniejsze części, dzieląc ją na cztery równe ćwiartki, a następnie każdą z tych ćwiartek na cztery kolejne itd. Jest używana na przykład w procesie wykrywania kolizji w dwóch wymiarach. Umożliwia szybkie odrzucenie dużych przestrzeni – gdy zostanie stwierdzone, że któraś ćwiartka nie ma kolizji z danym obiektem, jej podćwiartki też nie mają z nim kolizji. Drzewa czwórkowe znalazły również zastosowanie w kompresji bitmap dwukolorowych (czarno-białych), gdzie obraz dzielony jest na mniejsze części dopóki nie będą one jednokolorowe, a wtedy wystarczy tylko zapisać kolor tego kwadratu, na co wystarcza pojedynczy bit. Trójwymiarowym odpowiednikiem drzew czwórkowych są drzewa ósemkowe.
Abstract from DBpedia / Wikipedia · CC BY-SA