streamalism.org

1. Overzicht

In deze tutorial verkennen we het concept van zoeken naar buren in een tweedimensionale ruimte. Vervolgens zullen we de implementatie ervan in Java doorlopen.

2. Eendimensionaal zoeken versus tweedimensionaal zoeken

We weten dat binair zoeken een efficiënt algoritme is voor het vinden van een exacte overeenkomst in een lijst met items met behulp van een verdeel-en-heersbenadering.

Laten we nu beschouw een tweedimensionaal gebied waar elk item wordt weergegeven door XY-coördinaten (punten) in een vlak.

Stel dat we, in plaats van een exacte match, buren van een bepaald punt in het vlak willen vinden. Het is duidelijk dat als we het dichtstbijzijnde willen n overeenkomsten, dan zal de binaire zoekopdracht niet werken. Dit komt doordat de binaire zoekopdracht twee items op slechts één as kan vergelijken, terwijl we ze op twee assen moeten kunnen vergelijken.

We zullen in de volgende sectie naar een alternatief voor de binaire boomgegevensstructuur kijken.

3. Quadtree

Een quadtree is een ruimtelijke datastructuur waarin elk knooppunt precies vier kinderen heeft. Elk kind kan een punt zijn of een lijst met vier subkwadraten.

EEN punt slaat gegevens op - bijvoorbeeld XY-coördinaten. EEN regio vertegenwoordigt een gesloten grens waarbinnen een punt kan worden opgeslagen. Het wordt gebruikt om het bereik van een quadtree te definiëren.

Laten we dit beter begrijpen aan de hand van een voorbeeld van 10 coördinaten in een willekeurige volgorde:

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

De eerste drie waarden worden opgeslagen als punten onder het hoofdknooppunt, zoals weergegeven in de meest linkse afbeelding.

Het hoofdknooppunt kan nu geen nieuwe punten herbergen omdat het zijn capaciteit van drie punten heeft bereikt. Daarom zullen we verdeel het gebied van het hoofdknooppunt in vier gelijke kwadranten.

Elk van deze kwadranten kan drie punten opslaan en bovendien vier kwadranten binnen zijn grens bevatten. Dit kan recursief worden gedaan, wat resulteert in een boom van kwadranten, waar de quadtree datastructuur zijn naam aan ontleent.

In de middelste afbeelding hierboven kunnen we de kwadranten zien die zijn gemaakt op basis van het hoofdknooppunt en hoe de volgende vier punten in deze kwadranten worden opgeslagen.

Ten slotte laat de meest rechtse afbeelding zien hoe een kwadrant weer wordt onderverdeeld om meer punten in dat gebied te kunnen accommoderen terwijl de andere kwadranten de nieuwe punten nog kunnen accepteren.

We zullen nu zien hoe dit algoritme in Java kan worden geïmplementeerd.

4. Gegevensstructuur

Laten we een quadtree-datastructuur maken. We hebben drie domeinklassen nodig.

Ten eerste maken we een Punt class om de XY-coördinaten op te slaan:

