classes de collision

Bonjour,

J'ai un ensemble de rectangles (all_rects) que je cherche à partitionner de la manière suivante:
- deux rectangles qui s'intersectent doivent appartenir à la même classe
- 2 rect. de 2 classes distinctes ne doivent pas s'intersecter.

Le but de cette partition est, plutôt que de dessiner tous mes sprites d'un coup, de pouvoir redessiner uniquement des groupes de sprites qui s'intersectent (et qui doivent donc être dessinés ensemble, de manière 'atomique').

Commencons par une version simple: calculer la classe d'un rectangle (un_rect) donné.
J'imagine le pseudo code suivant:

Code:

---

1 2 3 4 5 6 7 8

classe = [] new_elems= [un_rect] while new_elems: all_rects.remove(new_elems) # epure la liste des candidats intersecting= [s for s in all_rects if s.collideany(new_elems) ] classe.extend(new_elems) new_elems= intersecting # epure la classe des éléments déja vérifiés

---

La complexité (O(N^3) au pire) de ce code me laisse perplexe, d'autant plus qu'il faudrait y rajouter des infos sur quels sprites ont été dessinés (car entre deux appels à paint(), les classes ont pu évoluer).

Je sais que l'un des pygame.SpriteGroup fait grosso modo la même chose, mais il est trop lent pour mes besoins. Existe-t'il un algo rapide pour faire cela ?

Je pense aux pistes suivantes:
- Une classification descendante (plutot qu'ascendante dans le pseudo code précédent)
- Mettre à jour à chaque update de rectangle la liste des rect intersectant, plutot que le calcul collideany() à chaque fois que je calcule une classe.

Merci d'avance pour vos idées / commentaires.