streamalism.org

1. Oversikt

I denne opplæringen vil vi utforske begrepet søker etter naboer i et todimensjonalt rom. Deretter går vi gjennom implementeringen i Java.

2. Endimensjonalt søk vs todimensjonalt søk

Vi vet at binært søk er en effektiv algoritme for å finne en nøyaktig samsvar i en liste over elementer ved hjelp av en del-og-erobre tilnærming.

La oss nå vurder et todimensjonalt område der hvert element er representert av XY-koordinater (punkter) i et plan.

Imidlertid, i stedet for en nøyaktig samsvar, anta at vi vil finne naboer til et gitt punkt i flyet. Det er klart det hvis vi vil ha det nærmeste n samsvarer, så fungerer ikke det binære søket. Dette er fordi det binære søket bare kan sammenligne to elementer i en akse, mens vi må kunne sammenligne dem i to akser.

Vi ser på et alternativ til datastrukturen for binært tre i neste avsnitt.

3. Quadtree

Et kvadratree er en romlig tredatastruktur der hver node har nøyaktig fire barn. Hvert barn kan enten være et poeng eller en liste som inneholder fire under-kvadrater.

EN punkt lagrer data - for eksempel XY-koordinater. EN region representerer en lukket grense der et punkt kan lagres. Den brukes til å definere rekkevidden til et firetre.

La oss forstå dette mer ved å bruke et eksempel på 10 koordinater i en vilkårlig rekkefølge:

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

De tre første verdiene lagres som punkter under rotnoden som vist på bildet til venstre.

Rotnoden kan ikke imøtekomme nye punkter nå, siden den har nådd kapasiteten på tre poeng. Derfor vil vi dele regionen til rotnoden i fire like kvadranter.

Hver av disse kvadranter kan lagre tre punkter og i tillegg inneholde fire kvadranter innenfor grensen. Dette kan gjøres rekursivt, noe som resulterer i et tre med kvadranter, det er der datatreet datastrukturen får navnet sitt.

På det midtre bildet over kan vi se kvadranter opprettet fra rotnoden og hvordan de neste fire punktene er lagret i disse kvadrantene.

Til slutt viser det høyeste bildet hvordan en kvadrant igjen er delt inn for å få plass til flere poeng i den regionen, mens de andre kvadrantene fremdeles kan akseptere de nye punktene.

Vi får nå se hvordan vi implementerer denne algoritmen i Java.

4. Datastruktur

La oss lage en datastruktur for firetre. Vi trenger tre domeneklasser.

For det første lager vi en Punkt klasse for å lagre XY-koordinatene:

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

For det andre, la oss lage en Region klasse for å definere grensene til en kvadrant:

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

Til slutt, la oss ha en QuadTree klasse for å lagre data som Punkt tilfeller og barn som QuadTree klasser:

offentlig klasse QuadTree {privat statisk finale int MAX_POINTS = 3; private Region området; private List poeng = ny ArrayList (); privat liste quadTrees = ny ArrayList (); offentlig QuadTree (Region area) {this.area = area; }}

Å instansiere en QuadTree objekt, spesifiserer vi dens område bruker Region klasse gjennom konstruktøren.

5. Algoritme

Før vi skriver kjernelogikken vår for å lagre data, la oss legge til noen hjelpemetoder. Disse vil vise seg nyttige senere.

5.1. Hjelpemetoder

La oss endre vår Region klasse.

For det første, la oss ha en metode inneholderPoint til angi om en gitt punkt faller innenfor eller utenfor en regionens område:

offentlig boolsk inneholderPoint (Point point) {retur point.getX ()> = this.x1 && point.getX () = this.y1 && point.getY () <this.y2; }

Deretter, la oss ha en metode overlapper til angi om en gitt region overlapper med en annen region:

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 sant; }

Til slutt, la oss lage en metode getQuadrant til del et område i fire like kvadranter og returner en spesifisert:

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-bryter (kvadrantIndex) {tilfelle 0: returner ny region (x1, y1, x1 + kvadrantBredde, y1 + kvadrantHøyde); tilfelle 1: returner ny Region (x1, y1 + kvadrantHøyde, x1 + kvadrantBredde, y2); tilfelle 2: returner ny Region (x1 + kvadrantBredde, y1 + kvadrantHøyde, x2, y2); tilfelle 3: returner ny Region (x1 + kvadrantBredde, y1, x2, y1 + kvadrantHøyde); } returner null; }

5.2. Lagring av data

Vi kan nå skrive logikken vår for å lagre data. La oss starte med å definere en ny metode addPoint på QuadTree klasse for å legge til en ny punkt. Denne metoden vil komme tilbake ekte hvis et punkt ble lagt til:

offentlig boolsk addPoint (Point point) {// ...}

Deretter, la oss skrive logikken for å håndtere poenget. Først må vi sjekke om punktet er innenfor rammen av QuadTree forekomst. Vi må også sørge for at QuadTree forekomst har ikke nådd kapasiteten MAX_POINTS poeng.

Hvis begge vilkårene er oppfylt, kan vi legge til det nye punktet:

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

På den andre siden, hvis vi har nådd MAX_POINTS verdi, så må vi legge til det nye punkt til en av underkvadrantene. For dette løper vi gjennom barnet firetre liste opp og ring det samme addPoint metode som vil returnere a ekte verdi på vellykket tillegg. Så går vi ut av løkken umiddelbart som et punkt må legges nøyaktig til en kvadrant.

Vi kan kapsle inn all denne logikken i en hjelpemetode:

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

I tillegg, la oss ha en praktisk metode createQuadrants å dele den nåværende firetreet i fire kvadranter:

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

Vi vil kalle denne metoden til lage kvadranter bare hvis vi ikke lenger er i stand til å legge til nye poeng. Dette sikrer at datastrukturen bruker optimal minne.

Når vi setter alt sammen, har vi oppdatert addPoint metode:

offentlig boolsk addPoint (Point point) {if (this.area.containsPoint (point)) {if (this.points.size () <MAX_POINTS) {this.points.add (point); returner sant; } annet {if (this.quadTrees.size () == 0) {createQuadrants (); } returner addPointToOneQuadrant (punkt); }} returner falsk; }

5.3. Søker etter data

Når vi har definert kvadratstrestrukturen vår for å lagre data, kan vi nå tenke på logikken for å utføre et søk.

Når vi leter etter å finne tilstøtende gjenstander, kan vi spesifiser en søk Region som utgangspunkt. Deretter sjekker vi om den overlapper med rotområdet. Hvis det gjør det, legger vi til alle barnepunktene som faller inne i searchRegion.

Etter rotområdet kommer vi inn i hver av kvadrantene og gjentar prosessen. Dette fortsetter til vi når enden av treet.

La oss skrive ovennevnte logikk som en rekursiv metode i QuadTree klasse:

public List search (Region searchRegion, List matches) {if (matches == null) {matches = new ArrayList (); } hvis (! this.area.doesOverlap (searchRegion)) {return matches; } annet {for (Point point: points) {if (searchRegion.containsPoint (point)) {matches.add (point); }} hvis (this.quadTrees.size ()> 0) {for (int i = 0; i <4; i ++) {quadTrees.get (i) .search (searchRegion, matches); }}} returnerer kamper; }

6. Testing

Nå som vi har algoritmen på plass, la oss teste den.

6.1. Fyll ut dataene

La oss først fylle firetreet med de samme 10 koordinatene vi brukte tidligere:

Region area = new Region (0, 0, 400, 400); QuadTree quadTree = nytt QuadTree (område); flyte [] [] poeng = ny flyte [] [] {{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 <poeng.lengde; i ++) {Punkt punkt = nytt punkt (punkt [i] [0], punkt [i] [1]); quadTree.addPoint (punkt); }

6.2. Områdesøk

Deretter la oss utføre et områdesøk i et område innelukket av nedre grense koordinat (200, 200) og øvre grense koordinat (250, 250):

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

Å kjøre koden vil gi oss en nærliggende koordinat i søkeområdet:

[[245.0 , 238.0]]

La oss prøve et annet søkeområde mellom koordinatene (0, 0) og (100, 100):

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

Å kjøre koden vil gi oss to nærliggende koordinater for det angitte søkeområdet:

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

Vi observerer at avhengig av størrelsen på søkeområdet, får vi null, ett eller flere poeng. Så, hvis vi får poeng og blir bedt om å finne det nærmeste n naboer, kunne vi definere et passende søkeområde der det gitte punktet er i sentrum.

Så, fra alle de resulterende punktene i søkeoperasjonen, kan vi beregne de euklidiske avstandene mellom de gitte punktene og sorter dem for å få de nærmeste naboene.

7. Tidskompleksitet

Tidskompleksiteten til en rekkeforespørsel er ganske enkelt På). Årsaken er at den i verste fall må krysse gjennom hvert element hvis det angitte søkeområdet er lik eller større enn det befolkede området.

8. Konklusjon

I denne artikkelen forsto vi først begrepet et firetre ved å sammenligne det med et binært tre. Deretter så vi hvordan den kan brukes effektivt til å lagre data spredt over et todimensjonalt rom.

Vi så hvordan vi lagrer data og utfører et områdesøk.

Som alltid er kildekoden med tester tilgjengelig på GitHub.