PDA

Voir la version complète : toile d'araignée



clemz
27/02/2010, 12h40
bonjour les loulous ,

juste pour l'exercice j'ai commencé un petit script pour générer/controler des toiles d'araignées , et j'arrive à un moment où j'ai besoin de l'aide des matheux psychopathes ! :love:

donc j'ai la partie spiralée qui fonctionne bien :
http://kiteclem35.free.fr/3D/C4D/Spider/SpiderWeb-progress2.jpg

mais maintenant je veux rajouter tout ça sous 2 splines tendues ( par ex entre 2 brins d'herbe , où un coin de mur etc .. )
donc en fait dans l'idée , on donne en DU un nul objet regroupant autant de nul que l'on veut . ces nuls servent ensuite dans le code de points d'attache extérieurs ( donc si on donne 4 points , on obtient une enceinte 'quadrilatère' pour une toile entre 2 brins d'herbe, simples , comme je disais au dessus ... mais on peut donner que 3 points par ex , pour un coin de fenêtre etc ... ou 5 points ...? ou plus )

mais je voudrais que l'on n'ait pas à organiser les nuls 'attaches' dans le bon ordre dans le nul root . car le code doit tracer ce 'Ngon' via ces points ,en les prenant dans l'odre les uns à la suite des autres.. mais il ne faut pas qu'une arête "passe par le mileu" .. voila une image pour mieux comprendre mes piêtres explications :calim: :

http://kiteclem35.free.fr/3D/C4D/Spider/Ngon.jpg

j'aimerais donc que mon code puisse lire n'importe quelle suite de nuls (ici 4 ) et en déduire la suite adéquate pour créer une cage "non croisée"

j'ai fais quelques recherches et j'ai trouvé qu'avec 4 points , le nombre de combinaisons possibles , en partant toujours du 1er ( donc : 1234 1243 1324 1342 1423 1432 ) = (n-1)(n-2) =6 avec n=4

pour 5 points (n=5) , on a (n-1)(n-2)(n-3) = 24 combinaisons .. pour n=6 on a (n-1)(n-2)(n-3)(n-4) ..120 combinaisons ..etc

donc comme vous voyez la formule n'est pas constante il faut rajouter un "(n-x)" de plus à chaque n+1 ...

Donc j'en arrive enfin à ma question :mrgreen: ..est-ce qu'il y aurait une formule "fixe" et non "dynamique" pour que mon script l'applique juste à la suite de nuls ? ceci afin de déterminer quelle est la somme des distances la plus courte car c'est la/les combinaison(s) donnant la somme des longueurs d'arêtes la plus courte qui sera la bonne .. des sommes plus grandes signifieraient que les arêtes se croisent comme sur mon image ci-dessus )

A moins qu'il n'y est une autre façon de savoir si le "Ngon est bon" ?

merki d'avance

:odile:

clem

Jean-Laurent
27/02/2010, 13h04
ceci afin de déterminer quelle est la somme des distances la plus courte car c'est la/les combinaison(s) donnant la somme des longueurs d'arêtes la plus courte qui sera la bonne .. des sommes plus grandes signifieraient que les arêtes se croisent comme sur mon image ci-dessus )


Intéressant ton problème. Et joliment présenté donc ça donne envie. :bave:

Par contre malheureusement ta proposition me semble fausse.
Sur ton image c'est intuitif mais comme on dit "la géométrie c'est raisonner juste sur des figures fausses" :mrgreen:

Le chemin le plus court en passant une seule fois par tous les points d'un nuage de point ne signifie pas que les chemins ne se croiseront pas.
Je me trompe peut-être mais c'est mes souvenirs. :oops:

J'y jette un oeil dès que j'ai un peu de temps.

champagne
27/02/2010, 13h05
Jean-Laurent, JEAN-LAURENT,
On t'appelle :mrgreen:
Ne t'inquiète pas Clemz, je suis sûr qu'il aura entendu :wink:

EDIT: tu vois ce que je disais :mrgreen:

clemz
27/02/2010, 13h11
ceci afin de déterminer quelle est la somme des distances la plus courte car c'est la/les combinaison(s) donnant la somme des longueurs d'arêtes la plus courte qui sera la bonne .. des sommes plus grandes signifieraient que les arêtes se croisent comme sur mon image ci-dessus )


Intéressant ton problème. Et joliment présenté donc ça donne envie. :bave:

