Circle Packing

Un site de forums contient des forums qui contiennent à leur tour des forums, chacun d'eux servant de conteneur aux discussions entre les utilisateurs. On désire représenter graphiquement un tel site par des cercles imbriqués, à la manière d'une carte démographique. Les critères de représentation peuvent être par exemple le taux de fréquentation, l'activité en nombre de messages ou de discussions, etc.

Dans cette représentation, le site est représenté par un gros cercle centré dans l'animation, dans lequel les cercles représentant ses forums sont placés de manière à ce qu'il n'y ait ni superposition ni dépassement de la bordure du gros cercle, de même pour les forums contenus à l'intérieur d'autres forums.

Le problème peut être décrit ainsi : placer un nombre quelconque de cercles ayant rayons connus dans un cercle parent, de manière à ce que leur surface occupe l'espace maximum disponible dans le cercle parent et qu'il n'y ait ni superposition ni dépassement de la bordure de son cercle parent. Cela permet de placer correctement les forums dans un forum parent, comme montré dans la figure 1-1.

Ce problème est très connu dans le domaine de la recherche opérationnelle, il s'agit du placement des cercles (Circle Packing). L'équipe de Mr Huang a proposé une heuristique (1) inspirée d'une stratégie du jeu de go qui permet de trouver une solution approchée de bonne qualité en temps raisonnable. L'objectif de cet article est d'appliquer cette heuristique et de développer un logiciel en PHP pour intégrer dans la gestion des forums chez Developpez.com.

Le problème du placement de cercles dans un conteneur à deux dimensions et de forme particulière (cercle, rectangle, carré, etc.) est un problème étudié depuis les années 60, ceci à cause des applications qu'il offre dans plusieurs domaines. Il consiste à placer des cercles dans un conteneur sans chevauchement en optimisant certains objectifs.

Pour simplifier le problème, cet article ne discute que le cas où le conteneur est circulaire, ce qui est le modèle de « Représentation de forums ».

Pour résoudre le problème, on va utiliser l'algorithme très simple : MHD(2). Le fonctionnement de l'algorithme est donné dans le chapitre 2.

Définition : Un cercle simple est un cercle tout seul.

Définition : Un cercle imbriqué C désigne un cercle parent contenant des cercles fils C1..Cn, qui peuvent être des cercles simples ou des cercles imbriqués.

Modèle : Étant donné un cercle imbriqué de plusieurs niveaux et des cercles simples de rayons connus, minimiser les rayons des cercles imbriqués de chaque niveau.

Résolution : On suppose que l'on a un algorithme configure qui peut trouver le rayon minimal du cercle imbriqué d'un niveau, puis on l'applique sur chaque niveau de cercles de l'intérieur à l'extérieur, donc on peut résoudre le problème par l'algorithme configure_récursive ci-dessous :

configure_recursive(C:   un cercle imbrique)
Debut
    Pour chaque fils F de C  faire
        Si F est un cercle imbrique
        Alors
            configure_recursive(F);
        Finsi;
    Finpour;
    configure(C);
Fin

On continue le travail par détailler l'algorithme configure.

Modèle : Étant donné un ensemble de cercles ayant le rayon fixé, trouver le rayon minimal du conteneur circulaire pouvant les contenir de façon à ce qu'il n'y ait aucune superposition.

Résolution : On résout ce problème sur un autre point de vue. On suppose que l'on a l'algorithme MHD (Maximum Hole Degree détaillé plus loin), qui va insérer l'ensemble des cercles dans le conteneur fixé, retournant succès quand tous les cercles peuvent être insérés. On redéfinit le rayon du conteneur et on essaie d'insérer des cercles par MHD. On répète l'opération ci-dessus en utilisant la stratégie dichotomie pour trouver un petit rayon ayant la précision donnée (cf. figure2-2).

configure (C:    un cercle imbrique)
Variable
    MaxR := la somme de rayons des fils directs du C;
    MinR := le rayon du cercle correspondant dont la surface est egale a la somme des 
             surfaces des fils directes du C;
    C0: un cercle imbrique qui n'a pas fils;
Debut
    Repete
        Si MHD(C.fils, C0)
        Alors
            MaxR := C0.R;
        Sinon
            MinR := C0.R;
        Finsi;
        C0.R := (MaxR+MinR)/2;
    Jusqu'a C a la precision donnee et MHD est successif;
    C := C0;
Fin

L'heuristique MHD est inspirée d'une stratégie du jeu de go : « Gold corner, silver side and grass middle ».

L'expérience des êtres humains montre que les bénéfices de placer un objet dans différentes positions à l'intérieur du conteneur sont différents. Les positions aux coins sont plus avantageuses que celles au milieu du conteneur.

Autrement dit, il est possible de résoudre le problème de placement des cercles en recherchant le meilleur coin. Nous allons définir une position au coin dans cette situation et détailler ci-dessous la démarche.

Définition : Supposons que l'on ait n cercles C1..Cn à placer dans le conteneur C0. Une configuration contient m cercles déjà placés sans chevauchement dans le conteneur et il reste à placer n-m cercles.

Définition : Étant donné une configuration, une position au coin de Ci est une position où Ci touche deux éléments sans chevaucher les autres cercles dans le conteneur. Un élément peut représenter soit un autre cercle, soit la bordure du conteneur.

Définition: La distance de deux éléments (des cercles, la position ou le conteneur) est la distance plus courte de ces deux éléments, notée dist(E1, E2).

Définition : Étant donné une liste des positions aux coins P1..Pn du cercle Ci dans une configuration. La distance minimale de Pi, notée dmin(Pi), est distance minimale avec les autres éléments qui ne sont pas les deux éléments que Pi doit toucher.

