Navigation – Plan du site
2015
736

Génération de semis de points fractals : une méthode du comptage de boites inversée

Cyril Fleurant

Résumés

En géographie, la dimension fractale est très utilisée pour caractériser la structure d’objets géographiques tels que les structures urbaines ou les réseaux hydrographiques. En revanche elle ne l’est pas ou peu pour les objets ponctuels tels que les semis de points. Dans cette étude nous proposons une méthode pour produire des semis de points fractals. La procédure consiste à inverser la méthode dite du comptage de boites. Cette procédure s’est révélée fiable puisque l’erreur relative entre les dimensions fractales théoriques et produites n’excède pas 2% lorsque la structure de l’objet à produire est assez fine. Au-delà de son objectif initial de créer des semis de points fractals, cette méthode permet également d’explorer les liens qui existent entre la dimension fractale et les méthodes classiques d’analyse spatiale en géographie.

Haut de page

Texte intégral

L’auteur souhaite adresser ses remerciements à Jon Burley (Professor in Landscape Planning, Michigan State University - USA) pour nos échanges sur la réhabilitation/re-végétalisation des carrières, ainsi qu’aux trois lecteurs anonymes qui ont contribué à l’amélioration de cet article.

Introduction

1Fractals Everywhere! C’est le titre du livre de Barnsley, publié en 1993, dans lequel l’auteur nous montre que notre environnement est composé d’un grand nombre d’objets fractals. Ces objets, qu’ils soient naturels ou d’origine anthropique, sont caractérisés par la complexité de leur forme et s’organisent à des échelles spatiales très variées. Il peut s’agir par exemple de végétaux, de structures urbaines ou encore de réseaux hydrographiques. Dans la modélisation des processus géographiques, la forme complexe des objets est souvent un facteur limitant. En effet, modéliser l’écoulement dans un tuyau est toujours plus facile que dans un sol car la géométrie du tuyau est simple, contrairement à celle du sol.

2Les outils quantitatifs qui permettent de décrire la complexité des formes naturelles qui nous entourent sont limités du fait de l’indifférence des sciences à l’égard des formes pendant des siècles. En sciences physiques, les formes compliquées ont été réduites à leur centre de gravité, donc à un point. Tout le monde se souvient de cet enseignant de sciences physiques au lycée proposant d'assimiler cette voiture à son centre de gravité pour appliquer la résultante des forces qui s’y exercent. En mathématiques, les objets trop irréguliers, trop discontinus ont longtemps été considérés comme des « monstres mathématiques » (Volkert, 2008) ou encore des « plaies lamentables » (Lettre de Charles Hermite à Thomas Stieltjes, 1893). Les domaines « nobles » des sciences dures comme la physique relativiste et la physique quantique s’intéressent principalement, et depuis toujours, respectivement au macrocosme et au microcosme. Les formes de la géographie qui appartiennent à des échelles intermédiaires, ont été négligées pendant des siècles. Il n’est donc pas étonnant que les théories morphologiques, développées pour beaucoup dans les années 1960, soient encore balbutiantes à proposer des modèles qui décrivent correctement les formes qui nous entourent. S’il est vrai que les formes à l’échelle géographique sont « changeantes, variées, diverses et donc complexes et difficiles à modéliser » (Boutot, 1993), qu’elles ont une notion fondamentalement qualitative, on peut penser que la jeunesse des théories morphologiques est une des causes principales des difficultés rencontrées pour les modéliser.

3Face à l’indifférence des sciences dures pour les formes pendant des siècles, des théories dites morphologiques sont apparues dans les années 1960. Il s’agit de la théorie des catastrophes qui s’intéresse aux aspects continuité/discontinuité (René Thom, 1968), de la théorie du chaos et de ses formes irrégulières et chaotiques (initiée par Henri Poincaré à la fin du XIX siècle et formalisée par James York et Tien-Yien Li, 1975), de la théorie des structures dissipatives décrivant les processus d’auto-organisation (Ilya Prigogine, 1960) ou encore de la géométrie fractale (Benoit Mandelbrot, 1960).

4Les fractales ont été observées à la fin du XIX siècle, bien que le terme "fractal" ait été attribué bien plus tard. Ces objets mathématiques particuliers ont été considérés comme de simples curiosités pendant très longtemps et ont été au cœur d’une nouvelle branche des mathématiques dans la seconde moitié du XX siècle, grâce au travail du mathématicien Benoît Mandelbrot (1924-2010). Durant son travail de recherche chez IBM sur l’optimisation du signal des objets bruités, il découvre des lois d’invariance entre les courbes de prévision des prix à court et à long termes. Le génie de Benoit Mandelbrot fût de faire le lien entre les formes d’objets très variés, complexes par leur nature et leur échelle, et d’unir leur description dans une nouvelle géométrie. Le mot fractal vient du latin fractus qui signifie cassé, brisé. Cette géométrie fractale s’intéresse donc aux objets dont l’irrégularité ne permet pas de les décrire correctement avec la géométrie classique dite euclidienne. La géométrie fractale s’est imposée très rapidement dans de nombreux domaines scientifiques comme un outil fondamental de description des objets. Cette véritable explosion scientifique s'est déroulée notamment après la sortie du livre fondateur « The Fractal Geometry of Nature » (Mandelbrot, 1982). De nombreuses références montrent la grande variété d’utilisation de cette géométrie et de ses applications dans les sciences de la Terre (Turcotte, 1997 ; Rodriguez-Iturbe & Rinaldo, 2001 ; Chandrasekhar et al., 2013 ; Barton, 2013), en géographie (Frankhauser, 1994 ; Dauphiné, 2000 ; Dauphiné, 2011, Tannier & Thomas, 2013), dans les sciences de l’ingénieur et de la physique (Nakagawa, 1999 ; Kozlov et al., 2013), dans les sciences de la vie (Brent & Russ, 2012) mais aussi par des ouvrages de vulgarisation scientifique (Barnsley, 1993 ; Sapoval, 2001 ; Mandelbrot, 2009).

