streamalism.org

1. Oversigt

I denne vejledning undersøger vi begrebet søger efter naboer i et todimensionelt rum. Derefter gennemgår vi implementeringen i Java.

2. En-dimensionel søgning vs to-dimensionel søgning

Vi ved, at binær søgning er en effektiv algoritme til at finde et nøjagtigt match i en liste over emner ved hjælp af en del-og-erobre tilgang.

Lad os nu overvej et todimensionelt område, hvor hvert element er repræsenteret af XY-koordinater (punkter) i et plan.

Men i stedet for et nøjagtigt match, formoder vi, at vi vil finde naboer til et givet punkt i flyet. Det er klart det hvis vi vil have det nærmeste n matcher, så fungerer den binære søgning ikke. Dette skyldes, at den binære søgning kun kan sammenligne to elementer i en akse, mens vi skal være i stand til at sammenligne dem i to akser.

Vi ser på et alternativ til den binære tredatastruktur i det næste afsnit.

3. Quadtree

Et firetræ er en rumlig tredatastruktur, hvor hver knude har nøjagtigt fire børn. Hvert barn kan enten være et punkt eller en liste, der indeholder fire under-kvadratre.

EN punkt gemmer data - for eksempel XY-koordinater. EN område repræsenterer en lukket grænse, inden for hvilken et punkt kan lagres. Det bruges til at definere rækkevidden for et firetræ.

Lad os forstå dette mere ved hjælp af et eksempel på 10 koordinater i en vilkårlig rækkefølge:

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

De første tre værdier gemmes som punkter under rodnoden som vist på billedet til venstre.

Rodknudepunktet kan ikke rumme nye punkter nu, da det har nået sin kapacitet på tre point. Derfor vil vi del regionen af ​​rodnoden i fire lige store kvadranter.

Hver af disse kvadranter kan gemme tre punkter og desuden indeholde fire kvadranter inden for dens grænse. Dette kan gøres rekursivt, hvilket resulterer i et træ med kvadranter, det er her kvadrattrendatastrukturen får sit navn.

På det midterste billede ovenfor kan vi se kvadranterne oprettet fra rodnoden, og hvordan de næste fire punkter er gemt i disse kvadranter.

Endelig viser billedet til højre, hvordan en kvadrant igen er opdelt for at rumme flere point i denne region, mens de andre kvadranter stadig kan acceptere de nye punkter.

Vi ser nu, hvordan vi implementerer denne algoritme i Java.

4. Datastruktur

Lad os oprette en firestedsdatastruktur. Vi har brug for tre domæneklasser.

For det første opretter vi en Punkt klasse for at gemme XY-koordinaterne:

offentlig klasse Punkt {privat float x; privat flyde y; public Point (float x, float y) {this.x = x; this.y = y; } // getters & toString ()}

For det andet, lad os oprette en Område klasse til at definere grænserne for en kvadrant:

offentlig klasse Region {private float x1; privat float y1; privat float x2; privat flyde y2; public Region (float x1, float y1, float x2, float y2) {this.x1 = x1; this.y1 = y1; dette. x2 = x2; this.y2 = y2; } // getters & toString ()}

Lad os endelig have en QuadTree klasse til at gemme data som Punkt tilfælde og børn som QuadTree klasser:

offentlig klasse QuadTree {privat statisk endelig int MAX_POINTS = 3; privat region område; private listepunkter = ny ArrayList (); privat liste quadTrees = ny ArrayList (); offentlig QuadTree (Region område) {this.area = area; }}

At instantiere en QuadTree objekt, vi specificerer dens areal bruger Område klasse gennem konstruktøren.

5. Algoritme

Før vi skriver vores kernelogik til at gemme data, lad os tilføje et par hjælpemetoder. Disse vil vise sig nyttige senere.

5.1. Hjælpemetoder

Lad os ændre vores Område klasse.

Lad os først have en metode indeholderPoint til angive, om en given punkt falder inden i eller uden for en regionens areal:

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

Lad os derefter have en metode gør Overlap til angive, om en given område overlapper hinanden område:

public boolean doesOverlap (Region testRegion) {if (testRegion.getX2 () this.getX2 ()) {return false; } hvis (testRegion.getY1 ()> this.getY2 ()) {return false; } hvis (testRegion.getY2 () <this.getY1 ()) {return false; } returner sandt }

Lad os endelig oprette en metode getQuadrant til del et interval i fire lige store kvadranter og returner en specificeret:

offentlig 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); tilfælde 1: returner ny Region (x1, y1 + kvadrantHøjde, x1 + kvadrantBredde, y2); tilfælde 2: returner ny Region (x1 + kvadrantBredde, y1 + kvadrantHøjde, x2, y2); tilfælde 3: returner ny region (x1 + kvadrantBredde, y1, x2, y1 + kvadrantHøjde); } returnere null; }

5.2. Lagring af data

Vi kan nu skrive vores logik til at gemme data. Lad os starte med at definere en ny metode addPoint på den QuadTree klasse for at tilføje et nyt punkt. Denne metode vender tilbage rigtigt hvis et punkt blev tilføjet med succes:

offentlig boolsk addPoint (punktpunkt) {// ...}

Lad os derefter skrive logikken for at håndtere pointen. Først skal vi kontrollere, om punktet er indeholdt inden for QuadTree eksempel. Vi er også nødt til at sikre, at QuadTree instans har ikke nået kapaciteten på MAX_POINTS point.

Hvis begge betingelser er opfyldt, kan vi tilføje det nye punkt:

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

På den anden side, hvis vi har nået MAX_POINTS værdi, så skal vi tilføje det nye punkt til en af ​​underkvadranterne. Til dette løber vi gennem barnet firetræer liste og kalde det samme addPoint metode, der returnerer en rigtigt værdi på vellykket tilføjelse. Derefter forlader vi sløjfen straks som et punkt skal tilføjes nøjagtigt til en kvadrant.

Vi kan indkapsle al denne logik i en hjælpemetode:

privat boolsk addPointToOneQuadrant (punktpunkt) {boolsk isPointAdded; for (int i = 0; i <4; i ++) {isPointAdded = this.quadTrees.get (i) .addPoint (point); hvis (isPointAdded) returner true; } returner falsk; }

Lad os desuden have en praktisk metode createQuadrants at opdele det aktuelle firkant i fire kvadranter:

privat ugyldighed createQuadrants () {Region region; for (int i = 0; i <4; i ++) {region = this.area.getQuadrant (i); quadTrees.add (nyt QuadTree (region)); }}

Vi kalder denne metode til Opret kun kvadranter, hvis vi ikke længere er i stand til at tilføje nye punkter. Dette sikrer, at vores datastruktur bruger optimal hukommelsesplads.

Når vi sætter det hele sammen, har vi opdateringen addPoint metode:

public boolean addPoint (Point point) {if (this.area.containsPoint (point)) {if (this.points.size () <MAX_POINTS) {this.points.add (point); returner sandt; } andet {hvis (this.quadTrees.size () == 0) {createQuadrants (); } returner addPointToOneQuadrant (punkt); }} returner falsk; }

5.3. Søgning efter data

Når vores firtræstruktur er defineret til at gemme data, kan vi nu tænke på logikken til at udføre en søgning.

Da vi leder efter at finde tilstødende genstande, kan vi angiv en searchRegion som udgangspunkt. Derefter kontrollerer vi, om det overlapper med rodområdet. Hvis det gør det, tilføjer vi alle dets børnepunkter, der falder inden i searchRegion.

Efter rodområdet kommer vi ind i hver af kvadranterne og gentager processen. Dette fortsætter, indtil vi når slutningen af ​​træet.

Lad os skrive ovenstående logik som en rekursiv metode i QuadTree klasse:

offentlig Listesøgning (Region searchRegion, List matches) {if (matches == null) {matches = new ArrayList (); } hvis (! this.area.doesOverlap (searchRegion)) {return matches; } andet {for (Punkt punkt: punkter) {hvis (searchRegion.containsPoint (punkt)) {matches.add (punkt); }} hvis (this.quadTrees.size ()> 0) {for (int i = 0; i <4; i ++) {quadTrees.get (i) .search (searchRegion, matches); }}} returner kampe }

6. Testning

Nu hvor vi har vores algoritme på plads, lad os teste den.

6.1. Udfyldning af data

Lad os først udfylde firkantet med de samme 10 koordinater, som vi brugte tidligere:

Region område = ny region (0, 0, 400, 400); QuadTree quadTree = nyt QuadTree (område); flyde [] [] point = ny flyde [] [] {{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 <point.length; i ++) {Point point = new Point (point [i] [0], points [i] [1]); quadTree.addPoint (punkt); }

6.2. Range Search

Lad os derefter udføre en områdesøgning i et område, der er omsluttet af nedre grænse koordinat (200, 200) og øvre grænse koordinat (250, 250):

Region searchArea = ny region (200, 200, 250, 250); Listeresultat = quadTree.search (searchArea, null);

Kørsel af koden giver os en nærliggende koordinat indeholdt i søgeområdet:

[[245.0 , 238.0]]

Lad os prøve et andet søgeområde mellem koordinaterne (0, 0) og (100, 100):

Region searchArea = ny region (0, 0, 100, 100); Listeresultat = quadTree.search (searchArea, null);

Kørsel af koden giver os to nærliggende koordinater til det angivne søgeområde:

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

Vi observerer, at afhængigt af størrelsen på søgeområdet får vi nul, et eller flere point. Så, hvis vi får et punkt og bliver bedt om at finde det nærmeste n naboer, kunne vi definere et passende søgeområde, hvor det givne punkt er i centrum.

Derefter kan vi fra alle de resulterende punkter i søgningen beregne de euklidiske afstande mellem de givne punkter og sorter dem for at få de nærmeste naboer.

7. Tidskompleksitet

Tidskompleksiteten af ​​en rækkeforespørgsel er simpelthen På). Årsagen er, at den i værste fald skal gå gennem hvert emne, hvis det angivne søgeområde er lig med eller større end det befolkede område.

8. Konklusion

I denne artikel forstod vi først begrebet kvadratree ved at sammenligne det med et binært træ. Dernæst så vi, hvordan det kan bruges effektivt til at gemme data spredt over et todimensionelt rum.

Vi så så, hvordan man lagrer data og udfører en rækkevidde.

Som altid er kildekoden med tests tilgængelig på GitHub.