[GRAPHES ?] Structure pour stocker des rectangles

Voici mon problème: j'ai besoin de mémoriser un grand nombre de rectangles, de dimensions diverses, et surtout de pouvoir les retrouver le plus rapidemment possible à partir de leurs coordonnées:

- Quels sont les rectangles qui contiennent le point X, Y
- Quels sont les rectangles qui sont dans (ou qui intersectent) un rectangle donné.

Je cherche donc une structure capable de structurer ces rectangles, du style arbre AVL pour les chaînes de caractères (pour la rapidité de recherche).

On a souvent parlé ici même du stockage et de recherche de coordonnées 2D, mais le problème est plus complexe: si un rectangle est de grandes dimensions, un point peut être dans ce rectangle et être très éloigné de ses coins. La recherche par rapport aux coordonnées des coins (ou du centre) ne sera pas efficace.

Les rectangles sont de taille et de forme quelconque (aplatis, allongés), mais tous parallèles aux axes (horizontaux ou verticaux).

bonjour,

je sais qu'il existe une structure tres particulière qui permet de gérer une tres grand nombre de triangle, notamment dans les cas de représentation de volumes par triangles.
Cette structure non triviale au premier abord, permet de savoir quel triangle en touche un autre, les voisins, ....

Tu pourrais peut être t'en inspirer ...

Citation:

---

Envoyé par ToTo13

Tu pourrais peut être t'en inspirer ...

---

Oui, peut-être. Aurais-tu un lien, un nom, une piste pour retrouver ça ?

Mais je précise que mes rectangles sont totalement quelconques: ils se chevauchent, ou ne se touchent pas, etc...

Bonjour,

Si l'espace est fini, on peut utiliser un quadrillage en cases de taille fixe.
On associe à chaque case , les rectangles qui ont une intersection avec la case.
(techniquement, Tableau de cases T à 2 dimension dont un élément pointe sur la liste des rectangles ayant une intersection avec la case).

Pour un point, on détermine à quelle case il appartient et on vérifie dans la liste des rectangles associés à la case, lesquels contiennent effectivement le point.

Pour un rectangle ABCD, on détermine à partir de A B C D les index min et max en X et Y des cases à traiter, puis on vérifie si pour chaque liste il y a intersection (attention on peut rencontrer le même rectangle dans 2 listes).

Pour optimiser les vérifications, on peut mettre un flag qui indique que si la case est entiérement contenue dans le rectangle.

Citation:

---

Envoyé par Graffito

Si l'espace est fini, on peut utiliser un quadrillage en cases de taille fixe.

---

L'espace est fini, bien sûr, mais pas forcément déterminé au départ. Il se peut qu'on doive ajouter en cours de traitement des zones qui débordent.

Citation:

---

Envoyé par Graffito

On associe à chaque case, les rectangles qui ont une intersection avec la case. (techniquement, Tableau de cases T à 2 dimension dont un élément pointe sur la liste des rectangles ayant une intersection avec la case).

---

Mouais, c'est la solution à laquelle on pense a priori. Mais elle a des tas de défauts: gaspillage de mémoire (il y aura sûrement des cases vides), post-traitement à faire pour éviter les doublons (puisqu'un rectangle peut être dans plusieurs cases. Et dans le pire des cas (un grand rectangle et plein de petits dans la même case), ça peut être pire qu'une recherche séquentielle.

Citation:

---

Envoyé par 10_GOTO_10

Voici mon problème: j'ai besoin de mémoriser un grand nombre de rectangles, de dimensions diverses, et surtout de pouvoir les retrouver le plus rapidemment possible à partir de leurs coordonnées:

- Quels sont les rectangles qui contiennent le point X, Y
- Quels sont les rectangles qui sont dans (ou qui intersectent) un rectangle donné.

---

Le nom anglais du problème, c'est Spacial Access Methods.

Structures de données classiques:
- R-Tree (avec une tonne de variantes)
- kd-Tree (dans ton cas, k=2)
- Quad-tree