streamalism.org

1. Prehľad

V tomto tutoriáli preskúmame koncept hľadanie susedov v dvojrozmernom priestore. Potom si prejdeme jeho implementáciu v Jave.

2. Jednorozmerné vyhľadávanie vs dvojrozmerné vyhľadávanie

Vieme, že binárne vyhľadávanie je efektívny algoritmus na nájdenie presnej zhody v zozname položiek pomocou prístupu rozdelenia a dobývania.

Poďme teraz uvažujme dvojrozmernú oblasť, kde je každá položka predstavovaná súradnicami XY (bodmi) v rovine.

Avšak namiesto presnej zhody predpokladajme, že chceme nájsť susedov daného bodu v rovine. Je to jasné ak chceme najbližšie n zhôd, potom binárne vyhľadávanie nebude fungovať. Je to tak preto, lebo binárne vyhľadávanie dokáže porovnávať dve položky iba na jednej osi, zatiaľ čo musíme byť schopní porovnávať ich v dvoch osiach.

V nasledujúcej časti sa pozrieme na alternatívu k dátovej štruktúre binárneho stromu.

3. Quadtree

Štvorsten je dátová štruktúra priestorových stromov, v ktorej má každý uzol presne štyri deti. Každé dieťa môže byť bod alebo zoznam obsahujúci štyri podstromy.

A bod ukladá údaje - napríklad súradnice XY. A regiónu predstavuje uzavretú hranicu, v rámci ktorej je možné uložiť bod. Používa sa na definovanie oblasti dosahu štvorstromu.

Pochopme to viac na príklade 10 súradníc v ľubovoľnom poradí:

(21,25), (55,53), (70,318), (98,302), (49,229), (135,229), (224,292), (206,321), (197,258), (245,238)

Prvé tri hodnoty sa uložia ako body pod koreňovým uzlom, ako je to znázornené na obrázku najviac vľavo.

Koreňový uzol teraz nemôže prijať nové body, pretože dosiahol kapacitu troch bodov. Preto budeme rozdelte oblasť koreňového uzla na štyri rovnaké kvadranty.

Každý z týchto kvadrantov môže uložiť tri body a navyše obsahovať štyri kvadranty v rámci svojej hranice. To je možné urobiť rekurzívne, výsledkom je strom kvadrantov, podľa ktorého získa dátová štruktúra štvorstromu svoje meno.

Na strednom obrázku vyššie vidíme kvadranty vytvorené z koreňového uzla a to, ako sú v týchto kvadrantoch uložené ďalšie štyri body.

Napokon obrázok úplne vpravo ukazuje, ako je jeden kvadrant opäť rozdelený tak, aby sa v ňom nachádzalo viac bodov, zatiaľ čo ostatné kvadranty stále môžu akceptovať nové body.

Teraz uvidíme, ako implementovať tento algoritmus v Jave.

4. Štruktúra údajov

Vytvorme dátovú štruktúru štvorstromu. Budeme potrebovať tri doménové triedy.

Najskôr vytvoríme a Bod triedy na uloženie súradníc XY:

