Tartomány keresési algoritmus a Java-ban

1. Áttekintés

Ebben az oktatóanyagban feltárjuk a fogalmát szomszédokat keres kétdimenziós térben. Ezután áttekintjük a Java-ban történő megvalósítását.

2. Egydimenziós keresés vs kétdimenziós keresés

Tudjuk, hogy a bináris keresés hatékony algoritmus a pontos egyezés megtalálásához az elemek listájában, oszd meg és hódítsd módszerrel.

Nézzük most vegyünk egy kétdimenziós területet, ahol minden elemet XY koordináták (pontok) képviselnek egy síkban.

Pontos egyezés helyett tegyük fel azonban, hogy a síkon egy adott pont szomszédjait akarjuk megtalálni. Ez egyértelmű ha a legközelebb akarunk n egyezik, akkor a bináris keresés nem fog működni. Ennek oka, hogy a bináris keresés két elemet képes összehasonlítani csak egy tengelyben, míg nekünk két tengelyben kell összehasonlítani őket.

A következő szakaszban megvizsgáljuk a bináris fa adatstruktúrájának alternatíváját.

3. Quadtree

A quadree egy térbeli fa adatstruktúra, amelyben minden csomópontnak pontosan négy gyermeke van. Minden gyermek lehet egy pont vagy egy lista, amely négy al-negyedfát tartalmaz.

A pont adatokat tárol - például XY koordinátákat. A vidék zárt határt képvisel, amelyen belül egy pont tárolható. A quadtree elérési területének meghatározására szolgál.

Értsük meg ezt jobban, ha tetszőleges sorrendben 10 koordinátát mutatunk be:

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

Az első három értéket pontként tároljuk a gyökércsomópont alatt, a bal oldali képen látható módon.

A gyökércsomópont most nem képes új pontok befogadására, mivel elérte hárompontos kapacitását. Ezért megtesszük ossza fel a gyökércsomópont régióját négy egyenlő kvadránsra.

E négyzetek mindegyike három pontot tárolhat, és négy negyedet tartalmazhat a határán belül. Ez megtehető rekurzív módon, így egy kvadránsfa jön létre, ahol a négyfás adatstruktúra megkapja a nevét.

A fenti középső képen láthatjuk a gyökércsomópontból létrehozott kvadránsokat és azt, hogy a következő négy pont hogyan van tárolva ezekben a kvadránsokban.

Végül a jobb szélső kép azt mutatja, hogy az egyik kvadrát ismét fel van osztva több pont befogadására az adott régióban, miközben a többi kvadráns még mindig képes elfogadni az új pontokat.

Most meglátjuk, hogyan lehet ezt az algoritmust Java-ban megvalósítani.

4. Adatszerkezet

Hozzunk létre egy négyfás adatstruktúrát. Három domain osztályra lesz szükségünk.

Először létrehozunk egy Pont osztály az XY koordináták tárolására:

public class Pont {private float x; privát úszó y; public Point (float x, float y) {ez.x = x; ez.y = y; } // getters & toString ()}

Másodsorban hozzunk létre egy Vidék osztály meghatározza a kvadrát határait:

public class Region {private float x1; privát úszó y1; magán úszó x2; privát úszó y2; public Region (float x1, float y1, float x2, float y2) {ez.x1 = x1; ez.y1 = y1; ez.x2 = x2; ez.y2 = y2; } // getters & toString ()}

Végül legyen egy QuadTree osztály az adatok tárolására Pont esetek és gyermekek mint QuadTree osztályok:

nyilvános osztály QuadTree {private static final int MAX_POINTS = 3; privát Régió területe; privát Lista pontok = új ArrayList (); privát lista quadTrees = new ArrayList (); public QuadTree (Region area) {this.terület = terület; }}

Példaként a QuadTree objektumot, megadjuk annak terület használni a Vidék osztály a kivitelezőn keresztül.

5. Algoritmus

Mielőtt megírnánk az alapvető logikánkat az adatok tárolására, adjunk hozzá néhány segítő módszert. Ezek később hasznosnak bizonyulnak.

5.1. Segítő módszerek

Módosítsuk a Vidék osztály.

Először is, legyen egy módszerünk tartalmazPointot nak nek jelezze, ha adott pont belül vagy kívül esik a régiók terület:

nyilvános logikai elem tartalmazzaPoint (Pont pont) {return point.getX ()> = this.x1 && point.getX () = this.y1 && point.getY () <this.y2; }

Ezután legyen egy módszer doOlaplap nak nek jelezze, ha adott vidék átfedésben van egy másikkal vidék:

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; } return true; }