5L’étude proposée ici s’intéresse à la modélisation en géographie fractale (Dauphiné, 2011). La géométrie fractale est utilisée pour décrire la structure d’objets, mais également pour en produire (Tannier et al., 2012). Si la production de ces formes fractales est assez commune pour des objets tels que des structures urbaines, des arborescences ou encore des réseaux, elle l’est beaucoup moins pour des semis de points. Or, les semis de points sont des éléments importants dans les structures géographiques puisqu’ils représentent des objets et/ou des lieux géographiques. Les problématiques spatiales qui y sont associées nécessitent souvent une analyse de leur localisation, de leur distribution et de leurs interactions (Pumain & Saint-Julien, 2010). L’objet de notre étude est de présenter une méthode originale pour générer des semis de points dont l’organisation est contrôlée par la notion de fractalité. Après avoir détaillé la démarche conceptuelle de cette méthode, donné les limite de son utilisation, nous présentons un exemple d’application en lien avec une problématique d’aménagement de l’espace par des végétaux. En effet, l’organisation spatiale des objets de notre environnement et/ou de ses structures – végétation, trames vertes, réseau de transport, habitat – est au cœur des préoccupations des géographes (Fernandes et al., 2011). Si les chercheurs veulent comprendre les processus, les dynamiques qui façonnent ces formes, les aménageurs et les ingénieurs souhaitent quant à eux pouvoir utiliser des outils pour produire et gérer l’espace. Sur le plan de l’aménagement par exemple, il existe une forte demande de l’utilisation de modèles mathématiques pour contrôler l’organisation spatiale de la plantation de végétaux. La demande est tout particulièrement importante aux États-Unis concernant la réhabilitation des carrières et mines à ciel ouvert (Lehmann et al., 2013, Burley, 2007). Dans ces projets de réhabilitation, les exploitants ont pour obligation de faire appel à des aménageurs pour re-végétaliser les carrières afin qu’elles retrouvent une bonne intégration visuelle dans le paysage. Pour ces aménageurs se pose la question de la méthode pour replanter. En effet, la méthode de re-végétalisation doit permettre aux aménageurs de créer une structuration spatiale des végétaux qui lui donne un aspect « naturel ».

Méthodologie : une méthode du comptage de boites inversée pour générer des semis de points

Calcul de la dimension de fractales mathématiques

6Dans son ouvrage de référence, Mandelbrot ( 1982) montre les limites de la géométrie euclidienne pour décrire les objets naturels qui composent notre environnement. La géométrie fractale est en fait une synthèse de nombreux travaux concernant les monstres mathématiques déjà pointés du doigt par le passé par des mathématiciens comme Cantor, Péano, Lebesgue ou encore Hausdorff. Un objet fractal peut être défini par les caractéristiques suivantes :

  • sa structure est "fine", à toute les échelles d’observation ;

  • sa structure est trop irrégulière pour être décrite par la géométrie euclidienne ;

  • il a la propriété d’être auto-similaire ou auto-affine (homothéties internes) ;

  • il a une dimension, dite fractale, qui est toujours supérieure à sa dimension topologique.

7Le flocon de von Koch (Figure 1) illustre bien les caractéristiques des fractales : il est utilisé en géographie comme modèle mathématique de fractales naturelles que sont les côtes du littoral. Ce flocon de von Koch est facile à concevoir, comme la majorité des fractales mathématiques d’ailleurs; C’est un des nombreux paradoxes qu’elles soulèvent : leur complexité est générée à partir de règles simples. Cette complexité est produite par la propriété d’autosimilarité : la structure reste identique à toutes les échelles. Un autre paradoxe intéressant est la relation entre le périmètre du flocon de von Koch et son aire. En effet, on peut montrer relativement facilement qu’à l’itération n, le périmètre Ln et l’aire An du flocon de von Koch, dont la longueur du côté du triangle initial est l’unité, valent respectivement :

Image 10000201000000B90000006733AB621B.png

En faisant tendre l’itération n vers l’infini on voit clairement que le périmètre Ln tend vers l’infini et que l’aire An tend vers une valeur constante Image 1000020100000064000000239340C29A.png.

8Toutes ces fractales sont caractérisées par leur dimension fractale. En réalité il existe plusieurs dimensions fractales (par exemple, la dimension de Hausdorff-Besicovitch ou encore la dimension de Minkowski-Bouligand) mais c’est la dimension fractale dite d’homothétie interne qui est la plus répandue car la plus aisée à calculer. En effet, si une fractale est décomposable en N parties dans un rapport d’homothétie de r du tout, alors sa dimension fractale est donnée par l’équation (1).

Image 100002010000006B00000028E0B213F3.png

9Ainsi, pour le flocon de von Koch, chaque côté du triangle est divisé par r = 3 et on ajoute deux segments de plus ce qui fait N = 4 segments, donc :

Image 10000201000000D80000002E2F7C2142.png

Figure 1 : Le flocon de von Koch s'obtient en partant d'un triangle équilatéral et en positionnant de façon récursive des triangles équilatéraux plus petits d’1/3 sur chacun des côtés.

Image 1000000000000136000001C4B9042856.jpg

Le triangle initial (initiateur) correspond à l’itération 0, nous avons donc dessiné ici 4 itérations grâce à un script écrit sous le logiciel R. Le flocon de von Koch est la fractale correspondant à une infinité d’itérations.

Calcul de la dimension de fractales naturelles