public class Point {private float x; súkromný plavák y; public Point (float x, float y) {this.x = x; this.y = y; } // getre & toString ()}

Po druhé, vytvorme a Región triedy na vymedzenie hraníc kvadrantu:

public class Region {private float x1; súkromný plavák y1; súkromný plavák x2; súkromný plavák y2; public Region (float x1, float y1, float x2, float y2) {this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; } // getre a toString ()}

Na záver si dajme a QuadTree trieda na ukladanie údajov ako Bod inštancie a deti ako QuadTree triedy:

verejná trieda QuadTree {súkromný statický konečný int MAX_POINTS = 3; oblasť súkromného regiónu; body súkromného zoznamu = nový ArrayList (); private List quadTrees = new ArrayList (); verejný QuadTree (oblasť regiónu) {this.area = oblasť; }}

Na vytvorenie inštancie a QuadTree objekt, zadáme jeho oblasti pomocou Región triedy prostredníctvom konštruktora.

5. Algoritmus

Predtým, ako napíšeme svoju základnú logiku na ukladanie údajov, pridajme niekoľko pomocných metód. Neskôr sa ukážu ako užitočné.

5.1. Pomocné metódy

Upravme naše Región trieda.

Po prvé, poďme mať metódu containsPoint do uveďte, či daný bod spadá dovnútra alebo zvonka a regiónu oblasti:

public boolean containsPoint (Point point) {return point.getX ()> = this.x1 && point.getX () = this.y1 && point.getY () <this.y2; }

Ďalej poďme mať metódu doesOverlap do uveďte, či daný regiónu prekrýva sa s iným regiónu:

public boolean doesOverlap (Region testRegion) {if (testRegion.getX2 () this.getX2 ()) {return false; } if (testRegion.getY1 ()> this.getY2 ()) {return false; } if (testRegion.getY2 () <this.getY1 ()) {return false; } návrat pravdivý; }

Na záver si vytvoríme metódu getQuadrant do rozdeliť rozsah na štyri rovnaké kvadranty a vrátiť zadaný:

public Region getQuadrant (int quadrantIndex) {float quadrantWidth = (this.x2 - this.x1) / 2; float quadrantHeight = (this.y2 - this.y1) / 2; // 0 = SW, 1 = NW, 2 = NE, 3 = SE switch (quadrantIndex) {case 0: return new Region (x1, y1, x1 + quadrantWidth, y1 + quadrantHeight); prípad 1: vrátiť nový región (x1, y1 + kvadrantVýška, x1 + kvadrantŠírka, y2); prípad 2: vrátiť nový región (x1 + kvadrantWidth, y1 + quadrantHeight, x2, y2); prípad 3: vrátiť nový región (x1 + kvadrantWidth, y1, x2, y1 + quadrantHeight); } return null; }

5.2. Ukladanie údajov

Teraz môžeme napísať našu logiku na ukladanie údajov. Začnime definovaním novej metódy addPoint na QuadTree triedy pridať nový bod. Táto metóda sa vráti pravda ak bol bod úspešne pridaný:

public boolean addPoint (bodový bod) {// ...}

Ďalej napíšeme logiku riešenia bodu. Najskôr musíme skontrolovať, či je bod obsiahnutý v hranici QuadTree inštancia. Musíme tiež zabezpečiť, aby: QuadTree inštancia nedosiahla kapacitu MAX_POINTS bodov.

Ak sú splnené obe podmienky, môžeme pridať nový bod:

if (this.area.containsPoint (point)) {if (this.points.size () <MAX_POINTS) {this.points.add (point); návrat pravdivý; }}

Na druhej strane, keby sme dosiahli MAX_POINTS hodnotu, potom musíme pridať nový bod do jedného z podkvadrantov. Za týmto účelom prechádzame slučkou cez dieťa štvorstromy zoznam a volajte rovnako addPoint metóda, ktorá vráti a pravda hodnota pri úspešnom pridaní. Potom okamžite opustíme slučku ako bod je potrebné pridať presne do jedného kvadrantu.

Celú túto logiku môžeme zapuzdriť do pomocnej metódy:

private boolean addPointToOneQuadrant (Point point) {boolean isPointAdded; pre (int i = 0; i <4; i ++) {isPointAdded = this.quadTrees.get (i) .addPoint (bod); if (isPointAdded) return true; } return false; }

Ďalej si dajme šikovnú metódu createQuadrants rozdeliť súčasný kvadrant na štyri kvadranty:

private void createQuadrants () {Oblasť regiónu; pre (int i = 0; i <4; i ++) {region = this.area.getQuadrant (i); quadTrees.add (nový QuadTree (región)); }}

Túto metódu zavoláme na vytvárať kvadranty, iba ak už nemôžeme pridávať nové body. To zaisťuje, že naša dátová štruktúra využíva optimálny pamäťový priestor.

Keď to zhrnieme všetko, máme aktualizáciu addPoint metóda:

public boolean addPoint (Bodový bod) {if (this.area.containsPoint (bod)) {if (this.points.size () <MAX_POINTS) {this.points.add (bod); návrat pravdivý; } else {if (this.quadTrees.size () == 0) {createQuadrants (); } návrat addPointToOneQuadrant (bod); }} return false; }

5.3. Vyhľadávanie údajov

Keď máme definovanú našu štruktúru štvorlístka na ukladanie údajov, môžeme teraz myslieť na logiku vykonávania vyhľadávania.

Keď hľadáme hľadanie susedných predmetov, môžeme uveďte a searchRegion ako východiskový bod. Potom skontrolujeme, či sa prekrýva s koreňovou oblasťou. Ak áno, pridáme všetky jeho podradené body, ktoré spadajú do searchRegion.

Po koreňovej oblasti sa dostaneme do každého z kvadrantov a postup opakujeme. Takto to pokračuje, kým sa nedostaneme na koniec stromu.

Napíšeme vyššie uvedenú logiku ako rekurzívnu metódu do súboru QuadTree trieda:

verejné vyhľadávanie v zozname (Region searchRegion, zoznam zápasov) {if (zápasy == null) {zápasy = nový ArrayList (); } if (! this.area.doesOverlap (searchRegion)) {návratové zhody; } else {for (Point point: points) {if (searchRegion.containsPoint (point)) {match.add (point); }} if (this.quadTrees.size ()> 0) {for (int i = 0; i <4; i ++) {quadTrees.get (i) .search (searchRegion, matches); }}} vrátiť zápasy; }

6. Testovanie

Teraz, keď máme náš algoritmus zavedený, otestujme ho.

6.1. Vyplnenie údajov

Najskôr naplníme štvorkolku rovnakými 10 súradnicami, ktoré sme použili predtým:

Oblasť regiónu = nový región (0, 0, 400, 400); QuadTree quadTree = nový QuadTree (oblasť); float [] [] points = new float [] [] {{21, 25}, {55, 53}, {70, 318}, {98, 302}, {49, 229}, {135, 229}, {224, 292}, {206, 321}, {197, 258}, {245, 238}}; for (int i = 0; i <points.length; i ++) {Point point = new Point (points [i] [0], points [i] [1]); quadTree.addPoint (bod); }

6.2. Vyhľadávanie rozsahu

Ďalej vykonajme hľadanie rozsahu v oblasti ohraničenej súradnicou dolnej hranice (200, 200) a súradnice hornej hranice (250, 250):

Region searchArea = nový región (200, 200, 250, 250); Výsledok zoznamu = quadTree.search (searchArea, null);

Spustenie kódu nám poskytne jednu súradnicu v blízkosti, ktorá sa nachádza v oblasti vyhľadávania:

[[245.0 , 238.0]]

Vyskúšajme inú oblasť vyhľadávania medzi súradnicami (0, 0) a (100, 100):

Region searchArea = nový región (0, 0, 100, 100); Výsledok zoznamu = quadTree.search (searchArea, null);

Spustenie kódu nám poskytne dve susedné súradnice pre zadanú oblasť vyhľadávania:

[[21.0 , 25.0], [55.0 , 53.0]]

Pozorujeme, že v závislosti od veľkosti oblasti vyhľadávania dostaneme nulu, jeden alebo viac bodov. Takže ak dostaneme bod a požiadame o nájdenie najbližšieho n susedia, mohli by sme definovať vhodnú oblasť hľadania, kde je daný bod v strede.

Potom môžeme zo všetkých výsledných bodov vyhľadávacej operácie vypočítajte euklidovské vzdialenosti medzi danými bodmi a roztriedte ich tak, aby ste získali najbližších susedov.

7. Časová zložitosť

Časová zložitosť dotazu na rozsah je jednoduchá O (n). Dôvod je ten, že v najhoršom prípade musí prejsť každou položkou, ak je zadaná oblasť vyhľadávania rovnaká alebo väčšia ako obývaná oblasť.

8. Záver

V tomto článku sme najskôr pochopili koncept štvorstromu jeho porovnaním s binárnym stromom. Ďalej sme videli, ako sa dá efektívne využiť na ukladanie údajov rozšírených v dvojrozmernom priestore.

Potom sme videli, ako ukladať údaje a vykonávať prehľad rozsahu.

Ako vždy, zdrojový kód s testami je k dispozícii na GitHub.