11-02-2010, 11:55 AM
(Modification du message : 11-02-2010, 12:07 PM par NicoMSEvent.)
crée une chaine linéaire, et chaque élément contient un couple de valeur (x,y), d'une telle manière que tu puisse faire une recherche rapide sur x et y. Ensuite, crée les liens (donc ton graphe) sur base des voisins
fais gaffe aux "exceptions" (début et fin de chaque anneau)
je ne crois pas que ça soit spécialement difficile, juste un peu dur a appréhender si tu n'as une bonne vision en 2D du problème (transformation d'une chaine en graphe)
Edit : j'ai p-e mal compris ton besoin... je pense que tu cherches a mettre ce graphe en mémoire, et avoir accès facilement d'un noeud a un autre (ou déterminer facilement les voisins). Mais p-e qu'il suffit juste d'un petit morceau d'algorithme, et pas d'un graphe complet )
par exemple, juste sur base de l'algo pour un schéma ou tu passerait en paramètre (3,4), comme pour ton exemple (3 niveaux,4 sphères),
basé sur les voisins (x-1,y-1), (x-1,y), (x+1,y), (x-1,y+1), (x,y+1), (x-1,y+1) (on ignore les négatifs pour x, de meme ce qui dépasse, et pour y on utilise un modulo)
ta sphère (2,1) à comme voisin -> (1,0),(1,1),(3,1),(1,2),(2,2),(3,2).
en gros, chaque noeud possède 1->N lien (pour ta chaine, tu utiliserait juste 1 lien pour le noeud de début et de fin, et pour les autres, 2 liens : précédent et suivant)
Si tu as un algorithme(ou du pseudo-code), je veux bien y jeter un oeil
Edit2 : erf,je viens de voir que ta spirale de base n'est pas une chaine, mais déjà un graphe... :p
Citation :il y a un voisin vers le centre, deux voisins sur la même "boucle" de la spirale, et trois voisins vers l'extérieur.
donc
(x-1,y-1), (x-1,y), (x+1,y), (x-1,y+1), (x,y+1), (x-1,y+1)
fais gaffe aux "exceptions" (début et fin de chaque anneau)
je ne crois pas que ça soit spécialement difficile, juste un peu dur a appréhender si tu n'as une bonne vision en 2D du problème (transformation d'une chaine en graphe)
Edit : j'ai p-e mal compris ton besoin... je pense que tu cherches a mettre ce graphe en mémoire, et avoir accès facilement d'un noeud a un autre (ou déterminer facilement les voisins). Mais p-e qu'il suffit juste d'un petit morceau d'algorithme, et pas d'un graphe complet )
par exemple, juste sur base de l'algo pour un schéma ou tu passerait en paramètre (3,4), comme pour ton exemple (3 niveaux,4 sphères),
basé sur les voisins (x-1,y-1), (x-1,y), (x+1,y), (x-1,y+1), (x,y+1), (x-1,y+1) (on ignore les négatifs pour x, de meme ce qui dépasse, et pour y on utilise un modulo)
ta sphère (2,1) à comme voisin -> (1,0),(1,1),(3,1),(1,2),(2,2),(3,2).
en gros, chaque noeud possède 1->N lien (pour ta chaine, tu utiliserait juste 1 lien pour le noeud de début et de fin, et pour les autres, 2 liens : précédent et suivant)
Si tu as un algorithme(ou du pseudo-code), je veux bien y jeter un oeil
Edit2 : erf,je viens de voir que ta spirale de base n'est pas une chaine, mais déjà un graphe... :p
Je signale que je ne détiens pas la vérité unique et absolue, je peux me tromper. La critique peut aussi être constructive. Critiquez moi!
La quête d'Ewilan
http://easy2hack.ma-soiree.be
La quête d'Ewilan
http://easy2hack.ma-soiree.be