Donc dmin(Pi)=min{dist(Cj, Pi), Cj n'est pas Ci, ni les éléments que Pi doit toucher}, montré en figure 2-3-3.

Définition : Le trou minimal de Ci, noté Tmin(Ci), est la valeur minimale des distances des positions aux coins du Ci.

Donc Tmin(Ci) = min{dmin(Pj de Ci), j =1..k}.

Modèle : Étant donné un conteneur circulaire C0 avec son rayon fixé R0. On va insérer dans C0 un ensemble de cercles C1..Cn qui sont fils directs du cercle imbriqué C.

Résolution : Chaque fois que l'on insère Ci, trouver sa position aux coins possibles, calculer les distances minimales des positions au coin, insérer Ci sur la position qui provoque le trou minimal. On échoue quand il n'y a pas de position au coin, autrement dit, on ne peut plus insérer aucun cercle dans C0. On réussit quand tous les fils de C peuvent être insérés dans C0.

MHD(C1..Cn des cercles, C0:      un cercle imbrique avec aucun fils)
Variable:
Debut
    Initialiser la configuration par inserer C1 et C2 dans C0.
    Pour i allant de 3 a n faire
        calculer la position au coin par la configuration courant;
        S'il existe des positions aux coins
        Alors
             trouver la position P dont la distance minimale est plus petite;
             inserer Ci Sur P dans C0;
        Sinon
             retourne faux;
        Finsi;
    Finpour;
    retourne vrai;
Fin

La figure 3-1 introduit les classes de gestion des cercles qui servent à représenter les cercles imbriqués, ainsi que l'algorithme dont il est question ci-dessus.

• Circle représente les données d'un cercle simple ;
• Nested, une sous-classe de Circle, représente les données d'un cercle imbriqué ;
• Position, une sous classe de Circle, représente la position au coin ;
• Algo représente l'algorithme MHD ;
• Forum, l'extension de Nested, représente les données d'un forum.

<?php
set_time_limit(0);
date_default_timezone_set('Europe/Paris');

function __autoload($class)
{
    require_once strtr($class, '_', '/').'.php';
}
    
$c = new Circle_Nested();
$c1 = new Circle_Nested();
$c2 = new Circle_Nested();
$c3 = new Circle_Nested();
$c1->r = 30;
$c2->r = 40;
$c3->r = 50;
$c->append($c1);
$c->append($c2);
$c->append($c3);
$c->pack();
echo $c;
/* le resultat:
Circle([x]=0 [y]=0 [r]=90.0147098681 
     children[0]=Circle([x]=-40.0147098681 [y]=0 [r]=50) 
     children[1]=Circle([x]=49.9485289806 [y]=2.57209172824 [r]=40)
     children[2]=Circle([x]=15.0009492863 [y]=-58.0799212104 [r]=30)
)
*/
$c_absolue = $c->getDrawableCopy(200, 200);
/*le résultat: 
Circle([x]=200 [y]=200 [r]=90.0147098681
   children[0]=Circle([x]=159.985290132 [y]=200 [r]=50)
   children[1]=Circle([x]=249.948528981 [y]=202.572091728 [r]=40)
   children[2]=Circle([x]=215.000949286 [y]=141.92007879 [r]=30)
)
*/

<?xml version="1.0" encoding="UTF-8" ?>
<forums>
    <forum name="Bienvenue au club des développeurs" threads="2100" messages="74190" views="3385015">
        <forum name="Mode d'emploi &amp; aide aux nouveaux" threads="459" messages="3042" views="806953"/>
        <forum name="Evolutions du club" threads="266" messages="4834" views="926371"/>
        <forum name="La taverne privée du Club : Humour et divers" threads="1375" messages="66314" views="1651691">
            <forum name="Films &amp; TV" threads="175" messages="4982" views="106532"/>
            <forum name="Jeux" threads="241" messages="11032" views="225946"/>
            <forum name="Lectures" threads="57" messages="1587" views="35432"/>
            <forum name="Musique" threads="98" messages="2560" views="47508"/>
            <forum name="Politique" threads="146" messages="10021" views="188520"/>
        </forum>
    </forum>
</forums>

Comme vous pouvez le voir, la gestion des cercles imbriqués est très simple, tout ce que vous devez faire est de donner les cercles, leur rayon et les relations d'appartenance. Puis vous appelez la méthode pack() de Nested pour ranger les cercles par la stratégie de MHD. Vous pouvez consulter le résultat en texte en appelant directement echo.

La figure 3-2 introduit les classes de représentation graphique des forums. C'est en fait une application de gestion des cercles.

• Forum, classe étendue de Nested, représente les données d'un forum ;
• ForumIterator est l'itérateur de forums ;
• Image, une classe générale, représente graphiquement les forums ;
• Png, une sous classe d'Image, représente les forums en PNG ;
• Flash, une sous classe d'Image, représente les forums en Flash.

<?php
set_time_limit(0);
date_default_timezone_set('Europe/Paris');

function __autoload($class)
{
    require_once strtr($class, '_', '/').'.php';
}

$iterator = new ForumIterator('forums.xml', ForumIterator::DATA_VIEWS);
$png = new Image_Png($iterator, 1100, 'fonts/arial.ttf');
$png->saveAs('output1.png');

$iterator->path('Java');
$png2 = new Image_Png($iterator, 800, 'fonts/arial.ttf');
$png2->saveAs('output2.png');

$flash = new Image_Flash($iterator, 1100, 'fonts/vera.fdb');
$flash->saveAs('output.swf');

echo $png2;

La représentation de forums est simple : vous créez un itérateur de forum en lui donnant un fichier XML et les données qui vous intéressent. À l'aide de cet itérateur, vous pouvez créer des fichiers PNG et Flash comme vous voulez. Puis vous les affichez ou les sauvegardez.