Détection de collisions entre rectangles

J'ai besoin de déplacer des objets rectangulaires dans une "zone de dessin", mais ces objets ne doivent jamais se superposer : ils ne doivent jamais entrer en collision les un avec les autres.

Illustration ici :
http://img327.imageshack.us/img327/4310/collide4ku.jpg
J'ai trois petits objets et un plus gros. La zone en bleue est l'endroit où l'utilisateur essaie de déplacer l'objet, et comme on peut le voir, l'objet reste coincé par les petits objets.

J'ai déjà un algorithme relativement bon, mais il ne gère pas tous les cas, et j'aimerais que cet algorithme soit le plus propre possible.

En définitive, cet algorithme doit servir à positionner des articles dans un rayonnage virtuel de grand magasin.
J'ai en fait deux types d'articles : les articles montés sur une broche et les articles posés sur une planche.

J'ai donc les mêmes contraintes à remplir avec les planches (ce qui marche très bien actuellement) :
http://img338.imageshack.us/img338/2968/image63oa.jpg
Et les objets posés sur une planche (qui fonctionne relativement bien, il y a un cas où un bug survient.... :?) :
http://img338.imageshack.us/img338/2...age57lx.th.jpghttp://img338.imageshack.us/img338/1...age64ex.th.jpghttp://img338.imageshack.us/img338/8...age76bk.th.jpg

Donc, de manière à régler ces quelques problèmes, j'aimerais repartir sur des bases plus saines, plus générales, plus communes à tous les objets.

Avez-vous déjà travaillé sur un problème similaire ? Et avez-vous trouvé une solution élégante à ce problème ?

Bonjour,

il est simple de gérer les collisions d'objets rectangulaires : un simple test à partir des dimensions. La seule difficulté serait peut être de gérer le fait que le clic sur l'objet à déplacer ne se fait jamais au millieu de l'objet. Il faut donc tenir compte de la souris sur l'objet pour faire le test.

En revanche, si tu veux remplir les rayons d'un magasin virtuel, tu aura de gros souci avec ton raisonnement : lorsque tout les objets seront placé sauf un, ce un qui peut être en plein milieu (tu l'aurai peut être oublié), si les objets ne doivent pas se chevaucher pendant le déplacement, tu ne pourras jamais déplacer l'objet vers son emplacement. Par contre, si tu fais le test uniquement au moment où l'objet est laché, tu pourras le placer.

c'est tout à fait normal
si je construis un tas avec une cavité en son sein il me reste bien une place mais inutilisable car non accessible
donc je dois retirer des éléments libérer la cavité la remplir et complèter
je pense à une recherche qui placerait chaque élément en laissant une voie d'accès pour les suivants
inconvénent en termes de logistique on se trouve alors en lifo

En fait ça ne fonctionne pas exactement de cette manière.

En réalité, il est possible de déplacer un objet où on veut, même s'il n'y a pas "d'accès".

Exemple :
http://img224.imageshack.us/img224/6...ide27sz.th.jpg
Comme vous pouvez le voir, il n'y a pas d'accès au centre des 8 objets et le 9e objet semble "bloqué".

Mais si je déplace un peu ma souris vers le centre....
http://img224.imageshack.us/img224/7...ide11fd.th.jpg
On voit qu'en réalité le centre des 8 objets était bien accessible par le 9e objet.

En revanche, après une petite discussion avec l'intéressé, la collision par rectangles risque de ne pas être suffisante.
En effet, il y a des cas où les objets sont "encastrables" les uns dans les autres (par exemple un pot de fleur). Mais ça n'est pas tout, il existe des cas où les objets sont superposés à des objets d'un autre type (et les deux objets en question ne sont pas forcément rectangulaires (je n'ai malheureusement pas d'illustration sous la main...)

En définitive, il me faudrait un algorithme qui à partir de la position et la forme d'un objet déplacé et de la position et de la forme d'un ensemble d'objets fixes (car non déplacés à ce moment là) me donne la position de l'objet déplacé la plus proche de la position du curseur de manière à ce que l'objet déplacé n'entre en collision avec aucun objet, ni avec les limites du rayonnage (on parle de linéaire en fait), d'ailleurs.

Le pire dans tout ça, c'est qu'un objet donné a une apparence graphique donnée mais que les contours du graphisme ne correspondent pas aux "contours de collision" de l'objet.

Bonjour,

comme tu t'en doutes, le plus dur va être d'avoir une représentation de la forme de l'objet et surtout de ces contours. Surtout pour les objets, disons... patatoïdes.
Si tout tes objets peuvent se réduire à de rectangles ou des ellipses, quelques tests suffisent.

Sinon, une version bourrin mais facile si tes objets ne sont pas enormes et si ton echelle est raisonable :
- tu trouves la boite englobante de tes objets.
- tu crées un tableau de la taille de cette boite. Ce tableau contiendra des 1 et 0 qui te donneront de manière discrête la forme de l'objet.
- Etant donné que la boite englobante est de forme rectangulaire, cela évitera des tests.

C'est moche comme méthode, mais ça marche et selon la taille, c'est hyper rapide.