Drzewo czwórkowe

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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.

Bitmapa reprezentowana przez drzewo czwórkowe

Trójwymiarowym odpowiednikiem drzew czwórkowych są drzewa ósemkowe.

Zobacz też[edytuj | edytuj kod]