Trouver une zone libre dans la scène

Question

Je dessine des rectangles à des positions aléatoires sur la scène, et je ne veux pas qu'ils se chevauchent. Donc, pour chaque rectangle, j'ai besoin de trouver une zone vide pour le placer.

J'ai pensé à essayer une position aléatoire, vérifiez si elle est libre avec

private function containsRect(r:Rectangle):Boolean { 
    var free:Boolean = true; 
    for (var i:int = 0; i < numChildren; i++) 
     free &&= getChildAt(i).getBounds(this).containsRect(r); 
    return free; 
} 

et dans le cas où il retourne faux, essayer avec une autre position aléatoire. Le problème est que s'il n'y a pas d'espace libre, je serai coincé à essayer des positions aléatoires pour toujours.

Il existe une solution élégante à cela?

Answer 1

Soit S la zone de la scène. Soit A la zone du plus petit rectangle que nous voulons dessiner. Soit N = S/A

Une approche déterministe possible:

Lorsque vous dessinez un rectangle sur une scène vide, ce divise la scène en au plus 4 régions qui peuvent correspondre à votre prochain rectangle. Lorsque vous dessinez votre prochain rectangle, une ou deux régions sont divisées en au plus 4 sous-régions (chacune) pouvant contenir un rectangle, etc. Vous ne créerez jamais plus de N régions, où S est la zone de votre scène, et A est la zone de votre plus petit rectangle. Conserver une liste de régions (non triées), chacune représentée par ses quatre points d'angle, et chacune étiquetée avec sa surface, et utiliser la zone pondérée par zone reservoir sampling avec une taille de réservoir de 1 pour sélectionner une région avec probabilité proportionnelle à sa superficie dans au plus un passage dans la liste. Placez ensuite un rectangle à un emplacement aléatoire dans cette région. (Sélectionnez un point aléatoire dans la partie inférieure gauche de la région qui vous permet de dessiner un rectangle avec ce point comme son coin inférieur gauche sans toucher le mur supérieur ou droit.)

Si vous ne partez pas d'une étape vide, alors construisez simplement votre liste de régions disponibles dans O (N) (en retravaillant tous les rectangles existants sur une scène vierge dans n'importe quel ordre, par exemple) avant de rechercher votre premier point pour dessiner un nouveau rectangle.

Remarque: Vous pouvez modifier la taille de votre réservoir à k pour sélectionner les k rectangles suivants en une seule étape.

Note 2: Vous pouvez également stocker les régions disponibles dans un arbre avec chaque poids de bord égal à la somme des zones des régions dans le sous-arbre sur la zone de la scène. Ensuite, pour sélectionner une région dans O (logN), nous sélectionnons récursivement la racine avec la zone de probabilité de la région racine/S, ou chaque sous-arbre avec le poids du bord de probabilité/S. La mise à jour des poids sera gênante.

Durée: O (N)
Espace: O (N)

Une approche aléatoire possible:

Sélectionnez un point au hasard sur la scène. Si vous pouvez dessiner un ou plusieurs rectangles qui contiennent le point (pas seulement celui qui a le point dans son coin inférieur gauche), puis renvoyez un rectangle positionné aléatoirement qui contient le point. Il est possible de positionner le rectangle sans biais avec quelques subtilités, mais je vous le laisserai. Au pire, il y a un espace exactement assez grand pour notre rectangle et le reste de la scène est rempli. Donc, cette approche réussit avec une probabilité> 1/N, ou échoue avec la probabilité < 1-1/N. Répétez N fois. Nous échouons maintenant avec la probabilité < (1-1/N)^N < 1/e. Par échec, nous voulons dire qu'il y a un espace pour notre rectangle, mais nous ne l'avons pas trouvé. Par réussir, nous voulons dire que nous avons trouvé un espace s'il en existait un.Pour obtenir une probabilité raisonnable de succès, nous répétons Nlog (N) fois pour la probabilité 1/N d'échec, ou N² fois pour la probabilité 1/e^N d'échec. Résumé: Essayez des points aléatoires jusqu'à ce que nous trouvions un espace, en nous arrêtant après NlogN (ou N²) essais, auquel cas nous pouvons être sûrs qu'il n'y a pas d'espace.

Durée: O (NlogN) pour une forte probabilité de succès, O (N²) pour très haute probabilité de succès
Espace: O (1)