10Il existe de nombreuses autres fractales mathématiques toutes merveilleusement complexes et paradoxales. Parmi les plus célèbres on notera les poussières de Cantor, les tapis de Sierpiñski ou encore les éponges de Menger. Ces fractales mathématiques sont des objets théoriques et les fractales naturelles rencontrées dans notre environnement ont des propriétés moins « extrêmes ». Par exemple, leur propriété d’autosimilarité ne s’étend que sur quelques ordres de grandeur seulement – l’infini n’ayant pas de sens dans la réalité des objets qui nous entourent. Cette propriété est de plus statistique, c’est-à-dire que d’une échelle à l’autre elle n’est pas exactement la même. Pour illustrer le concept de fractales naturelles, prenons l’exemple certes classique mais pertinent de la côte bretonne. Quelle est donc la longueur de cette côte ? Il y a plusieurs réponses à cette question qui dépendent du moyen utilisé pour parcourir cette distance (Figure 2). Suivre la côte avec un avion rapide à haute altitude, qui ne peut donc suivre que grossièrement la ligne de côte, indique une distance d'environ 550 km. En revanche, avec un ULM, beaucoup plus lent et à basse altitude, ce chiffre monte à 670 km, car l’aéronef pourra suivre les côtes plus précisément. On comprend que si le chemin est parcouru à pied en suivant la côte par les sentiers, la distance indiquée par notre podomètre sera plus grande encore. La côte bretonne est une fractale naturelle et sa longueur dépend de l’échelle d’observation du géomètre.

Figure 2 : Suivi de la côte bretonne avec un avion rapide (en rouge) et un ULM (en jaune).

Image 100000000000055C000003DBE8755D5F.jpg

Les trajets rouge et jaune, calculés avec Google Earth, sont respectivement de 550 km et de 670 km.

11Si la côte bretonne est une fractale, elle doit avoir une dimension fractale. Or, dans le cas des fractales naturelles, on ne connaît pas le mode de construction de l’objet, on ne peut donc pas utiliser une équation analytique comme pour la dimension d’homothétie interne (équation 1). Le calcul de la dimension fractale se fait donc par le biais de méthodes qui explorent la structure de la fractale à différentes échelles. C’est le cas par exemple de la méthode du comptage des boites. Cette méthode est décrite dans de nombreuses références (e.g. Frankhauser, 1994 ; Rodriguez-Iturbe & Rinaldo, 2001) et adapte l’équation (1) de la façon suivante :

Image 10000201000000670000001979473E4C.png

12Avec N, le nombre de boites pleines, ε, la taille de la boite, D, la dimension fractale et K, une constante. L’équation (2) peut également s’écrire à une constante près :

Image 100002010000006B0000002EC19B24EB.png

13L’équation (3) est similaire par la forme à l’équation de la dimension d’homothétie interne (équation 1) mais sur le fond la méthodologie employée est bien différente. En effet, la méthode consiste à appliquer successivement sur l’objet que l’on étudie un quadrillage de plus en plus fin et à compter à chaque itération le nombre de boites pleines, i.e. le nombre de boites contenant au moins une partie de l’objet à mesurer (Figure 3). Ensuite, on trace le graphe des points de coordonnées (1/εi, Ni) sur une échelle bi-logarithmique. La pente de la droite de régression linéaire, correspond ainsi à la dimension fractale de l’objet (Figure 4).

14Toutefois la détermination de cette dimension n’est pas aussi facile qu’il n’y paraît car la régression linéaire ne doit pas se faire sur l’ensemble des points, mais seulement sur ceux correspondant à la zone de fractalité de l’objet. Cette zone de fractalité est comprise entre deux coupures dites inférieure et supérieure. La coupure supérieure est atteinte lorsque le maillage est assez fin pour commencer à prendre en compte la structure de l’objet : c’est le cas ici à l’itération 1 où l'on voit apparaître une boite vide. Avant la coupure supérieure, la pente de la droite de régression est égale à 2 : toutes les boîtes du quadrillage sont pleines, leur nombre augmente avec le carré de leur taille. Pour des boîtes de taille plus petite que la coupure inférieure, la pente est égale à 1 car le nombre de boîtes pleines augmente proportionnellement à la taille des boîtes. Les points n'appartenant ni à la droite de pente égale à 2 ni à celle de pente égale à 1, sont donc des points qui décrivent la fractalité de l'objet étudié. Dans cette zone de fractalité, la pente est égale à la dimension fractale. La détermination de la dimension fractale revient alors à identifier la zone d’alignement le plus rigoureusement possible. Ceci s’avère délicat car l’étendue de la fractalité est souvent réduite pour des fractales non mathématiques, donc les objets de notre environnement. La détermination des limites de la zone caractérisant le comportement scalant (coupures supérieure et inférieure) apparaît donc essentiel pour identifier cette étendue. Pinnaduwa et al., 1997 indiquent que la mesure par comptage de boites de la plupart des objets naturels révèle le même type de comportement. Il précise « qu’une des questions les plus critiques lorsqu’on applique la méthode des boites à la mesure d’un objet naturel, est l’identification de la taille des boites à partir de laquelle le nuage de points est aligné dans le graphe en bi-logarithmique. Ce rang est dépendant de l’ordre d’autosimilarité, du facteur de réduction et certainement des coupures inférieure et supérieure caractéristiques ». Il faut ici rappeler la notion de fréquence de coupure et son interprétation intuitive. Comme l’indique Sapoval(2001), la détermination des coupures inférieure et supérieure, « c’est à dire de la plus petite taille non fractale et de la taille jusqu’à laquelle la géométrie est fractale », peut constituer une caractérisation utile. Dans sa discussion sur la longueur de la côte bretonne, Mandelbrot (1982) définit les notions de coupures externe et interne qui limitent l’étendue du comportement scalant d’un objet fractal.

Figure 3 : Principe de la méthode du comptage de boites.

Image 100000000000056A0000056A77815AA4.jpg

A chaque itération un maillage de plus en plus fin est apposé afin de délimiter la structure de l’objet à mesurer. Le processus s’arrête lorsque la finesse du maillage ne permet plus d’apporter d’informations supplémentaires sur la structure de l’objet : ici à l’itération 3 il y a 1 point par boite.

Figure 4 : La dimension fractale est ensuite calculée en traçant l’évolution du nombre de boites pleines (N) en fonction de la taille des boites (ε).

