Trouver un emplacement vide.

**méphistopheles** · 26/03/2006, 22h07

Bonjour.

J'essaye actuellement de trouver un algo pour positionner un carré de coté X sur une feuille sachant qu'il y en à d'autres dont je connais la position.

J'arrive sans problèmes à voir si pour telle position donnée mon carré est en conflict avec un autre, mais je n'arrive pas à choisir la position à comparer, c'est à dire que je ne peux pas me permettre d'essayer toutes les position de la feuilles une à une ou avec un trés petit pas.

Si vous avez une idée....

Codialement

**ToTo13** · 27/03/2006, 09h32

Bonjour,

de mémoire les problèmes de placement ou rangement sont NP Complet. Il est donc normal que tu ne puisses essayer toutes les positions.

As tu pensé dans ton cas aux métaheuristiques ?

**FrancisSourd** · 27/03/2006, 11h41

Le problème ici est clairement polynomial.

Pour éviter de tester toutes les positions, on peut chercher des conditions de dominances pour trouver un ensemble de positions possibles pour le point en haut à gauche.

Par exemple, pour chaque paire d'obstacles, on il n'y a qu'un point "en haut à gauche" possible (voir dessin ci-dessous). En effet, on peut toujours supposer qu'on peut "caler" le nouveau carré contre 2 obstacles existants.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
               xxxxxxxxxxxx
               xxxxxxxxxxxx
               xxxxxxxxxxxx
               xxxxxxxxxxxx
               xxxxxxxxxxxx
               xxxxxxxxxxxx
     ^      
 
  xxx
  xxx
  xxx

Donc, s'il y a k obtacles, il n'y a que k(k-1)/2 points de départ à essayer.

**méphistopheles** · 27/03/2006, 18h46

métaheuristiques?

heu non, connais pas

pour la réponse de françis sourd, ce serais vais si les obstacles étaient de même taille, mais par exemple pour une configuration du type:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
  XXXXX
  XXXXX
  XXXXX
  XXXXX
  XXXXX
 
XXXX
XXXX
XXXX XXX
XXXX XXX
     XXX

le nombre d'espaces à essayer va dépendre de la taille du carré à placer. enfin, je crois.

sinon, si ce que tu dis est vrai, comment choisir les positions à essayer?

merci

**FrancisSourd** · 27/03/2006, 22h14

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
__11111__
__11111__
__11111__
__11111__
_E__A____
2222_____
2222D__B_
2222_333_
2222_333_
____C333_

Effectivement, ma réponse ne considérait pas tous les cas... Voici donc l'illustration de l'idée sur ton exemple.
Si on suppose que ton objet est calé contre 1 et 2, on peut mettre son coin supérieur gauche en A ou son coin inférieur droit en E.
Si on suppose qu'il est calé entre 1 et 3, on peut mettre son coin inférieur gauche en B ou son coin supérieur droit en A
S'il est calé par 2 et 3, on peut mettre son coin supérieur droit en C ou son coin inférieur gauche en D.

J'espère ne pas m'être planté entre gauche/droit et supérieur/inférieur...

En tout cas, cela fait apparemment deux positions possibles pour chaque paire d'obtacles, quelle que soit leur taille.

**méphistopheles** · 27/03/2006, 22h25

En fait, je ne vois pas trés bien ce que tu appelle position. on peut trés bien mettre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
_F11111G__ 
__11111__ 
__11111__ 
__11111__ 
_E__A____ 
2222_____ 
2222D__B_ 
2222_333_ 
2222_333_ 
____C333H

en plus, si par exemple l'objet que je veux placer fait deux cases, je peux la placer en f mais aussi aux positions en dessous...

pour ma part, je considererais plutot une position par angle plus y positions par coté ou y= logueur du coté/X...

**FrancisSourd** · 27/03/2006, 22h59

