Drzewo czwórkowe

Drzewo czwórkowe

Drzewo czwórkowe to struktura danych, która dzieli dwuwymiarową przestrzeń na mniejsze części poprzez podział na cztery równe ćwiartki. Ta struktura ma zastosowanie w różnych dziedzinach, w tym w wykrywaniu kolizji oraz kompresji danych.

Zastosowania

• Wykrywanie kolizji: Drzewo czwórkowe umożliwia szybkie odrzucenie dużych obszarów przestrzeni. Jeśli jedna ćwiartka nie ma kolizji z obiektem, to jej podćwiartki również nie będą miały kolizji.
• Kompresja bitmap dwukolorowych: W przypadku obrazów czarno-białych, drzewo czwórkowe dzieli obraz na mniejsze części, aż uzyska jednokolorowe obszary. W takim przypadku wystarczy zapisać kolor kwadratu, co można zrobić za pomocą jednego bitu.

Odpowiednik w trójwymiarze

Trójwymiarowym odpowiednikiem drzew czwórkowych są drzewa ósemkowe, które działają na podobnej zasadzie, ale w trzech wymiarach.