Image 1000000000000340000001D8E59F1F25.jpg

L’exemple présenté ici est illustratif de la méthode, le petit nombre d’itérations dans la zone de fractalité de l’objet est insuffisant pour calculer une dimension fractale représentative.

Inverser la méthode de comptage de boites pour générer des semis de points

15On fait ici l’analogie entre le quadrillage formé par les boites et une représentation matricielle (Figure 5). Ainsi une matrice (2×2) est un quadrillage de 4 boites, une matrice (4×4) est un quadrillage de 16 boites et ainsi de suite. On impose la règle suivante : lorsqu’une boite est pleine, c’est-à-dire qu’elle contient tout ou partie d’un objet, l’élément correspondant de la matrice est égal à la valeur 1, sinon il vaut 0.

A l’itération 0, la taille de l’unique boite est égale à l’unité et elle est par définition pleine puisqu’elle contient entièrement l’objet fractal que l’on souhaite générer. Le passage à l’itération 1 se fait en divisant les dimensions de la boite par deux, nous obtenons ainsi 4 boites, soit une matrice (2×2). A ce stade, le nombre total de boites est Image 100002010000003D000000175E951A5E.png et le nombre de boites pleines est égale à Image 1000020100000034000000187BFDF0D7.png puisque aucun processus de transformation des boites pleines en boites vides n’a été initié. Ce processus consiste à déterminer pour chaque itération, les nombres de boites vides et pleines. Ces nombres sont calculés à partir de l’équation (2) que l’on peut réécrire de la façon suivante :

Image 10000201000000730000001BD447FD43.png

Ainsi, à chaque itération k, il existe une relation entre le nombre de boites pleines Image 100002010000002000000017B33161D0.png, la dimension fractale (D) et la taille de la boite (Image 10000201000000100000000FE156DBED.png). Pour chaque itération on peut donc écrire :

Image 10000201000000E90000001C687C15F1.png

Or on connaît les liens entre les tailles successives Image 10000201000000100000000FE156DBED.png :

Image 10000201000000DF00000023D6140B75.png

16En associant les équations (5) et (6) on a donc successivement :

Image 10000201000000EB00000025AF0C8926.png

17et

Image 10000201000000AB00000028600F6912.png

18Le passage de l’équation (7) à l’équation (8) ne peut se faire que si ε0 est non nul, ce qui est évidemment toujours le cas puisque ε0 représente la taille de la boite initiale qui contient l’objet à étudier.

On sait que le nombre de boites pleines à l’itération 0 vaut 1, donc Image 100002010000003400000018B96AEED7.png. Ainsi de l’équation (8) on peut déduire que :

Image 10000201000000A40000001B598F7095.png

19Or à chaque itération, on divise la taille de la boite par deux, on multiplie donc le nombre de boites par 4. Ainsi on peut en déduire le nombre total de boites à chaque itération et par soustraction de l’équation (9) le nombre de boites vides à chaque itération :

Image 10000201000000D500000033E5806D48.png

Figure 5 : Analogie entre le quadrillage de la méthode des boites et la représentation matricielle nécessaire à la programmation informatique de la méthode présentée ici.

Image 10000000000002C00000014E6C391422.jpg

Une boite pleine dans le quadrillage (ligne noire épaisse) correspond à la valeur 1 de l’élément matriciel correspondant.

Résultats

Procédure de génération des semis de points

La mise en œuvre de la méthode se fait par le biais d’un script écrit avec le gratuiciel R (R Development Core Team, 2008). Ce script est donné en annexe et peut-être demandé par courriel à l’auteur. Le principe de la procédure est le suivant (on prend ici l’exemple de 3 itérations et d’une dimension fractale de D = 1.3. Les notations Image 100002010000003C00000019E1C8F603.png et Image 100002010000001400000013B815EE5E.png indiquent respectivement le nombre total de boites à l’itération k, le nombre de boites pleines à l’itération k et le nombre de boites vides à l’itération k) :

Image 100002010000027E000001E6002B3370.png

Cette procédure matricielle et itérative permet de produire l’objet fractal pour un nombre d’itérations préalablement donné, qui est donc noté Image 100002010000001500000017EFC82A6B.png, n étant l’itération finale. Ce nombre correspond à la valeur de la coupure inférieure, c’est-à-dire l’itération à partir de laquelle il n’est plus nécessaire d’avoir un maillage plus fin car le nombre de boites pleines reste constant. La valeur de cette itération finale (équation 10) est calculée à partir de l’équation (9) pour la valeur du nombre total de points que l’utilisateur souhaite.

Image 10000201000000880000002657E8A2A1.png

Plusieurs simulations ont été réalisées pour Image 100002010000001500000017EFC82A6B.png = 10 (Figure 6), Image 100002010000001500000017EFC82A6B.png = 100 (Figure 7), Image 100002010000001500000017EFC82A6B.png = 1000 (Figure 8) et Image 100002010000001500000017EFC82A6B.png = 10000 (Figure 9). Pour chacun de ces objets fractals, la dimension fractale théorique de la procédure est successivement de 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8 et 1.9. Les boites pleines à l’itération finale n ont été colorées en noir afin de visualiser la forme de l’objet fractal produit.

On constate que la génération des objets fractals pour différentes dimensions ne demande pas le même nombre d’itérations, puisque ce nombre dépend à la fois du nombre final de boites pleines souhaité et de la dimension fractale (équation 10). De plus, pour un nombre final donné de boites pleines Image 100002010000001500000017EFC82A6B.png, le nombre d’itérations n diminue lorsque la dimension fractale D augmente. Il est en effet logique que si on souhaite avoir un même nombre final de boites pleines Image 100002010000001500000017EFC82A6B.png pour un objet dont la structure fractale est différente, la taille des boites doit également être différente. En augmentant le nombre d’itérations, on diminue la taille des boites, ce qui permet d’avoir un plus grand nombre de boites pleines sans pour autant augmenter la dimension fractale.

