Bereichssuchalgorithmus in Java

1. Übersicht

In diesem Tutorial untersuchen wir das Konzept der Suche nach Nachbarn in einem zweidimensionalen Raum . Anschließend werden wir die Implementierung in Java durchgehen.

2. Eindimensionale Suche vs zweidimensionale Suche

Wir wissen, dass die binäre Suche ein effizienter Algorithmus ist, um mithilfe eines Divide-and-Conquer-Ansatzes eine genaue Übereinstimmung in einer Liste von Elementen zu finden.

Betrachten wir nun einen zweidimensionalen Bereich, in dem jedes Element durch XY-Koordinaten (Punkte) in einer Ebene dargestellt wird .

Angenommen, wir möchten anstelle einer exakten Übereinstimmung Nachbarn eines bestimmten Punkts in der Ebene finden. Es ist klar, dass die binäre Suche nicht funktioniert , wenn wir die nächsten n Übereinstimmungen wollen . Dies liegt daran, dass die binäre Suche nur zwei Elemente auf einer Achse vergleichen kann, während wir sie auf zwei Achsen vergleichen können müssen.

Wir werden uns im nächsten Abschnitt eine Alternative zur Datenstruktur des Binärbaums ansehen.

3. Quadtree

Ein Quadtree ist eine räumliche Baumdatenstruktur, in der jeder Knoten genau vier Kinder hat. Jedes Kind kann entweder ein Punkt oder eine Liste sein, die vier Teilbäume enthält.

Ein Punkt speichert Daten - zum Beispiel XY-Koordinaten. Eine Region stellt eine geschlossene Grenze dar, innerhalb derer ein Punkt gespeichert werden kann. Es wird verwendet, um den Reichweitebereich eines Quadtree zu definieren.

Lassen Sie uns dies anhand eines Beispiels von 10 Koordinaten in beliebiger Reihenfolge besser verstehen:

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

Die ersten drei Werte werden als Punkte unter dem Wurzelknoten gespeichert, wie im Bild ganz links gezeigt.

Der Stammknoten kann jetzt keine neuen Punkte aufnehmen, da er seine Kapazität von drei Punkten erreicht hat. Daher teilen wir den Bereich des Wurzelknotens in vier gleiche Quadranten .

Jeder dieser Quadranten kann drei Punkte speichern und zusätzlich vier Quadranten innerhalb seiner Grenze enthalten. Dies kann rekursiv erfolgen, was zu einem Quadrantenbaum führt, in dem die Quadtree-Datenstruktur ihren Namen erhält.

Im mittleren Bild oben sehen wir die aus dem Wurzelknoten erstellten Quadranten und wie die nächsten vier Punkte in diesen Quadranten gespeichert werden.

Schließlich zeigt das Bild ganz rechts, wie ein Quadrant erneut unterteilt wird, um mehr Punkte in dieser Region aufzunehmen, während die anderen Quadranten die neuen Punkte noch akzeptieren können.

Wir werden nun sehen, wie dieser Algorithmus in Java implementiert wird.

4. Datenstruktur

Erstellen wir eine Quadtree-Datenstruktur. Wir benötigen drei Domainklassen.

Zunächst erstellen wir eine Point- Klasse zum Speichern der XY-Koordinaten :

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

Zweitens erstellen wir eine Region- Klasse, um die Grenzen eines Quadranten zu definieren :

public class Region { private float x1; private float y1; private float x2; private float 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() }

Schließlich werfen sie einen hat Quadtree Klasse zum Speichern von Daten als Punkt - Instanzen und Kinder als Quadtree Klassen :

public class QuadTree { private static final int MAX_POINTS = 3; private Region area; private List points = new ArrayList(); private List quadTrees = new ArrayList(); public QuadTree(Region area) { this.area = area; } }

Um ein QuadTree- Objekt zu instanziieren , geben wir seinen Bereich mithilfe der Region- Klasse über den Konstruktor an.

5. Algorithmus

Bevor wir unsere Kernlogik zum Speichern von Daten schreiben, fügen wir einige Hilfsmethoden hinzu. Diese werden sich später als nützlich erweisen.

5.1. Hilfsmethoden

Lassen Sie uns unsere Region- Klasse ändern .

Lassen Sie uns zunächst eine Methode mitPoint angeben, um anzugeben, ob ein bestimmter Punkt innerhalb oder außerhalb des Bereichs einer Region liegt :

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

Lassen Sie uns als Nächstes eine Methode " DoesOverlap" verwenden, um anzugeben, ob sich eine bestimmte Region mit einer anderen Region überschneidet :

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

