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, z liniami łączącymi węzeł nadrzędny z węzłami dla dzieci. IlustraAtion może kontynuować, z czwórką kolejnych węzłów dziecięcych wiszących z każdego z czworo oryginalnych węzłów dziecięcych.

Ilustracją kwadratu 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 mają ten sam kolor, nie ma powodu, aby dalej dzielić ćwiartkę.

Chociaż dane przechowywane w strukturze drzewa czterokrotnego mogą wymagać dużo miejsca do przechowywania w porównaniu z innymiMetody organizowania danych do grafiki komputerowej, struktura quade 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 określonego obszaru fotografii do manipulacji obrazem jest łatwiejsze dzięki strukturze quad drzewa.

Czwarte drzewa są również używane w kilku innych sytuacjach, w tym w indeksowaniu przestrzennym. 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.