Figure 6 : Génération d’objets fractals avec 10 boites pleines finales.

Image 100000000000056A0000056AFFBD6382.jpg

Les dimensions fractales théoriques sont D = Image 100002010000005D0000003A53974887.png, ce qui correspond à l’itération finale n = Image 100002010000004300000038F089C325.png.

Figure 7 : Génération d’objets fractals avec 100 boites pleines finales.

Image 100000000000056A0000056AAF123843.jpg

Les dimensions fractales théoriques sont D = Image 100002010000005C000000384AEB4319.png, ce qui correspond à l’itération finale n = Image 1000020100000041000000396C2E30E7.png

Figure 8 : Génération d’objets fractals avec 1 000 boites pleines finales.

Image 100000000000056A0000056AC15B792B.jpg

Les dimensions fractales théoriques sont D = Image 100002010000005C00000037E2F776E6.png, ce qui correspond à l’itération finale n =Image 10000201000000410000003748133C93.png.

Figure 9 : Génération d’objets fractals avec 10 000 boites pleines finales.

Image 100000000000056A0000056AE419F63E.jpg

Les dimensions fractales théoriques sont D = Image 100002010000005D0000003715C11862.png, ce qui correspond à l’itération finale n = Image 100002010000005500000037D4C10DC9.png.

Analyse de la fiabilité de la méthode

20Dans la procédure de génération des objets fractals par la méthode du comptage de boites inversée, le calcul d’arrondi du nombre final d’itérations n engendre une erreur sur le nombre de boites à placer à chaque itération, ce qui conduit à une approximation de la valeur de la dimension fractale.

Pour illustrer cet enchaînement d’erreurs, prenons l’exemple de la génération d’un objet de 10 boites pleines finales (Figure 6). Dans la procédure de génération des objets fractals, la première étape est de calculer le nombre d’itérations nécessaire pour produire ces boites pleines pour une dimension fractale donnée. Cette étape se fait par l’intermédiaire de l’équation (10). Prenons par exemple le cas de la dimension fractale théorique D = 1.2, dans ce cas le nombre final d’itérations est Image 100002010000005E00000024600C772F.png = 2.76. Ce nombre réel doit évidemment être arrondi par un nombre entier, ce qui conduit à n = 3. Ce nombre final d’itérations permet de calculer les nombres de boites pleines et vides par l’équation (9). Ces nombres sont également des réels qu’il faut transformer en nombres entiers de boites. Dans l’exemple présenté ici, pour une dimension fractale théorique de D=1.2, à l’itération n = 3, on aura 2nD = 23×1.2 = 12.12 boites pleines. Un calcul d’arrondi est effectué pour déterminer l’entier le plus proche, soit 12 dans cet exemple précis. On constate que, si dans la procédure de départ, on souhaitait générer un objet de 10 boites pleines, on en a en fait produit 12. Cette erreur d’arrondi engendre donc un écart entre la dimension fractale théorique et la dimension fractale produite par la procédure de calcul. Ces écarts sont représentés sur la Figure 10 pour des objets de 10, 100, 1 000, et 10 000 boites pleines finales et pour les dimensions fractales théoriques de 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8 et 1.9. On constate que l’erreur relative entre les dimensions fractales théorique et produite s’atténue très vite lorsque le nombre de boites pleines générées augmente. Ainsi, pour des objets supérieurs à 1 000 boites pleines, l’erreur relative est toujours inférieure à 2% (Tableau 1).

Tableau 1 : Valeurs de l’erreur relative entre les dimensions fractales théorique et produite.

Dimension fractale théorique

1.100

1.200

1.300

1.400

1.500

1.600

1.700

1.800

1.900

Dimension fractale produite

1.100

1.221

1.325

1.385

1.492

1.602

1.706

1.819

1.891

Erreur relative (%)

0.035

1.816

1.977

-1.067

-0.528

0.180

0.385

1.060

-0.462

21Cette erreur inhérente à la procédure de calcul engendre à son tour une altération de la dimension fractale des objets produits. Pour vérifier ces écarts, nous avons produit pour chaque objet fractal de 10, 100, 1 000 et 10 000 boites pleines, dix simulations différentes pour chacune des dimensions fractales théoriques 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8 et 1.9 (soit 360 objets fractals différents). La dimension fractale des objets ainsi produits a été calculée par une méthode dite du comptage des boites développée sous R. Ces dimensions fractales calculées sont comparées aux dimensions fractales théoriques correspondantes (Figure 11). Chaque point représente donc une moyenne sur 10 simulations, les écart-types ne sont pas représentés car tous inférieurs à 1.3 10-2. Là encore on constate que lorsque le nombre de boites pleines finales des objets augmente, les dimensions fractales produites par la procédure de calcul et théoriques sont très proches (erreurs relatives toujours inférieures à 2% également).

Figure 10 : Erreurs relatives issues de l’approximation du nombre final d’itérations sur les dimensions fractales des objets.

Image 100000000000024F0000024EBFBE0E05.jpg

L’erreur relative est calculée par l’équation suivante : (Dp – Dth) × 100/Dth, avec Dth et Dp respectivement la dimension fractale théorique et la dimension fractale produite.

Figure 11 : Comparaison entre la dimension fractale théorique et la dimension fractale calculée par la méthode du comptage de boites.

Image 10000000000002A00000029F9480A506.jpg

Les points représentent une moyenne sur 10 simulations pour chaque dimension fractale théorique. Les écart-types ne sont pas indiqués car très faibles et tous inférieurs à 1.3 10-2.

Discussion – conclusion

22Dans cette étude nous présentons une méthode pour produire des objets dont la structure spatiale est contrôlée par une dimension fractale. La procédure utilisée a consisté à inverser la méthode dite du comptage de boites et a permis de produire de façon fiable des objets pour une dimension fractale théorique donnée. En effet, l’erreur relative entre la dimension fractale théorique et la dimension fractale produite n’excède jamais 2%. On montre que l’erreur est d’autant plus faible que le nombre de boites finales à générer est important. En d’autres termes, plus l’objet produit a une structure fine et moins l’erreur entre dimensions fractales théorique et produite est importante.