Par contre malheureusement ta proposition me semble fausse.
Sur ton image c'est intuitif mais comme on dit "la géométrie c'est raisonner juste sur des figures fausses" :mrgreen:

Le chemin le plus court en passant une seule fois par tous les points d'un nuage de point ne signifie pas que les chemins ne se croiseront pas.
Je me trompe peut-être mais c'est mes souvenirs. :oops:

J'y jette un oeil dès que j'ai un peu de temps.


arf merci Jean-Laurent :) . oué tu dois avoir raison sur mon histoire de somme :oops: ..sur un exemple simple rectangulaire ça fonctionnerait mais sur d'autres config je dois avoir faux oué . flute ! diantre !

edit : ouep Champ, le gourou des maths m'a entendu :love:


edit 2 :

non pour ma formule dynamique , j'suis con c'est tout simple :
...
var comb = n-1; // n est le nombre de nuls
for(i=1;i<=comb-1;i++)
{
comb=comb*(n-(i+1));
}
..
ça devrait fonctionner .. mais bon comme le dit Jean-Laurent , c'est pas bon ..donc faut trouver autre chose :art:

Jean-Laurent
27/02/2010, 13h48
Alors manger porte conseil. :mrgreen:

Je viens de constater que pour un nuage de point quelconque il y a plusieurs possibilités pour que les segments ne se croisent pas.
Donc il faut mettre une condition supplémentaire.

Sinon pour ta formule c'est effectivement très simple.
Il s'agit de ce qu'on nomme une "factorielle". Très utilisé en probabilité. C'est très facile à implémenter dans un programme.

En première approximation ne peux-tu pas simplement rejoindre les points les plus proches entre eux, les uns à la suite des autres. :?:
Si ta distribution de point n'est pas trop erratique ça marchera.

clemz
27/02/2010, 14h06
ha ok :)
(n'oublie pas de faire ton rototo après manger ..ça aide à la digestion :deal: )




En première approximation ne peux-tu pas simplement rejoindre les points les plus proches entre eux, les uns à la suite des autres. :?:
Si ta distribution de point n'est pas trop erratique ça marchera.


bein si par ex j'ai cette config :

http://kiteclem35.free.fr/3D/C4D/Spider/CasExtreme-1.jpg

le point 2 risque d'aller chercher le point 4 si le code cherche les distances les plus courtes entre les points ?

Jean-Laurent
27/02/2010, 14h15
Tout à fait. :?

Une piste:
http://www.apprendre-en-ligne.net/OCinfo/algo/enveloppe.html

Edit: Il existe également des algos pour les enveloppe non-convexes.
Sachant qu'on va toujours supposé qu'une enveloppe est suffisante pour ce que tu veux faire.

Edit2: La marche de Jarvis me semble une bonne piste.
http://fr.wikipedia.org/wiki/Marche_de_Jarvis

Et un exemple de code, mais dans le plan bien évidemment:
http://www.uzit.fr/algorithmique/marche-jarvis.html

clemz
27/02/2010, 14h28
ha super merci pour les liens :) . il y a même un script python pour la methode Jarvis c'est cool :love:

je zieute tout ça !

:odile:

Jean-Laurent
27/02/2010, 14h32
Il faut regarder aussi au niveau des enveloppes non convexes:
http://www.iag.asso.fr/articles/nuage.htm

Mais quoi qu'il en soit il y a plusieurs possibilités donc un choix à faire à un moment ou à un autre.

Jean-Laurent
27/02/2010, 14h53
Une petite application sympa en bas de page:
http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html

Pas si simple que ça ton petit problème. :mrgreen:

clemz
27/02/2010, 15h37
Une petite application sympa en bas de page:
http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html

Pas si simple que ça ton petit problème. :mrgreen:


merci pour le lien :)

ouep ^^ en fait la partie toile d'araignée visible c'est simple mais ce truc à la con de lire les controlleurs dans le bon ordre c'est chaud ^^.

edit : excellente l'appli :) .

je vais essayer de faire un truc genre Jarvis / Graham : chaque point regarde les autres et prend le 1er en tournant dans un sens en partant du précédent ... ouch rien que de dire ça j'en ai deja mal aux neuronnes :lol:

clemz
28/02/2010, 00h00
bon chtite update .. j'ai mis de coté ce problême de cage convexe pour l'instant ..