openbare klasse Point {private float x; privé float y; openbaar punt (float x, float y) {this.x = x; this.y = y; } // getters & toString ()}

Ten tweede, laten we een Regio klasse om de grenzen van een kwadrant te definiëren:

openbare klasse Regio {privé float x1; privé vlotter y1; privé vlotter x2; privé vlotter y2; openbare regio (float x1, float y1, float x2, float y2) {this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; } // getters & toString ()}

Laten we tot slot een QuadTree klasse om gegevens op te slaan als Punt instanties en kinderen als QuadTree klassen:

openbare klasse QuadTree {privé statische laatste int MAX_POINTS = 3; privéregio gebied; private List points = nieuwe ArrayList (); privélijst quadTrees = nieuwe ArrayList (); openbare QuadTree (regiogebied) {this.area = area; }}

Om een QuadTree object, specificeren we zijn Oppervlakte de ... gebruiken Regio klasse via de constructor.

5. Algoritme

Voordat we onze kernlogica schrijven om gegevens op te slaan, laten we een paar hulpmethoden toevoegen. Deze zullen later nuttig blijken.

5.1. Helper-methoden

Laten we onze Regio klasse.

Laten we eerst een methode hebben bevatPoint naar aangeven of een gegeven punt valt binnen of buiten een Regio's Oppervlakte:

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

Laten we vervolgens een methode hebben overlapt naar aangeven of een gegeven regio overlapt met een ander regio:

openbare boolean doesOverlap (Regio testRegion) {if (testRegion.getX2 () this.getX2 ()) {return false; } if (testRegion.getY1 ()> this.getY2 ()) {return false; } if (testRegion.getY2 () <this.getY1 ()) {return false; } retourneren waar; }

Laten we tot slot een methode maken getQuadrant naar verdeel een bereik in vier gelijke kwadranten en retourneer een gespecificeerde:

openbare regio getQuadrant (int quadrantIndex) {float quadrantWidth = (this.x2 - this.x1) / 2; zwevende kwadrantHeight = (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); geval 1: retourneer nieuwe regio (x1, y1 + quadrantHeight, x1 + quadrantWidth, y2); geval 2: retourneer nieuwe regio (x1 + quadrantWidth, y1 + quadrantHeight, x2, y2); geval 3: retourneer nieuwe regio (x1 + quadrantWidth, y1, x2, y1 + quadrantHeight); } retourneer null; }

5.2. Gegevens bewaren

We kunnen nu onze logica schrijven om gegevens op te slaan. Laten we beginnen met het definiëren van een nieuwe methode addPoint op de QuadTree class om een ​​nieuw punt. Deze methode zal terugkeren waar als een punt succesvol is toegevoegd:

openbare boolean addPoint (puntpunt) {// ...}

Laten we vervolgens de logica schrijven om het punt af te handelen. Eerst moeten we controleren of het punt zich binnen de grens van de QuadTree voorbeeld. We moeten er ook voor zorgen dat de QuadTree instantie heeft de capaciteit van niet bereikt MAX_POINTS punten.

Als aan beide voorwaarden is voldaan, kunnen we het nieuwe punt toevoegen:

if (this.area.containsPoint (punt)) {if (this.points.size () <MAX_POINTS) {this.points.add (punt); terugkeer waar; }}

Aan de andere kant, als we de MAX_POINTS waarde, dan moeten we het nieuwe toevoegen punt naar een van de subkwadranten. Hiervoor lopen we door het kind quadTrees lijst en roep hetzelfde addPoint methode die een waar waarde op succesvolle toevoeging. Dan verlaten we de lus onmiddellijk als een punt moet exact bij één kwadrant worden opgeteld.

We kunnen al deze logica inkapselen in een hulpmethode:

private boolean addPointToOneQuadrant (Point point) {boolean isPointAdded; voor (int i = 0; i <4; i ++) {isPointAdded = this.quadTrees.get (i) .addPoint (punt); if (isPointAdded) retourneert waar; } return false; }

Laten we bovendien een handige methode hebben createQuadrants om het huidige kwadranten onder te verdelen in vier kwadranten:

private void createQuadrants () {Regio regio; voor (int i = 0; i <4; i ++) {region = this.area.getQuadrant (i); quadTrees.add (nieuwe QuadTree (regio)); }}

We noemen deze methode maak alleen kwadranten als we geen nieuwe punten meer kunnen toevoegen. Dit zorgt ervoor dat onze datastructuur optimale geheugenruimte gebruikt.

Alles bij elkaar: we hebben de update addPoint methode:

openbare boolean addPoint (punt punt) {if (this.area.containsPoint (punt)) {if (this.points.size () <MAX_POINTS) {this.points.add (punt); terugkeer waar; } else {if (this.quadTrees.size () == 0) {createQuadrants (); } retourneer addPointToOneQuadrant (punt); }} return false; }

5.3. Gegevens zoeken

Nu onze quadtree-structuur is gedefinieerd om gegevens op te slaan, kunnen we nu de logica bedenken voor het uitvoeren van een zoekopdracht.

Omdat we op zoek zijn naar aangrenzende items, kunnen we dat specificeer een searchRegion als uitgangspunt. Vervolgens controleren we of het overlapt met de wortelregio. Als dit het geval is, voegen we alle onderliggende punten toe die binnen de searchRegion.

Na de wortelregio komen we in elk van de kwadranten en herhalen we het proces. Dit gaat door tot we het einde van de boom bereiken.

Laten we de bovenstaande logica schrijven als een recursieve methode in de QuadTree klasse:

openbare lijst zoeken (regio zoekregio, lijst overeenkomsten) {if (overeenkomsten == null) {overeenkomsten = nieuwe ArrayList (); } if (! this.area.doesOverlap (searchRegion)) {return overeenkomsten; } 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 (zoekregio, overeenkomsten); }}} return matches; }