La procédure utilisée est basée sur l’arrangement aléatoire mais contrôlé de boites vides et pleines – qui contiennent tout ou partie de l’objet. Ainsi, on peut générer un très grand nombre d’objets différents pour une même dimension fractale théorique (Figure 12). Par exemple, pour le cas simple de 10 boites pleines finales et une dimension fractale de1.2, le nombre d’objets fractals qui peut être produit est de Image 100002010000006200000023291A7FCD.png =1.7 1014, soit plus de 100 mille milliards – le symbole mathématique ! représente la fonction factorielle, telle que Image 10000201000000A1000000135086DE11.png.

Figure 12 : Génération de 9 objets de 1 000 boites pleines finales pour les dimensions fractales théoriques : 1.1 (haut), 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8 et 1.9 (en bas).

Image 100000000000056A0000056A7814BFEA.jpg

23Sur les figures 6, 7, 8, 9 et 12, les objets fractals produits sont représentés par des boites noires qui indiquent la présence d’une partie de l’objet. Dans le cas où cet objet est un semi de points, il faut donc générer un point dans chaque boite noire. Ces points peuvent être placés au centre de la boite ou bien aléatoirement dans cette boite, ce qui permet de produire une infinité de semis de points pour une dimension fractale théorique donnée (Figure 13). L’aspect visuel des semis de points est très différent que les points soient placés au centre ou distribués aléatoirement dans la boite. On note que dans le cas où les points sont au centre de la boite (Figure 13 c), l’alignement produit un effet non naturel qui est atténué lorsque les points sont distribués aléatoirement dans les boites (Figures 13 d, e, f).

24Ces semis de points fractals sont des objets mathématiques mais ils peuvent être associés à un caractère géographique. En effet, ces points sont caractérisés par leurs coordonnées cartésiennes (x,y) qui permettent de localiser des objets géographiques qui peuvent être des communes, des végétaux, des sommets de montagne, des sources, des lacs, des épicentres de séisme, des écoles dans une ville ou encore des sites archéologiques. Notre méthode est générique et les semis de points peuvent donc être associés à des caractères variés. Au-delà des imperfections inhérentes à la méthode mathématique, il existe d’autres limitations à cette procédure lorsqu’elle s’intéresse aux objets géographiques, donc au monde réel. Ainsi, prenons l’exemple de semis de points qui caractériseraient des végétaux, afin de faire écho à la problématique de re-végatalisation des mines et carrières à ciel ouvert évoquée en introduction. On comprend bien que de générer des points dans l’espace n’est pas une solution complètement satisfaisante pour produire un plan de replantation concrètement réalisable. Dans un cas réel, il existe évidemment un certain nombre de contraintes de terrain qui viennent compliquer la situation :

  • Des contours non rectilignes de la surface à planter. Pour pallier ce problème on peut envisager de prendre en compte ces irrégularités par un forçage du choix des boîtes vides.

  • Des obstacles de la surface à planter. Il pourra s’agir de massifs rocheux, d’étendue d'eau ou encore de bâtiments, donc des zones sur lesquelles on ne pourra pas placer de végétaux. Là encore le positionnement forcé de certaines boîtes vides pourrait être une solution. Dans ces deux cas il faudra bien sûr vérifier comment la dimension fractale est influencée par ce forçage.

  • La nature des sols et la topographie. Les caractéristiques géométriques et physico-chimiques des sols vont dicter les différentes essences d'arbres à planter.

Figure 13 : Un semi de 1 000 points est généré pour une dimension fractale de 1.9.

Image 10000000000004BD00000794315C6B8B.jpg

Les boites pleines issues de la procédure de calcul sont colorées en noir (a). Elles correspondent à des boites adjacentes qui contiennent un point (b). Les points peuvent être placés au centre des boites (c) ou bien aléatoirement dans ces boites (d, e, f).

25L’intégration de ces contraintes de terrain demande un développement supplémentaire de notre méthode qui est théorique (génération de semis de points) et générique (nombreuses applications sur des objets variés de la géographie). Cette méthode ouvre également des questionnements sur l’utilisation d’outils de visualisation 3D de ces objets. En effet, l’intégration à la fois de paramètres physiques (taille des végétaux), biologiques (essence des végétaux), topographiques (terrains plat ou vallonné) dans un contexte de vision tridimensionnelle change complètement la perception du semi de points. La visualisation du semi de points de la Figure 13 en 3D montre les différences de perception d’un unique semi de points, caractérisé uniquement par ses coordonnées spatiales, lorsque qu’on fait varier des paramètres physico-biologiques et topographiques (Figures 14, 15, 16 et 17). La visualisation des semis de points en 3D est faite ici par le biais du logiciel NetLogo3D (Wilensky, 1999). Bien que cet environnement de programmation soit principalement destiné à la simulation mutli-agents, NetLogo3D permet aussi de positionner des agents (ici des arbres de tailles et d’essences différentes) en 3D.

Figure 14 : Représentation tridimensionnelle du semi de points généré de la Figure 13.

Image 100000000000056A0000056A79D3CE16.jpg

Ici les végétaux sont placés sur un terrain plat et au centre des boites. Ils sont représentés avec une seule taille (a), une taille dont la valeur est tirée aléatoirement (b), une seule taille mais deux essences différentes (c), deux essences différentes et des tailles tirées aléatoirement (d).

Figure 15 : Représentation tridimensionnelle du semi de points généré de la Figure 13.

Image 100000000000056A0000056ADE48C5E5.jpg

Ici les végétaux sont placés sur un terrain plat et positionnés aléatoirement dans les boites. Ils sont représentés avec une seule taille (a), une taille dont la valeur est tirée aléatoirement (b), une seule taille mais deux essences différentes (c), deux essences différentes et des tailles tirées aléatoirement (d).