donc voila avec les 3 étapes : enceinte/branches/spirale .

:odile:

Jean-Laurent
28/02/2010, 09h47
bon chtite update .. j'ai mis de coté ce problême de cage convexe pour l'instant ..


Tous les exemples que tu nous montres pour l'instant correspondent à des cages convexes. C'est déjà ça. :mrgreen:
Je regarde de mon côté le code alors. Je poste quand j'ai un truc viable. :odile:

clemz
28/02/2010, 12h35
bon chtite update .. j'ai mis de coté ce problême de cage convexe pour l'instant ..


Tous les exemples que tu nous montres pour l'instant correspondent à des cages convexes. C'est déjà ça. :mrgreen:
Je regarde de mon côté le code alors. Je poste quand j'ai un truc viable. :odile:




arf désolé ^^ ..concave alors je voulais dire :P

oki merci JLo ! :love:

j'ai rajouté un truc encore : un paramêtre de 'tension' pour que ce soit moins "linéaire" . donc pour l'enceinte si on met une couleur auto blanche sur 2 controlleurs successifs , le code comprend que l'on est sur une "paroie" et donc créé une spline 2 points basic ( donc bord de murs , coin de fenêtre etc ) et si on met une autre couleur que le blanc (vector(1,1,1)) le code comprend que l'enceinte n'est plus sur un bord , mais juste tenue par les controlleurs , alors il créé une spline 3 points entre chaque controlleur . et y applique alors une déformation ' tension' vers le centre de la toile ..
Je vais rajouter ce paramêtre de tension sur les branches et la spirale . et rajouter un paramêtre de "circularité" pour que la spirale suivent quand même une forme plus ou moins circulaire , même si l'enceinte est complêtement zarbi

:odile:

valkaari
01/03/2010, 04h51
Une petite application sympa en bas de page:
http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html

Pas si simple que ça ton petit problème. :mrgreen:


De ce que je comprends de cette application, faut tracer le voronoi, déplacer des cercles de diamètre identique sur les bidules au milieu si les deux points sont sur le contour, on trace.

on augmente la taille du cercle jusqu'à ce qu'on est nbr coté = nbr points

enfin un truc du genre ?

Jean-Laurent
01/03/2010, 10h26
Je suis vraiment rouillé.
Deux boucles imbriquées et des listes et je me suis noyé dedans.
Enfin, pour la marche de Jarvis ça marche:
http://img19.imageshack.us/img19/5527/jarvisl.jpg

J'ai surtout eu du mal avec la gestion des listes dans Python, je crée souvent des alias sans m'en rendre compte. :coup:

Le code Python qui transforme une série de points dans le désordre en une autre série représentant l'enveloppe convexe:


def jarvis(points):

# On fait une copie de la liste de point, celle que l'on videra au cours du programme.
i=0
liste_jarvis=&#91;]
while i<k:
liste_jarvis.append(points[i])
i=i+1

# On retire de cette liste le point de départ le plus à gauche et on le place dans la liste finale.
liste_jarvis.remove(plusgauche(points))
liste_finale=[[plusgauche(points)[0],plusgauche(points)[1]]]

depart=[0,0]
depart[0]=plusgauche(points)[0]
depart[1]=plusgauche(points)[1]

j=0
while j<k-1:
intermediaire=liste_jarvis[0]
# On part du point de départ et on vérifie qu'il n'existe aucun point à gauche du segment entre ce point
# et le point intermédiaire. Sinon on change de point intermédiaire.

i=0
while i<len(liste_jarvis):
if sens_direct(depart,intermediaire,liste_jarvis[i]):
i=i+1
else :
intermediaire=liste_jarvis[i]
i=i+1

depart[0]=intermediaire[0]
depart[1]=intermediaire[1]
liste_finale.append([intermediaire[0],intermediaire[1]])

j=j+1

return liste_finale


Je peux te mettre ça en coffee si besoin.


Mais tout en codant ça j'ai réalisé que c'était pas forcément le plus utile. Il y a bien plus simple.
Dans le cas qui t'intéresse c'est pour une toile d'araignée donc on peut honnêtement supposer que la forme de la toile a quelque chose qui ressemble vaguement à un centre et qu'on aura pas un nuage de point complétement aléatoire.
Il suffit de partir d'un point fictif au centre des autres points, de tourner dans le sens qu'on veut et d'accrocher au fur et à mesure les points qu'on rencontre. On les aura ainsi dans l'ordre, convexe ou concave. 8)

