Algorithme de recherche par plage en Java

1. Vue d'ensemble

Dans ce didacticiel, nous allons explorer le concept de recherche de voisins dans un espace à deux dimensions . Ensuite, nous allons parcourir son implémentation en Java.

2. Recherche unidimensionnelle vs recherche bidimensionnelle

Nous savons que la recherche binaire est un algorithme efficace pour trouver une correspondance exacte dans une liste d'éléments en utilisant une approche de division et de conquête.

Considérons maintenant une zone bidimensionnelle où chaque élément est représenté par des coordonnées XY (points) dans un plan .

Cependant, au lieu d'une correspondance exacte, supposons que nous voulions trouver des voisins d'un point donné dans le plan. Il est clair que si nous voulons les n correspondances les plus proches , la recherche binaire ne fonctionnera pas . En effet, la recherche binaire peut comparer deux éléments sur un seul axe, alors que nous devons pouvoir les comparer sur deux axes.

Nous examinerons une alternative à la structure de données de l'arborescence binaire dans la section suivante.

3. Quadtree

Un quadtree est une structure de données d'arbre spatial dans laquelle chaque nœud a exactement quatre enfants. Chaque enfant peut être un point ou une liste contenant quatre sous-quadtrees.

Un point stocke des données - par exemple, les coordonnées XY. Une région représente une limite fermée à l'intérieur de laquelle un point peut être stocké. Il est utilisé pour définir la zone de portée d'un arbre quaternaire.

Comprenons cela davantage en utilisant un exemple de 10 coordonnées dans un ordre arbitraire:

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

Les trois premières valeurs seront stockées sous forme de points sous le nœud racine, comme indiqué dans l'image la plus à gauche.

Le nœud racine ne peut pas accueillir de nouveaux points maintenant car il a atteint sa capacité de trois points. Par conséquent, nous allons diviser la région du nœud racine en quatre quadrants égaux .

Chacun de ces quadrants peut stocker trois points et contenir en outre quatre quadrants dans sa limite. Cela peut être fait de manière récursive, ce qui donne un arbre de quadrants, où la structure de données de l'arbre quaternaire tire son nom.

Dans l'image du milieu ci-dessus, nous pouvons voir les quadrants créés à partir du nœud racine et comment les quatre points suivants sont stockés dans ces quadrants.

Enfin, l'image la plus à droite montre comment un quadrant est à nouveau subdivisé pour accueillir plus de points dans cette région tandis que les autres quadrants peuvent encore accepter les nouveaux points.

Nous allons maintenant voir comment implémenter cet algorithme en Java.

4. Structure des données

Créons une structure de données quadtree. Nous aurons besoin de trois classes de domaine.

Tout d'abord, nous allons créer une classe Point pour stocker les coordonnées XY :

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

Deuxièmement, créons une classe Region pour définir les limites d'un quadrant :

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

Enfin, ayons une classe QuadTree pour stocker les données en tant qu'instances Point et les enfants en tant que classes 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; } }

Pour instancier un objet QuadTree , nous spécifions sa zone à l'aide de la classe Region via le constructeur.

5. Algorithme

Avant d'écrire notre logique de base pour stocker des données, ajoutons quelques méthodes d'aide. Ceux-ci s'avéreront utiles plus tard.

5.1. Méthodes d'assistance

Modifions notre classe Region .

Tout d'abord, nous allons avoir une méthode containsPoint pour indiquer si un point donné se situe à l'intérieur ou à l'extérieur de la zone d'une région :

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

Ensuite, nous allons avoir une méthode doOverlap pour indiquer si une région donnée chevauche une autre région :

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

Enfin, créons une méthode getQuadrant pour diviser une plage en quatre quadrants égaux et en renvoyer un spécifié:

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. Stocker des données

Nous pouvons maintenant écrire notre logique pour stocker des données. Commençons par définir une nouvelle méthode addPoint sur la classe QuadTree pour ajouter un nouveau point. Cette méthode retournera true si un point a été ajouté avec succès:

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

Ensuite, écrivons la logique pour gérer le point. Tout d'abord, nous devons vérifier si le point est contenu dans la limite de l' instance QuadTree . Nous devons également nous assurer que l' instance QuadTree n'a pas atteint la capacité de MAX_POINTS points.

Si les deux conditions sont remplies, nous pouvons ajouter le nouveau point:

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

Dans cet article, nous avons d'abord compris le concept d'arbre quaternaire en le comparant à un arbre binaire. Ensuite, nous avons vu comment il peut être utilisé efficacement pour stocker des données réparties dans un espace bidimensionnel.

Nous avons ensuite vu comment stocker des données et effectuer une recherche par plage.

Comme toujours, le code source avec des tests est disponible à l'adresse over sur GitHub.