Figure 16 : Représentation tridimensionnelle du semi de points généré de la Figure 13.

Image 100000000000056A0000056ADFDA4564.jpg

Ici les végétaux sont placés sur un terrain vallonné et au centre des boites. Ils sont représentés avec une seule taille (a), une taille dont la valeur est tirée aléatoirement (b), une seule taille mais deux essences différentes (c), deux essences différentes et des tailles tirées aléatoirement (d).

Figure 17 : Représentation tridimensionnelle du semi de points généré de la Figure 13.

Image 100000000000056A0000056A76033554.jpg

Ici les végétaux sont placés sur un terrain vallonné et positionnés aléatoirement dans les boites. Ils sont représentés avec une seule taille (a), une taille dont la valeur est tirée aléatoirement (b), une seule taille mais deux essences différentes (c), deux essences différentes et des tailles tirées aléatoirement (d).

26Si la dimension fractale est un indicateur très utilisée en géographie pour caractériser la structure d’objets surfaciques (structures urbaines par exemple), elle l’est en revanche beaucoup moins pour les objets ponctuels comme les semis de points. Or, les semis de points sont des éléments importants dans les structures géographiques. Ces points géométriques sont des objets et/ou des lieux géographiques qui peuvent faire l’objet d’une analyse spatiale afin de répondre à des questionnements concernant leur localisation, leur distribution ainsi que leurs interactions (Pumain & Saint-Julien, 2010). Les méthodes d’analyse spatiale des semis de points sont nombreuses, et comprennent des analyses simples comme les statistiques spatiales descriptives ou encore la méthode des quadrats, jusqu’à des analyses plus compliquées comme l’auto-corrélation spatiales ou encore l’analyse des plus proches voisins à plusieurs ordres (Zaninetti, 2005 ; Lloyd, 2010 ; Caloz & Collet, 2011). Mais quels sont les liens entre la dimension fractale d’un semi de points et l’indice de Morishita (méthode des quadrats multi-échelles) ? Un semi de points de structure fractale aura-t-il une fonction LRipley caractéristique (plus proches voisins à plusieurs ordres) ? Si certaines études répondent partiellement à ces questions (e.g. Golay et al., 2014), la méthode présentée peut peut-être permettre d’explorer les liens entre les méthodes d’analyse spatiale classiquement utilisées en géographie et la fractalité des semis de points.

Haut de page

Bibliographie

Barnsley, M. F., 1993. Fractals Everywhere. 2 Sub edition ed. New York: Morgan Kaufmann Pub.

Barton, C. C., 2013. Fractals in the Earth Sciences. New York: Springer-Verlag.

Boutot, A., 1993. L'invention des formes. O. Jacob ed. Paris: s.n.

Brent, N. & Russ, J., 2012. Measuring Shape. s.l.:CRC Press Inc.

Burley, J.B, 2007. "Surface mine reclamation. Restoration and Mediation Chapter. Part 3: Process, Implementation, and Applications". Hopper, L.J. (ed.) in: Landscape Architectural Graphic Standards. J. Wiley & Sons, pp. 806-810.

Caloz, R. & Collet, C., 2011. Analyse spatiale de l'information géographique. Lausanne: Presses Polytechniques et Universitaires Romandes.

Chandrasekhar, E., Vijay, P. & Vikram, M., 2013. Wavelets and Fractals in Earth System Sciences. London: CRC Press Inc.

Dauphiné, A., 2000. Chaos, fractales et dynamiques. s.l.:La Documentation fraçaise.

Dauphiné, A., 2011. Géographie fractale. Paris: Hermes Science Publication.

Fernandes, M., Aguiar, F. & Ferreira, M., 2011, " Assessing riparian vegetation structure and the influence of land use using landscape metrics and geostatistical tools", Landscape and Urban Planning, 99(2), pp. 166-177.

Frankhauser, P., 1994. La fractalité des structures urbaines. s.l.:Economica.

Golay J., Kanevski M., Vega Orozco C., Leuenberger M. 2014, "The multipoint Morisita index for the analysis of spatial patterns", Physica A, 406, pp. 191–202.

Kozlov, G., Doblin, I. & Zaikov, G., 2013. The Fractal Physical Chemistry of Polymer Solutions and Melts. s.l.:Apple Academic Press Inc..

Lehmann, W., Burley, J. B., Fleurant, C. & Loures, L., 2013. "Replicating species based fractal patterns for reclaiming northern Michigan waste rock piles", Journal of the American Society of Mining and Reclamation, 2(1), pp. 114-135.

Lloyd, C., 2010. Spatial data analysis: an introduction for GIS users. New York: Oxford University Press.

Mandelbrot, B., 1982. The Fractal Geometry of Nature. W.H.Freeman & Co Ltd ed. New York: s.n.

Mandelbrot, B., 2009. Fractales, hasard et finance. s.l.:Flammarion.

Nakagawa, M., 1999. Chaos and Fractals in Engineering. London: World Scientific Publishing Co Pte Ltd.

Pinnaduwa, H., Fielder, R. & Panda, B., 1997. "Box fractal dimension as a measure of statistical", Engineering Geology, Volume 48, pp. 217-229.

Pumain, D. & Saint-Julien, T., 2010. Analyse spatiale : les localisations. 2nde ed. Paris: Armand Colin.

R Development Core Team, 2008. R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria. ISBN 3-900051-07-0, URL http://www.r-project.org/

Rodriguez-Iturbe, I. & Rinaldo, A., 2001. Fractal River Basins: Chance and Self-Organization. London: Cambridge University Press.

Sapoval, B., 2001. Universalités et fractales. s.l.:Flammarion.

Tannier C., Vuidel G., Houot H., Frankhauser P., 2012, "Spatial accessibility to amenities in fractal and non fractal urban patterns", Environment and Planning B: Planning and Design, 39(5), pp. 801-819.

