Remplir un disque avec des motifs équidistants

**brunoperel** · 03/06/2010, 07h18

Bonjour,

Après quelques recherches infructueuses sur le Web, je me décide à poster ici...
Je cherche à remplir un cercle avec des motifs. Tout ce que je souhaite c'est qu'ils aient la même taille et qu'ils soient uniformément répartis dans le disque.

J'ai trouvé quelques éléments sur des sites de maths, mais ça me semble très compliqué !

Toute idée sera bienvenue !

**pseudocode** · 03/06/2010, 11h44

On peut avoir un exemple, pour clarifier le problème ?

**brunoperel** · 03/06/2010, 12h08

Certainement.
Ma problématique est la suivante : je cherche à représenter des histoires contenues de magazines. Chaque numéro d'un magazine contient plusieurs histoires. Je voudrais que l’on voie les histoires que l’on trouve dans des numéros de magazines différents.

Chaque point contenu dans un disque représente une histoire d'un magazine. Si une histoire est contenue dans deux numéros de deux magazines différents, alors ce point sera à la fois contenu dans le disque du magazine 1 et le disque du magazine 2...
Pour l'instant je souhaite écrire un algorithme me permettant de dessiner des points dans le disque de façon uniforme. Est-ce que c'est possible ?

**pseudocode** · 03/06/2010, 12h34

Envoyé par brunoperel

Pour l'instant je souhaite écrire un algorithme me permettant de dessiner des points dans le disque de façon uniforme. Est-ce que c'est possible ?

Oui, c'est possible de diverses manières.

Mais pour la suite de ton projet (points contenus dans plusieurs disques), ca limite les solutions possibles. Je te conseille de partir tout de suite sur les algos de layout "force-based", en mettant une force d'attraction vers le centre du gros cercle (magazine) et des forces de repoussement entre les points.

**brunoperel** · 03/06/2010, 13h05

C'est si compliqué que ça ? En cherchant "force-based layout", je tombe principalement sur des articles de recherche !
Je ne veux pas forcément faire quelque chose de dynamique (bien sûr ça serait idéal mais bon...).
Hm, est-ce que si au lieu de disques j'utilisais des ellipses, ça serait plus simple algorithmiquement ou pas ?

**pseudocode** · 03/06/2010, 14h00

Envoyé par brunoperel

C'est si compliqué que ça ? En cherchant "force-based layout", je tombe principalement sur des articles de recherche !
Je ne veux pas forcément faire quelque chose de dynamique (bien sûr ça serait idéal mais bon...).