Je fais ça quand j'ai un peu de temps. :wip:




De ce que je comprends de cette application, faut tracer le voronoi, déplacer des cercles de diamètre identique sur les bidules au milieu si les deux points sont sur le contour, on trace.

on augmente la taille du cercle jusqu'à ce qu'on est nbr coté = nbr points

enfin un truc du genre ?


Heu, un truc du genre. :mrgreen:
J'avoue que j'ai regardé du coup le principe de la triangulation de Delauney et de Voronoi mais je n'ai pas poussé plus loin.
Pour les cercles ils apparaissent visiblement quand le diamètre correspond à la distance entre deux points. Ils passent toujours par ces deux points et donc leur centre est sur le diagramme de voronoi et ils disparaissent dès que le rayon est suffisant pour englober un troisième point.
Visuellement c'est simple mais à coder. :?:

lenogre
01/03/2010, 10h36
xsyann a fait un plug qui s'appelle spiderweb

Itsmil
01/03/2010, 10h49
xsyann a fait un plug qui s'appelle spiderweb


qui c'est lui ? :mrgreen:

clemz
01/03/2010, 11h38
Mais tout en codant ça j'ai réalisé que c'était pas forcément le plus utile. Il y a bien plus simple.
Dans le cas qui t'intéresse c'est pour une toile d'araignée donc on peut honnêtement supposer que la forme de la toile a quelque chose qui ressemble vaguement à un centre et qu'on aura pas un nuage de point complétement aléatoire.
Il suffit de partir d'un point fictif au centre des autres points, de tourner dans le sens qu'on veut et d'accrocher au fur et à mesure les points qu'on rencontre. On les aura ainsi dans l'ordre, convexe ou concave. 8)


Visuellement c'est simple mais à coder. :?:




super Jean-Laurent :) merci de t'être penché sur le prob . mais oui tu as raison peut-être c'est se prendre la tête pour simplement organiser l'ordre des controleurs à notre place .. enfin on va voir :) . j'ai mis ça en dernier sur la liste des trucs à rajouter car je sents que ça pas être facile :boss:



xsyann a fait un plug qui s'appelle spiderweb

ouep il me semblait bien que quelqu'un avait déja fait un essai la dessus :) . mais pour moi c'est just un excercice ;)
et puis , avec tout le respect que j'ai pour le taf de Xs_yann , sa toile d'araignée est trop simple
http://www.xsyann.com/fc4d/toile.jpg
moi je veux plus de controles , plus d'effet toon :art:.

:odile:

Buzhug
01/03/2010, 12h26
Coucou,

je n'ai rien lu de vos posts, ça m'évitera d'avoir mal au crâne.

Ça n'aidera sûrement pas, mais c'est beau :
http://www.espace-sciences.org/science/images/images-maj/Perso/spiderweb/index_spider.html

clemz
01/03/2010, 12h56
ha oué super Buz merci :) :love: . je savais pas qu'il y avait 2 spirales en fait :oops: tu fais chier ! :lol: .. jvais rajouter ça sur ma liste des krukafaire

:odile:

clemz
02/03/2010, 13h11
bon ce qui semblait être simple au début commence à se compliquer un peu ^^ .. j'ai un peu galéré pour gérer la distribution des branches sur la nouvelle enceinte qui au départ était composée que d'une spline donc c'était facile de piloter les positions des branches via cette spline et une valeur 0<->1 sur cette spline . Maintenant il y a autant de splines que de controlleurs , il faut donc passer d'une spline à l'autre dès qu'on dépasse une certaine valeur dépendante du nombre de branches ..etc
Mais je suis pas encore satisfait de la distribution des branches , dans les zones "tendues/étroites" il n'en tient pas compte et du coup ça donne des branches trop proches les unes des autres .. (zone en bas a droite sur l'image )

J'ai rajouter un paramêtre de 'circularité' : ça regarde quelle branche est la plus petite et transfert ce ratio par rapport à chaque branche . on mix l'influence via une DU 0-100%

Pareil, le random de la spirale ne tient pas compte des proximités des branches (on le voit sur la droite de la spirale ) donc faut que je bidouille ça pour que ça fasse "plus régulier dans l'irrégulier" :)