Answer 2

Je ne suis pas sûr de savoir à quel point cela serait élégant, mais vous pourriez définir un nombre maximum de tentatives. Peut-être 100?

Bien sûr, il se peut que vous ayez encore de l'espace disponible, mais vous pouvez quand même déclencher l'événement "finish". Ce serait comme lorsque des bibliothèques d'interpolation alignent un objet sur le point de destination juste parce qu'il est "assez proche".

HTH

Answer 3

Un possible vérifier que vous pourriez faire pour déterminer s'il y avait assez d'espace, serait de vérifier à quel point la zone actuelle de l'ensemble rectangels prennent place. Si la superficie restante est inférieure à la surface du nouveau rectangle, vous pouvez immédiatement abandonner et renflouer. Je ne sais pas quelles informations vous avez à votre disposition, ou si les rectangles sont posés régulièrement, mais si c'est le cas, vous pouvez modifier la vérification pour voir s'il n'y a pas assez d'espace disponible.

Ce n'est peut-être pas la méthode la plus appropriée pour vous, mais c'est la première chose qui m'est venue à l'esprit!

Answer 4

En supposant que vous définissez les dimensions du rectangle avant d'essayer de le dessiner, je pense que quelque chose comme cela pourrait fonctionner:

d'établir une grille de points centraux possibles sur la scène du rectangle candidat. Donc, pour un rectangle 6x4, votre premier point serait à (3, 2), puis (3 + 6 * x, 2 + 4 * y). Si vous pouvez dessiner un rectangle entre les quatre points adjacents, un espace possible existe.

for (x = 0, x < stage.size/rect.width - 1, x++) 
    for (y = 0, y < stage.size/rect.height - 1, y++) 
     if can_draw_rectangle_at([x,y], [x+rect.width, y+rect.height]) 
      return true; 

Cela ne veut pas vous dire où vous pouvez le dessiner (bien qu'il devrait être possible de construire une liste des zones de dessin possibles), juste que vous pouvez.

Answer 5

Vous pouvez simplifier les choses avec une transformation. Si vous cherchez un endroit valide pour placer votre rectangle LxH, vous pouvez à la place développer tous les rectangles L précédents vers la droite, et H vers le bas, puis rechercher un seul point qui n'intersecte aucun de ceux-ci. . Ce point sera le coin inférieur droit d'un endroit valide pour placer votre nouveau rectangle.

Ensuite, appliquez un algorithme de balayage de ligne de balayage pour trouver les zones non couvertes par un rectangle. Si vous voulez une distribution uniforme, vous devez choisir une coordonnée y aléatoire (en supposant que vous balayez vers le bas) pondérée par la distribution de zone libre. Choisissez ensuite une coordonnée x aléatoire de manière uniforme à partir des segments ouverts dans la ligne de balayage que vous avez sélectionnée.

Answer 6

Je pense que le seul moyen efficace de faire cela avec ce que vous avez est de maintenir un tableau booléen 2D des emplacements ouverts. Avoir le tableau de taille suffisante pour que les positions de dessin apparaissent toujours aléatoires.Lorsque vous dessinez un nouveau rectangle, mettez à zéro la pièce rectangulaire correspondante du tableau. La vérification d'une aire libre est alors constante. H H H H H H H H H. Oups, cela signifie qu'une recherche est O (nm) time, où n est la longueur, m est la largeur. Il doit y avoir une solution basée sur la gamme, argh.

Edit2: Apparemment, la réponse est here mais, à mon avis, cela pourrait être un peu plus à mettre en œuvre sur Actionscript, surtout si vous n'êtes pas intéressé par la géométrie.

Answer 7

Voici l'algorithme I « d utiliser

1. Baissez nombre N de points aléatoires, où N est le nombre de rectangles que vous souhaitez
2. augmente de manière itérative les dimensions des rectangles créés à chaque point N jusqu'à ce qu'ils touchent un autre rectangle.

Vous pouvez limiter la façon dont les points initiaux sont placés si vous souhaitez avoir une taille de rectangle minimale autorisée.

Si vous voulez tout l'espace couvert de rectangles, vous pouvez ensuite ajouter des points aléatoires à l'espace libre restant jusqu'à ce qu'il n'y ait plus de zone non couverte.