A K-D fa (más néven K-dimenziós fa) egy bináris keresési fa, ahol az egyes csomópontokban lévő adatok egy K- dimenziós pont a térben … Balra mutat ennek a térnek az adott csomópont bal oldali részfája, a tértől jobbra lévő pontokat pedig a jobb oldali részfa képviseli.
A KD Tree pontos?
Az adatpontok minden csomópontnál két készletre vannak osztva. Az előző algoritmushoz hasonlóan a KD Tree is egy bináris fa algoritmus, amely mindig maximum két csomópontra végződik … Az alábbi kép jobb oldalán láthatja a adatpontok, bal oldalon ezek térbeli helyzete.
Hogyan készíthetsz KD fát?
KD-Tree építése
- Az első beillesztett pont a fa gyökerévé válik.
- Válassza ki a tengelyt a mélység alapján, hogy a tengely az összes érvényes értéken áthaladjon. …
- A pontlista rendezése tengely szerint, és forgáselemnek válassza a mediánt. …
- Haladjon be a fán, amíg a csomópont üres nem lesz, majd rendeljen pontot a csomóponthoz.
- Ismételje meg a 2-4 lépést rekurzívan, amíg az összes pontot feldolgozza.
Miért használunk kd fát?
A KD-fák egy speciális adatstruktúra az adataink hatékony megjelenítéséhez A KD-fák különösen segítik az adatpontok meghatározott feltételek alapján történő rendszerezését és particionálását. Most néhány tengelyhez igazított vágást fogunk végezni, és listákat vezetünk azokról a pontokról, amelyek ezekbe a különböző rekeszekbe esnek.
Az octree egy fa kd?
Az oktfa minden levélcsomópontjának adatai egy helyi KD-fából állnak. Az oktrában a csomópontok csak a határolódobozra vonatkozó információkat tárolják. A kutatás kényelme érdekében minden levélcsomóponthoz indexérték tartozik.