:odile:

edit : 2ème spirale ajoutée

edit 2 : petite vid example : setup example (http://kiteclem35.free.fr/3D/C4D/Spider/SpiderWeb-example.mov) 3.6mo

Jean-Laurent
02/03/2010, 17h58
Joli travail. :poucehaut:

L'histoire de l'enveloppe ne marche pas trop mal.
http://img222.imageshack.us/img222/2996/contours.jpg

En noir c'est le point central autour duquel on tourne pour créer l'enveloppe. Les distributions de points sont aléatoires.
C'est en python mais je devrais pouvoir te mettre ça en coffee. :odile:

clemz
02/03/2010, 18h21
L'histoire de l'enveloppe ne marche pas trop mal.
http://img222.imageshack.us/img222/2996/contours.jpg

En noir c'est le point central autour duquel on tourne pour créer l'enveloppe. Les distributions de points sont aléatoires.
C'est en python mais je devrais pouvoir te mettre ça en coffee. :odile:


yo merci JLo :bounce: . sur certaines de tes images on voit la spline bleue changer de direction alors qu'il n'y a pas de point .. tu serais pas en train d'essayer de couler mon projet toi ? :mrgreen:

nan blague à part c'est super :) . tu as fais ça dans quoi ? ( je reconnais pas l'interface ) tu as programmé ça direct dans un editeur python ?

donc le point noir pourrait être le centre de la toile , c'est cool :art:

bein je veux bien si tu peux coffeeser ça stp :love: :wink:

:odile:

Jean-Laurent
02/03/2010, 19h35
sur certaines de tes images on voit la spline bleue changer de direction alors qu'il n'y a pas de point .. tu serais pas en train d'essayer de couler mon projet toi ? :mrgreen:


Je suis machiavélique mais ce n'est pas vraiment le but. :mrgreen:
Tu as l'oeil, cependant il manque sur toutes les courbes. :wink:
Mais c'est normal. En réalité c'est un point qui est présent mais pas dessiner par la fonction de dessin.
Je n'ai pas corrigé car ce n'est pas vraiment le dessin qui t'intéressait.

Le point noir central c'est pareil. En principe il n'est pas nécessaire. C'est juste le point moyen. Il n'est pas nécessaire qu'il soit au milieu de la toile.

Pour le programme c'est python de chez python.
J'utilise le module de pyton tKinter (un truc comme ça) qui gère les fenêtres, boutons, dessins etc ... de manière très simple.
Je tape tout ça dans un vulgaire éditeur de texte (enfin notpad++). Et je clique juste sur le fichier .py pour le lancer.

Pour donner un exemple le programme qui crée la fenêtre:

fen = Tk() # on appelle le module TKinter en créant une fenêtre nommée fen.
cadre = Canvas(fen, width=320, height=320, bg="light yellow") # C'est l'espace où on va dessiner
bou1 = Button(fen,text='Quitter',command=fen.quit) # C'est le bouton pour quitter mais on pourrait créer tous les boutons qu'on veut.

cadre.create_oval((milieu(points)[0]-3,milieu(points)[1]-3,milieu(points)[0]+3,milieu(points)[1]+3),fill="black") # C'est le code pour le point du milieu en réalité un oval.

dessiner_polygone(contour(points))

fen.mainloop() # Tout ce qu'il y a avant tourne en boucle près à recevoir des instructions, clicks de souris etc ...
fen.destroy() Ferme la fenêtre quand on quitte.


On peut créer toutes sortes de fenêtres très facilement avec toutes sortes de boutons, listes etc ...
Python. :poucehaut:

clemz
02/03/2010, 19h56
ha merci pour le petit pytut :) . il n'existe pas un plug genre resedit pour python ? c'est quand même bien pratique de ne pas se tapper l'interface tout en code :oops: ^^

Gyom
02/03/2010, 22h53
chapeau bas les gars ... mais pareil que Buzhug .. je prefere pas tout lire ;)

sinon Buzhug, merci pour ton lien sur le tissage de la toile
... ca m'epatera toujours qu'une ch'tite bestiole de mere Nature sache trouver le milieu de ses segments sans etre allee a l'ecole !
des generations d'araignees sont mortes de faim d'avoir fait des toiles qui se cassaient la figure
... comme quoi, l'evolution ca fait apprendre la geometrie !

allez ... ben ... bonne chance !