Co to jest quad?

Quad Tree, czasem quadTree, Q-Tree lub QT, to termin informatywny, który odnosi się do metody organizowania danych w czterech ćwiartkach.Bazy danych czasami używają quad drzew do przechowywania i znajdowania swoich rekordów.Ten rodzaj struktury organizacyjnej działa szczególnie dobrze, aby znaleźć konkretny bit lub piksel na dwuwymiarowym obrazie.

Quad Tree nieco podąża za strukturą danych drzewa powszechnie używaną w informatyce.Normalna struktura danych drzewa wygląda jak odwrócona w dół, w którym węzeł nadrzędny u góry drzewa ma podłączony jeden lub więcej węzłów dla dzieci.Każdy inny węzeł na drzewie ma jeden węzeł nadrzędny i może mieć dowolną liczbę węzłów dziecięcych, w tym zero.

W przeciwieństwie do normalnej struktury danych drzewa, struktura czterokrotnie wymaga, aby każdy węzeł wewnętrzny miał dokładnie czworo węzłów dzieci.Ilustrując większość struktur kwadratowych, zobaczysz węzeł, w którym wisi czworo węzłów dziecięcych, z liniami łączącymi węzeł nadrzędny z węzłami dla dzieci.Ilustracja może być kontynuowana, z czworo kolejnymi węzłami dziecięcymi wiszącymi z każdego z czworo oryginalnych węzłów dziecięcych. Innym razem ilustracja quadu będzie region lub kwadrat.Ilekroć region osiąga maksymalną pojemność do przechowywania danych, jest on podzielony na cztery ćwiartki.Zwykle regiony i kwadranty są kwadrami, chociaż mogą być również prostokątami lub innymi kształtami.

Quad Tree to dobra struktura danych do organizowania pikseli na zdjęciu i do organizowania grafiki komputerowej.Obraz można podzielić na ćwiartki, a każda kwadrant można podzielić na cztery kolejne.Można to powtarzać raz po raz, aż osiągniesz poziom poszczególnych pikseli.Jeśli kwadrant zawiera piksele, które są w tym samym kolorze, nie ma powodu, aby dalej dzielić kwadrant.

Chociaż dane przechowywane w strukturze czterordzeniowej mogą wymagać dużo miejsca do przechowywania w porównaniu z innymi metodami organizowania danych dla grafiki komputerowej, Struktura drzewa czterokrotnego ma kilka zalet.Najpierw możesz usunąć całe zdjęcie lub grafikę na jeden krok, oczyszczając węzeł główny, który usuwa również wszystkie węzły jego dzieci.Po drugie, szybko możesz zmniejszyć rozdzielczość na zdjęciu, po prostu oczyszczając końcowy poziom węzłów dzieci.Spowoduje to w ten sposób zmniejszenie wymaganej ilości miejsca do przechowywania.Wreszcie znalezienie konkretnego obszaru fotografii do manipulacji obrazem jest łatwiejsze dzięki strukturze quad drzewa.

Quad drzewa są również używane w kilku innych sytuacjach, w tym indeksowanie przestrzenne.Chociaż quady są ograniczone do obrazów dwuwymiarowych, reprezentowanie trójwymiarowego obrazu może podążać za podobną strukturą, zwaną oktree, która jest podziałem kostki na ośmioro dzieci.