streamalism.org

1. Pregled

U ovom uputstvu istražit ćemo koncept traženje susjeda u dvodimenzionalnom prostoru. Zatim ćemo proći kroz njegovu implementaciju u Javi.

2. Jednodimenzionalna pretraga vs dvodimenzionalna pretraga

Znamo da je binarno pretraživanje učinkovit algoritam za pronalaženje točnog podudaranja na popisu stavki koristeći pristup podijeli i osvoji.

Idemo sada razmotrimo dvodimenzionalno područje u kojem je svaka stavka predstavljena XY koordinatama (točkama) u ravnini.

Međutim, umjesto točnog podudaranja, pretpostavimo da želimo pronaći susjede određene točke u ravnini. Jasno je da ako želimo najbliže n podudara se, tada binarno pretraživanje neće raditi. To je zato što binarno pretraživanje može usporediti dvije stavke samo u jednoj osi, dok ih trebamo biti u mogućnosti usporediti u dvije osi.

U sljedećem ćemo odjeljku pogledati alternativu strukturi podataka binarnog stabla.

3. Quadtree

Kvadrat je struktura podataka prostornog stabla u kojoj svaki čvor ima točno četvero djece. Svako dijete može biti točka ili popis koji sadrži četiri potkvadreva.

A točka pohranjuje podatke - na primjer, XY koordinate. A regija predstavlja zatvorenu granicu unutar koje se točka može pohraniti. Koristi se za definiranje područja dosega kvadrata.

Shvatimo to više koristeći primjer 10 koordinata u nekom proizvoljnom redoslijedu:

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

Prve tri vrijednosti pohranit će se kao točke ispod korijenskog čvora kao što je prikazano na krajnjoj lijevoj slici.

Korijenski čvor sada ne može primiti nove točke jer je dosegao svoj kapacitet od tri točke. Stoga ćemo podijeliti područje korijenskog čvora na četiri jednaka kvadranta.

Svaki od ovih kvadranata može pohraniti tri točke i dodatno sadržavati četiri kvadranta unutar svojih granica. To se može učiniti rekurzivno, što rezultira stablom kvadranata, odakle i struktura podataka kvadrata dobiva svoje ime.

Na gornjoj srednjoj slici možemo vidjeti kvadrante stvorene od korijenskog čvora i kako su sljedeće četiri točke pohranjene u tim kvadrantima.

Konačno, slika najdesnije prikazuje kako se jedan kvadrant ponovno dijeli da primi više točaka u toj regiji, dok drugi kvadranti još uvijek mogu prihvatiti nove točke.

Sad ćemo vidjeti kako implementirati ovaj algoritam u Javi.

4. Struktura podataka

Stvorimo strukturu podataka quadtree. Trebat će nam tri klase domene.

Prvo ćemo stvoriti Točka razreda za pohranu XY koordinata:

točka javne klase {private float x; privatni plutajući y; javna točka (float x, float y) {this.x = x; ovo.y = y; } // getters & toString ()}

Drugo, stvorimo a Regija klasa za definiranje granica kvadranta:

javna klasa Regija {private float x1; privatni plovak y1; privatni plovak x2; privatni plovak y2; javna regija (float x1, float y1, float x2, float y2) {this.x1 = x1; ovo.y1 = y1; ovo.x2 = x2; ovo.y2 = y2; } // getters & toString ()}

Konačno, uzmimo a QuadTree klase za pohranu podataka kao Točka instance i djeca kao QuadTree razreda:

javna klasa QuadTree {private static final int MAX_POINTS = 3; privatno područje regije; privatni popisni bodovi = novi ArrayList (); privatni popis quadTrees = novi ArrayList (); javno QuadTree (područje regije) {this.area = area; }}

Za instanciranje a QuadTree objekt, mi specificiramo njegov područje koristiti Regija klasa kroz konstruktor.

5. Algoritam

Prije nego što napišemo svoju osnovnu logiku za pohranu podataka, dodajmo nekoliko pomoćnih metoda. Oni će se kasnije pokazati korisnima.

5.1. Metode pomagača

Izmijenimo svoj Regija razred.

Prvo, imajmo metodu sadržiPoint do naznačiti je li dano točka pada unutar ili izvan a regije područje:

javna logička vrijednost sadržiPoint (Point point) {return point.getX ()> = this.x1 && point.getX () = this.y1 && point.getY () <this.y2; }

Dalje, imajmo metodu ne Preklapa se do naznačiti je li dano regija preklapa se s drugom regija:

javni boolean doesOverlap (Regija testRegion) {if (testRegion.getX2 () this.getX2 ()) {return false; } if (testRegion.getY1 ()> this.getY2 ()) {return false; } if (testRegion.getY2 () <this.getY1 ()) {return false; } return true; }

Napokon, kreirajmo metodu getQuadrant do podijeliti raspon na četiri jednaka kvadranta i vratite navedeni:

javna Regija getQuadrant (int quadrantIndex) {float quadrantWidth = (this.x2 - this.x1) / 2; float quadrantHeight = (this.y2 - this.y1) / 2; // 0 = SW, 1 = SZ, 2 = NE, 3 = prekidač SE (quadrantIndex) {slučaj 0: vrati novu regiju (x1, y1, x1 + quadrantWidth, y1 + quadrantHeight); slučaj 1: vrati novu regiju (x1, y1 + quadrantHeight, x1 + quadrantWidth, y2); slučaj 2: vratiti novu regiju (x1 + quadrantWidth, y1 + quadrantHeight, x2, y2); slučaj 3: vratiti novu regiju (x1 + quadrantWidth, y1, x2, y1 + quadrantHeight); } return null; }

5.2. Pohranjivanje podataka

Sada možemo napisati svoju logiku za pohranu podataka. Počnimo s definiranjem nove metode addPoint na QuadTree razred za dodavanje novog točka. Ova metoda će se vratiti pravi ako je točka uspješno dodana:

javna boolean addPoint (Point point) {// ...}

Dalje, napišimo logiku za rješavanje točke. Prvo, moramo provjeriti je li točka unutar granica QuadTree primjer. Također moramo osigurati da QuadTree instanca nije dosegla sposobnost MAX_POINTS bodova.

Ako su oba uvjeta zadovoljena, možemo dodati novu točku:

if (this.area.containsPoint (point)) {if (this.points.size () <MAX_POINTS) {this.points.add (point); povratak istinit; }}

S druge strane, ako smo stigli do MAX_POINTS vrijednost, tada moramo dodati novu točka na jedan od potkvadranata. Zbog toga prolazimo kroz dijete četverostabla navesti i nazvati isto addPoint metoda koja će vratiti a pravi vrijednost na uspješnom dodavanju. Zatim izlazimo iz petlje odmah kao točku treba dodati točno u jedan kvadrant.

Svu ovu logiku možemo enkapsulirati u pomoćnu metodu:

privatni logički addPointToOneQuadrant (točka točke) {boolean isPointAdded; za (int i = 0; i <4; i ++) {isPointAdded = this.quadTrees.get (i) .addPoint (točka); if (isPointAdded) return true; } return false; }

Uz to, imajmo praktičnu metodu createQuadrants da podijelimo trenutni kvadrant u četiri kvadranta:

private void createQuadrants () {Regija regije; for (int i = 0; i <4; i ++) {region = this.area.getQuadrant (i); quadTrees.add (novo QuadTree (regija)); }}

Nazvat ćemo ovu metodu stvorite kvadrante samo ako više ne možemo dodavati nove točke. To osigurava da naša struktura podataka koristi optimalan memorijski prostor.

Sastavljajući sve zajedno, ažurirali smo addPoint metoda:

javna boolean addPoint (Point point) {if (this.area.containsPoint (point)) {if (this.points.size () <MAX_POINTS) {this.points.add (point); povratak istinit; } else {if (this.quadTrees.size () == 0) {createQuadrants (); } return addPointToOneQuadrant (točka); }} return false; }

5.3. Pretraživanje podataka

Imajući našu strukturu četverostabla definiranu za pohranu podataka, sada možemo smisliti logiku izvođenja pretraživanja.

Dok tražimo pronalazak susjednih predmeta, možemo navedite a searchRegion kao polazna točka. Zatim provjeravamo preklapa li se s korijenovom regijom. Ako se dogodi, zbrajamo sve njegove podređene točke koje spadaju u searchRegion.

Nakon korijenske regije ulazimo u svaki od kvadranata i ponavljamo postupak. To traje sve dok ne dođemo do kraja stabla.

Napišimo gornju logiku kao rekurzivnu metodu u QuadTree razred:

pretraživanje javnog popisa (Region searchRegion, Popis podudaranja) {if (matches == null) {matches = new ArrayList (); } if (! this.area.doesOverlap (searchRegion)) {return matches; } else {for (Point point: points) {if (searchRegion.containsPoint (point)) {matches.add (point); }} if (this.quadTrees.size ()> 0) {for (int i = 0; i <4; i ++) {quadTrees.get (i) .search (searchRegion, match); }}} uzvratne utakmice; }

6. Ispitivanje

Sad kad imamo svoj algoritam, testirajmo ga.

6.1. Popunjavanje podataka

Prvo, napunimo četverokut istim 10 koordinata koje smo koristili ranije:

Područje regije = nova Regija (0, 0, 400, 400); QuadTree quadTree = novo QuadTree (područje); float [] [] bodovi = novi 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 ++) {Točka točka = nova Točka (točke [i] [0], točke [i] [1]); quadTree.addPoint (točka); }

6.2. Pretraživanje dometa

Dalje, izvršimo pretragu raspona u području zatvorenom donjom granicom (200, 200) i gornjom granicom (250, 250):

Region searchArea = nova regija (200, 200, 250, 250); Rezultat popisa = quadTree.search (područje pretraživanja, null);

Pokretanjem koda dobit ćemo jednu obližnju koordinatu koja se nalazi unutar područja pretraživanja:

[[245.0 , 238.0]]

Pokušajmo s drugim područjem pretraživanja između koordinata (0, 0) i (100, 100):

Region searchArea = nova regija (0, 0, 100, 100); Rezultat popisa = quadTree.search (područje pretraživanja, null);

Pokretanjem koda dobit ćemo dvije obližnje koordinate za određeno područje pretraživanja:

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

Primjećujemo da ovisno o veličini područja pretraživanja dobivamo nulu, jednu ili više bodova. Tako, ako nam se da bod i zatražimo da pronađemo najbližeg n susjedi, mogli bismo definirati prikladno područje pretraživanja u kojem je zadana točka u središtu.

Tada iz svih rezultirajućih točaka postupka pretraživanja možemo izračunajte euklidske udaljenosti između zadanih točaka i razvrstajte ih kako biste dobili najbliže susjede.

7. Složenost vremena

Složenost upita za raspon vremenska je jednostavno Na). Razlog je taj što u najgorem scenariju mora prijeći svaku stavku ako je navedeno područje pretraživanja jednako ili veće od naseljenog područja.

8. Zaključak

U ovom smo članku najprije shvatili pojam četverostabla usporedbom s binarnim stablom. Zatim smo vidjeli kako se može učinkovito koristiti za pohranu podataka raširenih u dvodimenzionalnom prostoru.

Zatim smo vidjeli kako pohraniti podatke i izvršiti pretraživanje raspona.

Kao i uvijek, izvorni kod s testovima dostupan je na GitHubu.