6. Testen

Nu we ons algoritme hebben ingevoerd, gaan we het testen.

6.1. De gegevens vullen

Laten we eerst de quadtree vullen met dezelfde 10 coördinaten die we eerder hebben gebruikt:

Regio gebied = nieuwe regio (0, 0, 400, 400); QuadTree quadTree = nieuwe QuadTree (gebied); float [] [] punten = nieuwe float [] [] {{21, 25}, {55, 53}, {70, 318}, {98, 302}, {49, 229}, {135, 229}, {224, 292}, {206, 321}, {197, 258}, {245, 238}}; voor (int i = 0; i <punten.lengte; i ++) {Punt punt = nieuw punt (punten [i] [0], punten [i] [1]); quadTree.addPoint (punt); }

6.2. Bereik zoeken

Laten we vervolgens een bereikzoekopdracht uitvoeren in een gebied dat wordt omsloten door ondergrenscoördinaat (200, 200) en bovengrenscoördinaat (250, 250):

Regio searchArea = nieuwe regio (200, 200, 250, 250); Lijstresultaat = quadTree.search (searchArea, null);

Als u de code uitvoert, krijgen we een coördinaat in de buurt in het zoekgebied:

[[245.0 , 238.0]]

Laten we een ander zoekgebied proberen tussen coördinaten (0, 0) en (100, 100):

Regio searchArea = nieuwe regio (0, 0, 100, 100); Lijstresultaat = quadTree.search (searchArea, null);

Als u de code uitvoert, krijgen we twee coördinaten in de buurt voor het opgegeven zoekgebied:

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

We stellen vast dat we, afhankelijk van de grootte van het zoekgebied, nul, een of meerdere punten krijgen. Zo, als we een punt krijgen en wordt gevraagd om het dichtstbijzijnde te vinden n buren, zouden we een geschikt zoekgebied kunnen definiëren waar het opgegeven punt in het midden is.

Dan kunnen we van alle resulterende punten van de zoekbewerking bereken de Euclidische afstanden tussen de gegeven punten en sorteer ze om de dichtstbijzijnde buren te krijgen.

7. Tijdscomplexiteit

De tijdcomplexiteit van een bereikquery is eenvoudig Aan). De reden is dat het in het ergste geval elk item moet doorlopen als het opgegeven zoekgebied gelijk is aan of groter is dan het bevolkte gebied.

8. Conclusie

In dit artikel hebben we eerst het concept van een quadtree begrepen door het te vergelijken met een binaire boom. Vervolgens hebben we gezien hoe het efficiënt kan worden gebruikt om gegevens verspreid over een tweedimensionale ruimte op te slaan.

We hebben toen gezien hoe we gegevens konden opslaan en een bereikzoekopdracht konden uitvoeren.

Zoals altijd is de broncode met tests beschikbaar op GitHub.