Bonjour, j'ai un problème que je n'arrive pas à résoudre avec une complexité inférieure à n²    
 
(On travaille en 2 dimensions pour commencer)
 
Imaginons que l'on ait un certain nombre de rectangles, de tailles différentes. Ces rectangles peuvent se supperposer. La question est de savoir comment déterminer le "contour" des zones où un rectangle est posé.
 
 
Je pensais utiliser l'analogie suivante : imaginons que nos rectangles soient en fait des blocs parallélépipédiques parallèles au sol et que l'on ait un soleil pile au dessus de notre scène (mais très haut donc tous les rayons sont parallèles) : l'idée est de déterminer le contours des zones d'ombres qui apparaitront au sol ...
 
Voila je ne sais pas trop si j'ai été clair    
 
En tout cas merci d'avance de votre aide
 
NC

Ca a l'air plutôt simple, vu comme tu le présentes. J'aurais tendance à reprendre le principe d'un algo qu'on m'a présenté récemment, à savoir : créer un tableau intermédiaire contenant tous les débuts et fins de rectangles selon l'axe horizontal. Ensuite, parcourir ton tableau te permet assez simplement  de trouver les moments où tu es sous l'ombre d'un rectangle ou à découvert.
 
lien vers l'algo en question : http://www.ziggyware.com/readartic [...] cle_id=128

ok je regarde votre algorithme, mais je viens de poster sur imageshack une image de ce a quoi devrait ressembler le résultat : les rectangles étant les contours noirs, on doit obtenir les contours des zones rouges  
http://img156.imageshack.us/my.php?image=ombrespk5.jpg (deux zones donc)

effectivement, je n'avais pas du tout compris ce que tu voulais
 
Du coup, je me demande pourquoi tu veux regrouper tes rectangles parce que ca a l'air assez commode de les avoir sous forme de rectangles ... Tu cherches à remplir une map d'ombres ? Tu peux un peu plus détailler le contexte ?

en fait l'ombre est une analogie histoire de faire comprendre ce que je veux, mais ce n'est pas le but de mon algorithme
 
le but de mon algorithme est en fait de déterminer le contour d'une superposition d'obstacles : imaginons par exemple que l'on ait un certain nombre de briques empilées de diverses manières (on considèrera par soucis de simplicité qu'elles sont toutes horizontales et que donc leur projeté sur le sol est bien un rectangle), notre but est de déterminer le contours de l'obstacle constitué par ces briques, sachant qu'elles peuvent aussi bien faire un joli mur qu'un tas informe

dans ce cas, ca s'apparente à un regroupement des polygones par collision et à de la construction de polygones à partir de ceux en collision, non ?
 
Le lien que j'ai donné propose une solution pour accélérer la recherche de collision. La composition des polygones "complexes" à partir de tes rectangles est un autre problèmen mais tu dois pouvoir aussi trouver assez aisément des algos pour le faire rapidement, j'imagine