Végül hozzunk létre egy módszert getQuadrant nak nek osszon egy tartományt négy egyenlő kvadránsra és küldjön vissza egy megadottat:

public régió getQuadrant (int quadrantIndex) {float quadrantWidth = (this.x2 - this.x1) / 2; float quadrantHeight = (this.y2 - this.y1) / 2; // 0 = SW, 1 = ÉNy, 2 = NE, 3 = SE kapcsoló (quadrantIndex) {eset 0: return new Region (x1, y1, x1 + quadrantWidth, y1 + quadrantHeight); 1. eset: adja vissza az új régiót (x1, y1 + quadrantHeight, x1 + quadrantWidth, y2); 2. eset: adja vissza az új régiót (x1 + kvadrát szélesség, y1 + kvadrát magasság, x2, y2); 3. eset: adja vissza az új régiót (x1 + quadrantWidth, y1, x2, y1 + quadrantHeight); } return null; }

5.2. Adatok tárolása

Most megírhatjuk logikánkat az adatok tárolására. Kezdjük egy új módszer definiálásával addPoint a QuadTree osztály új hozzáadásához pont. Ez a módszer visszatér igaz ha egy pontot sikeresen hozzáadtunk:

nyilvános logikai addPoint (Pontpont) {// ...}

Ezután írjuk meg a logikát a lényeg kezelésére. Először ellenőriznünk kell, hogy a pont a QuadTree példa. Azt is biztosítanunk kell, hogy a QuadTree példány nem érte el a MAX_POINTS pontokat.

Ha mindkét feltétel teljesül, hozzáadhatjuk az új pontot:

if (this.area.containPoint (point)) {if (this.points.size () <MAX_POINTS) {this.points.add (point); return true; }}

Másrészről, ha elértük a MAX_POINTS értéket, akkor hozzá kell adnunk az újat pont az egyik alnegyedre. Ehhez végighurkoljuk a gyereket quadTrees listázza, és hívja ugyanazt addPoint módszer, amely a igaz a sikeres hozzáadás értéke. Ezután azonnal kilépünk a hurokból pontot pontosan hozzá kell adni egy kvadránshoz.

Ezt a logikát egy helper módszerbe foglalhatjuk:

privát logikai addPointToOneQuadrant (Pontpont) {logikai isPointAdded; for (int i = 0; i <4; i ++) {isPointAdded = this.quadTrees.get (i) .addPoint (point); if (isPointAdded) return true; } return false; }

Ezenkívül legyen egy praktikus módszerünk createQuadrants hogy az aktuális négyfát négy kvadránsra osztjuk:

private void createQuadrants () {Régió régiója; for (int i = 0; i <4; i ++) {régió = ez a terület.getQuadrant (i); quadTrees.add (új QuadTree (régió)); }}

Meghívjuk ezt a módszert csak akkor hozhatunk létre kvadránsokat, ha már nem tudunk új pontokat hozzáadni. Ez biztosítja, hogy adatstruktúránk az optimális memóriaterületet használja fel.

Az egészet összefogva megvan a frissítés addPoint módszer:

nyilvános logikai addPoint (Pont pont) {if (this.area.containsPoint (point)) {if (this.points.size () <MAX_POINTS) {this.points.add (point); return true; } else {if (this.quadTrees.size () == 0) {createQuadrants (); } return addPointToOneQuadrant (pont); }} return false; }

5.3. Adatok keresése

Miután meghatároztuk a négyfás struktúránkat az adatok tárolására, most gondolkodhatunk a keresés végrehajtásának logikáján.

Amint keresünk szomszédos tárgyakat, megtehetjük adja meg a searchRegion kiindulópontként. Ezután ellenőrizzük, hogy átfedésben van-e a gyökérterülettel. Ha mégis, akkor hozzáadjuk az összes gyermekpontját, amely a searchRegion.

A gyökérterület után bejutunk az egyes kvadránsokba, és megismételjük a folyamatot. Ez addig tart, amíg el nem érjük a fa végét.

Írjuk a fenti logikát rekurzív módszerként a QuadTree osztály:

nyilvános listakeresés (Region searchRegion, List matching) {if (egyezik == null) {mérkőzések = új ArrayList (); } if (! this.area.doesOverlap (searchRegion)) {return mérkőzések; } else {for (Pontpont: pontok) {if (searchRegion.containsPoint (pont)) {match.add (pont); }} if (this.quadTrees.size ()> 0) {for (int i = 0; i <4; i ++) {quadTrees.get (i) .search (searchRegion, mérkőzések); }}} visszatér mérkőzések; }

6. Tesztelés

Most, hogy az algoritmusunk a helyén van, teszteljük.

6.1. Az adatok feltöltése

Először töltsük be a négyzetfát ugyanazzal a 10 koordinátával, amelyet korábban használtunk:

Régió területe = új régió (0, 0, 400, 400); QuadTree quadTree = új QuadTree (terület); úszó [] [] pont = új úszó [] [] {{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 <pontok.hossz; i ++) {Pontpont = új Pont (pontok [i] [0], pontok [i] [1]); quadTree.addPoint (pont); }

6.2. Tartománykeresés

Ezután végezzünk egy tartomány keresést egy olyan területen, amelyet az alsó határ koordinátája (200, 200) és a felső határ koordinátája (250, 250) bezár:

Region searchArea = új régió (200, 200, 250, 250); Lista eredménye = quadTree.search (searchArea, null);

A kód futtatásával egy közeli koordinátát kapunk a keresési területen:

[[245.0 , 238.0]]

Próbálkozzunk egy másik keresési területtel a (0, 0) és (100, 100) koordináták között:

Region searchArea = új régió (0, 0, 100, 100); Lista eredménye = quadTree.search (searchArea, null);

A kód futtatása két közeli koordinátát kap a megadott keresési területhez:

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

Megfigyeljük, hogy a keresési terület nagyságától függően nulla, egy vagy sok pontot kapunk. Így, ha kapunk egy pontot, és megkérjük, hogy keresse meg a legközelebbi n szomszédok, meghatározhatnánk egy megfelelő keresési területet, ahol az adott pont áll a középpontban.

Ezután a keresési művelet összes eredő pontjából megtehetjük számítsa ki az euklideszi távolságokat a megadott pontok között, és rendezze őket a legközelebbi szomszédok megszerzéséhez.

7. Az idő komplexitása

Egy tartomány lekérdezésének időbeli összetettsége egyszerűen Tovább). Ennek oka, hogy a legrosszabb esetben minden elemen keresztül kell haladnia, ha a megadott keresési terület megegyezik vagy nagyobb, mint a lakott terület.

8. Következtetés

Ebben a cikkben először megértettük a quadtree fogalmát, összehasonlítva azt egy bináris fával. Ezután láttuk, hogyan lehet hatékonyan felhasználni kétdimenziós térben elterjedt adatok tárolására.

Ezután láttuk, hogyan kell tárolni az adatokat és elvégezni a tartomány keresését.

Mint mindig, a tesztekkel ellátott forráskód is elérhető a GitHubon.