Zuletzt erstellen wir eine Methode getQuadrant , um einen Bereich in vier gleiche Quadranten zu unterteilen und einen angegebenen zurückzugeben:

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 switch (quadrantIndex) { case 0: return new Region(x1, y1, x1 + quadrantWidth, y1 + quadrantHeight); case 1: return new Region(x1, y1 + quadrantHeight, x1 + quadrantWidth, y2); case 2: return new Region(x1 + quadrantWidth, y1 + quadrantHeight, x2, y2); case 3: return new Region(x1 + quadrantWidth, y1, x2, y1 + quadrantHeight); } return null; }

5.2. Daten speichern

Wir können jetzt unsere Logik schreiben, um Daten zu speichern. Beginnen wir mit der Definition einer neuen Methode addPoint in der QuadTree- Klasse, um einen neuen Punkt hinzuzufügen . Diese Methode gibt true zurück, wenn ein Punkt erfolgreich hinzugefügt wurde:

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

Als nächstes schreiben wir die Logik, um den Punkt zu behandeln. Zunächst müssen wir überprüfen, ob der Punkt innerhalb der Grenze der QuadTree- Instanz enthalten ist. Wir müssen auch sicherstellen, dass die QuadTree- Instanz nicht die Kapazität von MAX_POINTS- Punkten erreicht hat.

Wenn beide Bedingungen erfüllt sind, können wir den neuen Punkt hinzufügen:

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

On the other hand, if we've reached the MAX_POINTS value, then we need to add the new point to one of the sub-quadrants. For this, we loop through the child quadTrees list and call the same addPoint method which will return a true value on successful addition. Then we exit the loop immediately as a point needs to be added exactly to one quadrant.

We can encapsulate all this logic inside a helper method:

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

Additionally, let's have a handy method createQuadrants to subdivide the current quadtree into four quadrants:

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

We'll call this method to create quadrants only if we're no longer able to add any new points. This ensures that our data structure uses optimum memory space.

Putting it all together, we've got the updated addPoint method:

public boolean addPoint(Point point) { 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(point); } } return false; }

5.3. Searching Data

Having our quadtree structure defined to store data, we can now think of the logic for performing a search.

As we're looking for finding adjacent items, we can specify a searchRegion as the starting point. Then, we check if it overlaps with the root region. If it does, then we add all its child points that fall inside the searchRegion.

After the root region, we get into each of the quadrants and repeat the process. This goes on until we reach the end of the tree.

Let's write the above logic as a recursive method in the QuadTree class:

public List search(Region searchRegion, List matches) { 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, matches); } } } return matches; }

6. Testing

Now that we have our algorithm in place, let's test it.

6.1. Populating the Data

First, let's populate the quadtree with the same 10 coordinates we used earlier:

Region area = new Region(0, 0, 400, 400); QuadTree quadTree = new QuadTree(area); float[][] points = new 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++) { Point point = new Point(points[i][0], points[i][1]); quadTree.addPoint(point); }

6.2. Range Search

Next, let's perform a range search in an area enclosed by lower bound coordinate (200, 200) and upper bound coordinate (250, 250):

Region searchArea = new Region(200, 200, 250, 250); List result = quadTree.search(searchArea, null);

Running the code will give us one nearby coordinate contained within the search area:

[[245.0 , 238.0]]

Let's try a different search area between coordinates (0, 0) and (100, 100):

Region searchArea = new Region(0, 0, 100, 100); List result = quadTree.search(searchArea, null);

Running the code will give us two nearby coordinates for the specified search area:

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

We observe that depending on the size of the search area, we get zero, one or many points. So, if we're given a point and asked to find the nearest n neighbors, we could define a suitable search area where the given point is at the center.

Then, from all the resulting points of the search operation, we can calculate the Euclidean distances between the given points and sort them to get the nearest neighbors.

7. Time Complexity

The time complexity of a range query is simply O(n). The reason is that, in the worst-case scenario, it has to traverse through each item if the search area specified is equal to or bigger than the populated area.

8. Conclusion

In diesem Artikel haben wir zunächst das Konzept eines Quadtree verstanden, indem wir ihn mit einem Binärbaum verglichen haben. Als nächstes haben wir gesehen, wie es effizient zum Speichern von Daten verwendet werden kann, die über einen zweidimensionalen Raum verteilt sind.

Wir haben dann gesehen, wie Daten gespeichert und eine Bereichssuche durchgeführt werden.

Wie immer ist der Quellcode mit Tests auf GitHub verfügbar.