Ce genre d'algo est dynamique par nature. C'est meme plus simple de faire un algo "dynamique" (qui fait des iterations jusqu'a trouver un équilibre) plutot que de trouver une formule qui donne la position idéale de chaque point (si tant est que ca soit possible)

Hm, est-ce que si au lieu de disques j'utilisais des ellipses, ça serait plus simple algorithmiquement ou pas ?

Je pense que ca serait même plus compliqué.

**brunoperel** · 03/06/2010, 14h07

Bon... Dans ce cas, tentons de réfléchir sur ce que nous souhaitons faire faire à ce fameux programme de force-based layout...

Commençons par créer un cercle. On lui affecte un point c qui est son centre. On souhaite que n numéros soient inclus dans ce cercle.
Si je demande à ce que tous les numéros aient la même force d'attraction vers le centre, ils vont tous se retrouver superposés sur le centre non ? Au mieux, ils vont tous se retrouver alignés le long d'un cercle de même centre que celui de départ... Je ne vois pas trop comment faire en sorte qu'il y ait une maille uniforme !

**Jean Dumoncel** · 03/06/2010, 14h48

Salut,

une question bête, mais si tu réparties des points sur une grille uniforme, est-ce si compliqué de construire les disques englobant chacun de tes ensembles?

Si le réseau de tes disques n'est pas trop compliqué, cela ne sert peut-être à rien de chercher à optimiser, si?

**pseudocode** · 03/06/2010, 14h55

Envoyé par brunoperel

Bon... Dans ce cas, tentons de réfléchir sur ce que nous souhaitons faire faire à ce fameux programme de force-based layout...

Commençons par créer un cercle. On lui affecte un point c qui est son centre. On souhaite que n numéros soient inclus dans ce cercle.
Si je demande à ce que tous les numéros aient la même force d'attraction vers le centre, ils vont tous se retrouver superposés sur le centre non ? Au mieux, ils vont tous se retrouver alignés le long d'un cercle de même centre que celui de départ... Je ne vois pas trop comment faire en sorte qu'il y ait une maille uniforme !

Il faut aussi une force de répulsion qui force les points a s'éloigner les un des autres, ainsi ils ne seront pas superposés.

On peut aussi voir les points comme des palets ronds de petit diamètre, posés sur une table, et qui doivent se regrouper autour d'un centre. Les palets ne peuvent pas se superposer mais doivent rester "a plat" sur la table.

Ou aussi comme des billes dans un entonnoir, vu de dessus.

**Graffito** · 04/06/2010, 00h15

A priori, la meilleure répartition uniforme est donnée par des triangles équilatéraux. 6 triangles équilatéraux formant un héxagone, la solution proposée est basée sur des hexagones concentriques.

Pour remplir le disque, on commence par un hexagone de coté 1, puis on l'agrandit pour obtenir des hexagones de coté 5, puis 7, etc.

Pour un hex coté-1 : F(-1) =1 (centre du cercle)
Pour un Hex coté 1 : F( 1) = 1 + 6
Pour un Hex coté 3 : F( 3) = 1+6+6*2
Pour un Hex coté 5 : F( 5) = 1+6+6*2+6*4
Pour un Hex coté i : F( i ) = F(i-2)+6*(i-1)

Les plus courageux pouront sans doute exprimer F(n) en fonction de n.

Sinon on peut determiner par itération le coté x de l'hexagone tel que le nombre de points n à mettre dans le cercle soit inférieur ou égal à F(x) et supérieur à F(x-2). On repartira ensuite le plus uniformément possible uniformément dans la dernère couronne les points restant : soit n-f(x-2) points à répartir parmi les 6*(x-1) points les plus externes.

Reste juste à ajuster la taille du cercle sur l'héxagone de coté n ou celle des triangles de base à la taille du cercle.

**brunoperel** · 04/06/2010, 12h14

Bon, j'ai trouvé f(n) en fonction de n pour ta suggestion Graffito :

Code :

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

f(n)=6*[((n+1)/2)² - (n-1)/2]

... Par contre cette formule représente seulement les nouveaux triangles que l'on crée a chaque fois qu'on ajoute 2 triangles (cf fichier attaché).

La formule qui donne le nombre de triangles total que l'on peut dessiner avec un hexagone de n unités de coté est :

Code :

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

f(n)=6*[i²/2 - i + 5/2]

ou si on aime les jolies formules :

Code :

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

f(n)=3*[(i-1)²+4]

Voila pour la théorie...
Imaginons que je souhaite représenter 500 numéros.
La solution de notre équation peut etre trouvée ici : entre 13 et 14.
En effet, avec un hexagone de 13 unités de coté, on peut placer 444 numéros, et avec 15 unités on peut en placer 600. Les 14eme et 15eme unités vont donc permettre de placer les 66 restants.
Est-il envisageable de placer les 66 restants en remplissant, en gros, 2 triangles sur 5 parmi ceux de la derniere couronne ?

En tout cas merci pour vos suggestions, j'ai pu avancer !

**pseudocode** · 04/06/2010, 12h25

Envoyé par Graffito

A priori, la meilleure répartition uniforme est donnée par des triangles équilatéraux. 6 triangles équilatéraux formant un héxagone, la solution proposée est basée sur des hexagones concentriques.

Pour résoudre le problème initial du PO, on peut effectivement faire de la tessellation régulière sur un polygone (approximant le cercle).

Après, pour son problème suivant, je ne sais pas si ca sera le plus simple.

**brunoperel** · 04/06/2010, 12h53

Hm, pourtant en y réfléchissant, ca me semble plus simple d'utiliser des hexagones communs que des portions de cercle communes, pour représenter des histoires communes...Non?

**pseudocode** · 04/06/2010, 14h12

Envoyé par brunoperel

Hm, pourtant en y réfléchissant, ca me semble plus simple d'utiliser des hexagones communs que des portions de cercle communes, pour représenter des histoires communes...Non?

Peut-être... Perso, je préfère affecter a chaque histoire une liste de magazines et laisser l'algo se dépatouiller pour afficher "plus ou moins joliment" le résultat, plutôt que de chercher a calculer à chaque fois l'affichage "parfait".

Masi bon, je suis sans doute influencé par les applications de yworks.com que j'utilise.

**Graffito** · 04/06/2010, 15h05

Est-il envisageable de placer les 66 restants en remplissant, en gros, 2 triangles sur 5 parmi ceux de la derniere couronne ?

Si il ya 600-444=156 positions possibles sur la dernière couronne, je placerai le point i (0<=i<66) sur le point Nième point de la couronne (0<=N<156) tel que N = Round(i*156.0/66.0).

**pseudocode** · 05/06/2010, 12h06

En passant, comme ça : vous avez regardé du coté des spirales de Fermat (du genre root-2) ?

**brunoperel** · 08/06/2010, 12h47

Bonjour,

Les spirales de Fermat ? Euh oui, ça a l'air puissant, mais ça a l'air au-delà de mes possibilités d'abstraction mathématique

Je suis parti sur les hexagones. J'ai réalisé une implémentation en PHP : http://ducksmanager.net/storyviewer.php?nb_numeros=1000. Alors j'ai plusieurs problèmes :

La problématique des histoires "périphériques" refait surface. Ce n'est pas aussi simple que je pensais. Pour l'instant les cercles représentant les histoires s'arrêtent quand il n'y en a plus à afficher... Mais du coup l'affichage n'est pas très élégant.
Mon code en pseudo-code :

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
var RAYON=arrondi_superieur(racine(NB_NUMEROS/6));
var cpt=0;
pour j de 0 à RAYON  {
    var dernier=2*RAYON-j;
    pour i de 1 à dernier inclus {
        pour k de -1 à 1 inclus par pas de 2 {
            var pt1;
            pt1->x=((i-1)+j/2)*COTE;
            pt1->y=CENTRE_CERCLE->Y+k*HAUTEUR*j;
            var pt2;
            pt2->x=(i+j/2)*COTE;
            pt2->y=CENTRE_CERCLE->Y+k*HAUTEUR*j;
            var pt3;
            pt3->x=pt1->x+COTE/2;
            pt3->y=CENTRE_CERCLE->Y+k*HAUTEUR*(j+1);
            var pt4=pt3;
            pt4->x+=COTE;
            var centre1=toCenter(pt1, pt2, pt3);
            dessiner_triangle(pt1,pt2,pt3);
            si (cpt<NB_NUMEROS) {
                dessiner_cercle(centre1->x, centre1->y, COTE/10);
                cpt++;
            }
            si (i!=dernier) {
                dessiner_triangle(pt2,pt3,pt4);
                si (cpt<NB_NUMEROS) {
                    var centre2=toCenter(pt2, pt3, pt4);
                    dessiner_cercle(centre2->x, centre2->y, COTE/10);
                    cpt++;
                }
            }
        }
    }
}

On voit vraiment, même quand les triangles ne sont pas visibles, que les motifs ne sont pas inscrits dans un cercle... Ici aussi, il n'y a pas moyen de rendre l'affichage plus élégant ?
Une fois que j'aurai résolu ces problèmes, il faudra que je pense à l'intersection entre deux hexagones, par exemple trouver où, de façon optimale, placer les motifs communs aux deux hexagones ?

J'ai pas fini !

Si quelqu'un a de l'aide à proposer je suis preneur

**pseudocode** · 08/06/2010, 13h58

Envoyé par brunoperel

Les spirales de Fermat ? Euh oui, ça a l'air puissant, mais ça a l'air au-delà de mes possibilités d'abstraction mathématique

(...)

J'ai pas fini !

Si quelqu'un a de l'aide à proposer je suis preneur

Un truc comme ca. Bon, ca ne marche que si tu as suffisamment de points a tracer (N>20 ou 30).

Code java :

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
 
// spiral info
int N = 500;
Point center = new Point(300,300);
int radius = 250;
 
// fermat's constants and scaling
double c = radius/Math.sqrt(N-1), g = 2.399963;
 
// compute points
for(int i=0;i<N;i++) {
	double rho = c*Math.sqrt(i+0.5);
	double theta = g*(i+0.5);
	double x = center.x + rho*Math.cos(theta);
	double y = center.y + rho*Math.sin(theta);
 
	// draw pixel at (x,y)
}

Exemple avec N=100, 500 et 1000

**brunoperel** · 09/06/2010, 09h02

Ah ouais pas mal ! J'ai pu tester, ça marche bien et c'est très élégant, comme j'aime !

Je réfléchis à présent à la manière de réaliser l'intersection entre deux spirales. Mon intuition me dit de transformer le code de placement des points en une fonction mathématique, et de résoudre l'équation entre deux spirales pour déterminer les points communs... Mais je n'arrive pas à pousser plus loin la réflexion, et surtout à la mettre en application.
Quelqu'un a une idée ?

**pseudocode** · 09/06/2010, 09h23

Envoyé par brunoperel

Je réfléchis à présent à la manière de réaliser l'intersection entre deux spirales. Mon intuition me dit de transformer le code de placement des points en une fonction mathématique, et de résoudre l'équation entre deux spirales pour déterminer les points communs... Mais je n'arrive pas à pousser plus loin la réflexion, et surtout à la mettre en application.
Quelqu'un a une idée ?

Ca va être très dur de trouver mathématiquement les points communs a deux spirales de Fermat.

Il vaut mieux une approche graphique.