J'ai une application qui construit des images aléatoires en fonction de contraintes. Différents pixels colorés sont sélectionnés au hasard et placés dans une grille qui répondent à toutes les contraintes. Par exemple (simplifiant), il pourrait y avoir une contrainte qui dit si un pixel bleu ou vert est à (0, -1) et les pixels rouges sont à (-1, -1) et (-1, 0), puis placent Un pixel blanc est interdit. Ces coordonnées sont des vecteurs de l'emplacement de placement actuel (c'est-à-dire son quartier).
En ce moment, je stocke les contraintes dans une matrice et en boucle, vérifiant si chacun est applicable ou non. Je dois le faire pour chaque pixel que je place dans la grille. La performance souffre donc que de plus de contraintes sont ajoutées. En outre, il est possible que deux contraintes soient en conflit, mais il n'est pas facile de vérifier cela.
Je pense qu'une structure de données de type graphique (arbre?) pourrait être un moyen de stocker toutes les contraintes de manière à déterminer rapidement du voisinage de pixels qui (le cas échéant) s'appliquent. Mais je ne pouvais pas comprendre comment faire une telle structure, étant donné qu'une seule coordonnée peut contenir plusieurs couleurs et comment lier un ensemble de coordonnées / couleurs à l'ensemble de couleurs de pixels interdites. Des idées?
4 Réponses :
Pour ce problème, vous pouvez utiliser différents types d'arbres.
Cela semble être largement recherché du sujet et une réponse probablement serait bien plus longue que la normale. Reportez-vous à la section suivante:
http://www.computer.org/csdl/ TRANS / TS / 1977/02/01702419.PDF
Havent a travaillé avec un motif correspondant, mais ce qui me vient à l'esprit est:
Prenez habituellement graphique DS où les sommets seront vos vecteurs et vos bords seront des couleurs interdites les reliant. Ici, vous pouvez connecter tous les sommets entre les autres, plus optimal aura une certaine direction que vous utiliserez remplir votre DS, vous devez utiliser le même point de départ et la même direction lorsque vous passerez via des tableaux de pixels. De votre exemple si vous commencez à partir de (0, -1) aller dans le sens des aiguilles d'une montre, ce sera quelque chose comme: (0, -1) --Blue-- (-1, -1), (0, -1) --green- - (-1, -1), (-1, -1) - (-1, 0), (-1, 0) - (- 1, 1), (-1, 1) --White - (0, 1), (-1, 1) - White-- (1, 1), (-1, 1) --White-- (1, 0)
Utilisez maintenant DFS pour rechercher la couleur pour vérifier (il sera bord)
Il me semble qu'un choix pratique serait un arbre KD. En stockant vos contraintes dans un arbre KD, vous pourriez être capable d'accéder aux contraintes qui s'appliquent avec un type de voisin de voisin le plus proche.
Je vous suggérerais de jeter un coup d'œil au livre algorithmes en un mot . Vous pouvez trouver un Mise en œuvre facile d'un KD -tree qui pourrait être applicable à votre problème.
Cependant, gardez à l'esprit que si les contraintes ne sont pas uniformément réparties dans votre scène, l'arbre résultant pourrait ne pas être bien équilibré. Dans ce cas, vous devriez trouver une meilleure représentation des contraintes, ou la complexité réelle de l'algorithme sera plus proche de la pire valeur O (n), plutôt que la valeur moyenne (et la meilleure) O (log n).
Vous pouvez utiliser une coupe graphique pour résoudre ce problème. Il s'occupera même des conflits mentionnés. C'est fondamentalement comment cela fonctionne: il essaie d'attribuer des étiquettes en fonction d'une fonction de coût que vous souhaitez minimiser. Pour votre cas, la fonction de coût pourrait être quelque chose du genre:
E(x)=infinite ; if constraint is violated and 0 ; otherwise
Merci! Cela a l'air de la bonne direction pour poursuivre. Je n'ai jamais entendu parler des coupes de graphique avant.