Algoritmo di ricerca intervallo in Java

1. Panoramica

In questo tutorial, esploreremo il concetto di ricerca dei vicini in uno spazio bidimensionale . Quindi, esamineremo la sua implementazione in Java.

2. Ricerca unidimensionale vs ricerca bidimensionale

Sappiamo che la ricerca binaria è un algoritmo efficiente per trovare una corrispondenza esatta in un elenco di elementi utilizzando un approccio divide et impera.

Consideriamo ora un'area bidimensionale in cui ogni elemento è rappresentato da coordinate XY (punti) in un piano .

Tuttavia, invece di una corrispondenza esatta, supponiamo di voler trovare i vicini di un dato punto nel piano. È chiaro che se vogliamo le n corrispondenze più vicine , la ricerca binaria non funzionerà . Questo perché la ricerca binaria può confrontare due elementi su un solo asse, mentre dobbiamo essere in grado di confrontarli su due assi.

Vedremo un'alternativa alla struttura dei dati ad albero binario nella sezione successiva.

3. Quadtree

Un quadtree è una struttura di dati ad albero spaziale in cui ogni nodo ha esattamente quattro figli. Ogni bambino può essere un punto o un elenco contenente quattro sottoquadri.

Un punto memorizza i dati, ad esempio le coordinate XY. Una regione rappresenta un confine chiuso entro il quale è possibile memorizzare un punto. Viene utilizzato per definire l'area di portata di un quadtree.

Comprendiamolo meglio usando un esempio di 10 coordinate in un ordine arbitrario:

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

I primi tre valori verranno memorizzati come punti sotto il nodo radice come mostrato nell'immagine più a sinistra.

Il nodo radice non può accogliere nuovi punti ora poiché ha raggiunto la sua capacità di tre punti. Pertanto, divideremo la regione del nodo radice in quattro quadranti uguali .

Ciascuno di questi quadranti può memorizzare tre punti e inoltre contenere quattro quadranti all'interno del suo confine. Questo può essere fatto in modo ricorsivo, risultando in un albero di quadranti, da cui prende il nome la struttura dati a quattro alberi.

Nell'immagine centrale sopra, possiamo vedere i quadranti creati dal nodo radice e come i successivi quattro punti vengono memorizzati in questi quadranti.

Infine, l'immagine più a destra mostra come un quadrante sia nuovamente suddiviso per accogliere più punti in quella regione mentre gli altri quadranti possono ancora accettare i nuovi punti.

Vedremo ora come implementare questo algoritmo in Java.

4. Struttura dei dati

Creiamo una struttura dati a quattro alberi. Avremo bisogno di tre classi di dominio.

Innanzitutto, creeremo una classe Point per memorizzare le coordinate XY :

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

In secondo luogo, creiamo una classe Region per definire i confini di un quadrante :

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() }

Infine, disponiamo di una classe QuadTree per memorizzare i dati come istanze Point e figli come classi QuadTree :

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

Per istanziare un oggetto QuadTree , specifichiamo la sua area utilizzando la classe Region tramite il costruttore.

5. Algoritmo

Prima di scrivere la nostra logica di base per archiviare i dati, aggiungiamo alcuni metodi di supporto. Questi si riveleranno utili in seguito.

5.1. Metodi di aiuto

Modifichiamo la nostra classe Region .

In primo luogo, diamo un metodo containsPoint per indicare se un determinato punto cade all'interno o all'esterno di una regione zona :

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

Successivamente, disponiamo di un metodo doesOverlap per indicare se una data regione si sovrappone a un'altra regione :

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

Infine, creiamo un metodo getQuadrant per dividere un intervallo in quattro quadranti uguali e restituirne uno specificato:

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. Archiviazione dei dati

Ora possiamo scrivere la nostra logica per memorizzare i dati. Cominciamo definendo un nuovo metodo addPoint sulla classe QuadTree per aggiungere un nuovo punto. Questo metodo restituirà true se un punto è stato aggiunto con successo:

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

Quindi, scriviamo la logica per gestire il punto. Innanzitutto, dobbiamo verificare se il punto è contenuto all'interno del confine dell'istanza QuadTree . Dobbiamo anche assicurarci che l' istanza QuadTree non abbia raggiunto la capacità di MAX_POINTS punti.

Se entrambe le condizioni sono soddisfatte, possiamo aggiungere il nuovo punto:

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 questo articolo, abbiamo prima compreso il concetto di un albero quadruplo confrontandolo con un albero binario. Successivamente, abbiamo visto come può essere utilizzato in modo efficiente per archiviare dati distribuiti in uno spazio bidimensionale.

Abbiamo quindi visto come memorizzare i dati ed eseguire una ricerca per intervallo.

Come sempre, il codice sorgente con i test è disponibile su GitHub.