J'imagine que les positions F, G, H que tu as rajoutées correspondent aux situations où l'objet est calé par un objet et un bord de ton cadre (je n'avais effectivement pas considéré les bords dans mon exemple...)

Pour les positions intermédiaires, je suis également d'accord avec toi (il y a Y-X positions à tester et non pas Y/X). Tout dépend de la question à résoudre:
- s'il suffit de savoir si tu peux placer ton nouvel objet, il suffit (je pense) de regarder les positions qui correspondent aux angles. Mon argument est que si un objet peut bouger sans rencontrer d'obstacle, on le bouge jusqu'à se qu'il arrive à une position où il se retrouve coincé. Comme on est en dimension 2, il est coincé par 2 objets. C'est en fait à ce problème que je répondais.
- s'il faut trouver toutes les positions possibles, le problème est plus difficile et il faudra sans doute une autre approche.

**méphistopheles** · 27/03/2006, 23h02

Une position suffit en effte, mais le problème, est qu'il faut que ce soit la premières dans le sens de la lecture.

de plus, je n'arrive pas à "trouver" les positions à tester, bien que je les conçoivent clairement dans leur principe.

**FrancisSourd** · 27/03/2006, 23h07

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
A_11111B_ 
__11111__ 
__11111__ 
__11111__ 
____C____ 
2222_____ 
2222_____ 
2222_333_ 
2222_333_ 
D____333_

Petite amélioration (si je ne dis pas de bétise): si on essaie de fait bouger l'objet vers le haut et la gauche, son coin supérieur gauche terminera soit en A,B,C ou D, quelque soit l'endroit où on le met au départ. Pour tester si l'objet rentre, il suffit donc de regarder ces 4 points (définis par l'intersection des 2 droites support du bas d'un obstacle et du coté droit d'un autre obstacle (ou bord)

**méphistopheles** · 27/03/2006, 23h23

Envoyé par FrancisSourd

(définis par l'intersection des 2 droites support du bas d'un obstacle et du coté droit d'un autre obstacle (ou bord)

Seul le point D corespond à cette définition non?

**FrancisSourd** · 28/03/2006, 09h23

Envoyé par méphistopheles

Envoyé par FrancisSourd

(définis par l'intersection des 2 droites support du bas d'un obstacle et du coté droit d'un autre obstacle (ou bord)

Seul le point D corespond à cette définition non?

Non, C est l'intersection entre la droite support du bord droit de 2 et la droite support du bord inférieur de 1 (évidemment, les arrondis dépendent de si on travaille dans le plan euclidien ou dans une matrice)

Le point B est l'intersection entre le bord droit de 1 et le bord supérieur du cadre (ce bord supérieur correspond à un obtacle mis en haut pour empêcher de sortir du cadre par le haut.

Le point A est l'intersection entre la bordure gauche et la bordure du haut du cadre.

Le point D est l'intersection entre la droite support du bas de l'obstacle 2 et la bordure gauche du cadre.

On peut encore un peu améliorer. Par exemple, je n'ai pas considéré l'intersection entre le bas de 2 et la droite de 1 et je ne l'aurais pas fait même en l'absence de l'obstacle 3: en effet, l'obstacle 2 est entièrement à gauche de la droite support du bord droit de 1: il n'y a donc aucune chance qu'un obstacle (qq soit sa taille) puisse toucher à la fois le bord inférieur de 2 et le bord droit de 1.

**méphistopheles** · 28/03/2006, 13h27

Je vois, mais je ne vois pas trop ce que ça donne en code....

par contre, j'ai remarqué que quelle que soit la configuration, s'il y as un emplacement vide on peut le trouver en positionant de trois manière différentes le carré à chaques angles.
par exemple pour positioner un carré de 4*4 avec un carré X

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
_______________
_11112***34444_
_11112***34444_
_11112***34444_
_11112***34444_
_ccccXXXXX5555_
_####XXXXX%%%%_
_####XXXXX%%%%_
_####XXXXX%%%%_
_bbbbXXXXX6666_
_aaaa9@@@87777_
_aaaa9@@@87777_
_aaaa9@@@87777_
_aaaa9@@@87777_
_______________
 
Avec: 
*=2 ou 3
%=5 ou 6
@=8 ou 9
#=b ou c

le problème , est que si j'ai une configuration de la forme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
________XXX____
_XXXXX__XXX____
_XXXXX__XXX____
_XXXXXA1111XXXX
_XXXXX_1111XXXX
_XXXXX_1111XXXX
_______1111XXXX

il trouvera forcément l'emplacement vide 1, mais il faudrais que je le décale ensuite d'une position vers la gauche pour avoir l'emplacement souaité... (A)

qu'en pense-tu?

Cordialement

Selehpotsihpem

**FrancisSourd** · 28/03/2006, 14h22

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
________XXX
_XXXXX__XXX
_XXXXX__XXX
_XXXXX1111_
_XXXXX1111_
_XXXXX1111X
______1111_

Si j'ai bien compris, il me semble que cet emplacement (le seul possible) ne correspond à aucun des cas que tu considères.

**méphistopheles** · 28/03/2006, 14h27

en effet, mais je pense que dans ce cas^précis, c'est une "exeption des bords", c'eszt à dire quil suffit de prendre toutes les absisses dont l'ordonnées corespondante est inférieure ou égale à 4(en partant du bas) et de faire un test pour chacunes.

**FrancisSourd** · 28/03/2006, 15h00

Non!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
________XXX
_XXXXX__XXX
_XXXXX__XXX
_XXXXX1111_
_XXXXX1111_
_XXXXX1111X
______1111_
_____XXX___
_____XXX___

On peut rajouter plein d'obstacle pour rendre cette position aussi loin des bords que l'on veut tout en la laissant la seule possible.

**méphistopheles** · 28/03/2006, 15h06

en effet.... là, je n'ai plus aucunes idées...

et toi?

**FrancisSourd** · 28/03/2006, 15h46

Mais la "méthode des deux obstacles" que je t'ai décrite plus haut marche!

Pour chaque rectancle, tu as quatre valeurs du style (g,d,h,b) qui correspondent à la colonne du bord gauche, à celle du bord droit, à la ligne du haut et à la ligne du bas:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
0____g__d___
 ___________
h____XXXX___
 ____XXXX___
 ____XXXX___
b____XXXX___
 ___________

Pour chaque obstacle (g,d,h,b) tu testes le point (0,d) et (b,0)
Pour chaque paire d'obstacle (g1,d1,h1,b1) et (g2,d2,h2,b2), tu testes les points (b2,d1) et (b1,d2)

Encore une fois, je suis dans le cas des coordonnées réelles. Si tu travailles avec des matrices, li faut prendre (b2+1,d1+1) et (b1+1,d2+1).

Est-ce plus clair?

**méphistopheles** · 28/03/2006, 16h07

oui merci, je vais essayer.

(je travaille en réel. en matrcie, je me casserais pas la tête à faire ça...)

**méphistopheles** · 29/03/2006, 14h35

Bon, j'ai réussi à programmer ça, mais en fait, je programme cela en ligne, sans vérifier s'il y as collision avec un objet:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
       e     f
       |     |
  XXXXX|     |
  XXXXX|   XX|
a_XXXXXc___XX|d__
  XXXXX|     |
b_XXXXXh_____g

ici, a, d et h peuvent être d'office élliminés, mais je ne sait pas comment les éviter...

si tu à une idée...

**FrancisSourd** · 29/03/2006, 15h28

Les points d et h proviennent des droites verticales et horizontales issues d'un même obstacle. On peut les supprimer en ne considérant que des paires d'obstacles différents.

Pour a, on peut l'éliminer car il y a un obstacle qui chevauche la droite support du bas du petit obstacle. L'implantation de cela varie avec la manière de stocker des blocks. En utilisant les notations de mon précédent message, cela donne d2 < d1 et h2 < b1 < b2.

Trouver un emplacement vide.

Algorithmes et structures de données

Discussions similaires

Partager

Partager