Tannier C., Thomas I., 2013, "Defining and characterizing urban boundaries: A fractal analysis of theoretical cities and Belgian cities", Computers, Environment and Urban Systems, 41, pp. 234-248.

Turcotte, D. L., 1997. Fractals and Chaos in Geology and Geophysics. London: Cambridge University Press.

Volkert, K., 2008. "La mathématique et le pathologique", Philosophia Scientiae, 12(2), pp. 65-74.

Wilensky, U., 1999. NetLogo. URL http://northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University. Evanston, IL.

Zaninetti, J.-M., 2005. Statistiques spatiale : méthode et applications géomatiques. Paris: Hermès, Lavoisier.

Haut de page

Annexe

Script R

#----------------------------------------
#  Méthode inverse du comptage des boites
#       © Cyril Fleurant - 2014
#----------------------------------------
# Paramètres graphiques
par(mfrow=c(1,1))
par(mai=c(0.1, 0.1, 0.1, 0.1))

#---------------
#      Sortie d’écran          
#---------------
cat("   Méthode inverse du comptage de boites    ","\n")
cat("          © Cyril Fleurant - 2014           ","\n")

# Nombre de points à la fin de la simulation
Nn = 10000
# Boucle sur la dimension fractale
# 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9
for(dim in 1:9) {
  D = 1+dim/10
  # Boucle sur le nombre d’expérience
  # 1 -> 10
  for(exp in 1:10) {
    # Matrice des points
    mf <- matrix(data=1,nrow=1,ncol=1,byrow=T)
    # Valeur de la coupure inférieure.
    n = round(log(Nn)/(D*log(2)))
  
    #--------------------
    # Procédure itérative
    #--------------------
    for(it in 0:(n-1)) {
      cat("Itération = ", it+1, "\n")
           # A chaque itération deux nouvelles matrices sont créées
           m_av <- matrix(mf,nrow=2^it,ncol=2^it)
           ni = 2*nrow(m_av)
           nj = 2*ncol(m_av)
           m <- matrix(nrow=ni,ncol=nj,byrow=T)
           for(i in 1:ni) {
             for(j in 1:nj) {          
               m[i,j] <- m_av[ceiling(i/2),ceiling(j/2)]
             }
           }
           # Nombre total des boites
           Np = sum(m)
           # Nombre des boites pleines
           Nf = (2^((it+1)*D))
           # Nombre des boites vides
           Nv = round(Np-Nf)
           # Procédure de choix aléatoire des boites vides
           cpt = 0
           while(cpt < Nv) {
             rand_i = ceiling(runif(1,0,ni))
             rand_j = ceiling(runif(1,0,nj))
             if(m[rand_i,rand_j] == 1) {
               m[rand_i,rand_j] <- 0
               cpt = cpt + 1
              }
            }
            # Copie de la matrice résultat
            mf <- m
            cat("Boites total = ", nrow(mf)*ncol(mf), "\n")
            cat("Boites pleines = ", sum(mf), "\n")
            cat("Boites vides = ", nrow(mf)*ncol(mf)-sum(mf), "\n")
    }

    #-------------------
    # Fichiers de sortie
    #-------------------
    # Formatage du nom des fichiers 
    if(D == 1.1) D_index = toString(11)
    if(D == 1.2) D_index = toString(12)
    if(D == 1.3) D_index = toString(13)
    if(D == 1.4) D_index = toString(14)
    if(D == 1.5) D_index = toString(15)
    if(D == 1.6) D_index = toString(16)
    if(D == 1.7) D_index = toString(17)
    if(D == 1.8) D_index = toString(18)
    if(D == 1.9) D_index = toString(19)
    file <- paste("fractal_",D_index,"_",ni,"_",exp,".txt",sep="")
    write.table(mf,file,row.names=F,col.names=F,append=T)

    #-----------
    # Graphiques
    #-----------
    # Définition de l’échelle de la zone (m)
    L = 2^n
    # Lecture du fichier et de ses données
    infile <- paste("fractal_",D_index,"_",ni,"_",exp,".txt",sep="")
    data_file <- read.table(infile,header=F,row.names=NULL)
    data <- as.matrix(data_file,ncol=ni,byrow=T)
    # Transformation des cellules en coordonnées (x,y)
    # data_x, coordonnées X des centres des cellules
    # data_y, coordonnées Y des centres des cellules
    data_x <- matrix(data=.0,nrow=ni,ncol=ni,byrow=T)
    data_y <- matrix(data=.0,nrow=ni,ncol=ni,byrow=T)
    # Taille des cellules
    dx = L / ni
    dy = L / nj
    plot(2*L,2*L,xlim=c(0,L),ylim=c(0,L),axes=F,xlab="",ylab="")
    box(lwd=1,col=1)
    for(n in 1:ni) {
           for(m in 1:nj) {
                  data_x[n,m] <- 0.5 * dx + (m-1) * dx
                  data_y[n,m] <- 0.5 * dy + (ni-n) * dy          
        # Pour tracer un point au centre de la boite
                  if(data[n,m] != 0) points(data_x[n,m],data_y[n,m],pch=16,cex=.25)
                }
    }
    # Copie du fichier image en format TIF
    name <- paste(file="fractal_",D_index,"_",exp,".tif",sep="")
    savePlot(name,type="tif")
  }

Haut de page

Pour citer cet article

Référence électronique

Cyril Fleurant, « Génération de semis de points fractals : une méthode du comptage de boites inversée », Cybergeo : European Journal of Geography [En ligne], Systèmes, Modélisation, Géostatistiques, document 736, mis en ligne le 11 septembre 2015, consulté le 23 mars 2017. URL : http://cybergeo.revues.org/27164 ; DOI : 10.4000/cybergeo.27164

Haut de page

Auteur

Cyril Fleurant

UMR 6554 CNRS LETG – Angers
Université d'Angers
cyril.fleurant@univ-angers.fr

Articles du même auteur

Haut de page

Droits d’auteur

© CNRS-UMR Géographie-cités 8504

Haut de page