cartes de distances et axes médians / distance maps and medial axes

Je dois en fait ma première intuition des cartes de distances à la communication de Gert J. van Tonder au colloque Ffractarq’04 (The 1st International Conference on Foundations for Fractal Architecture in the 21st Century, Madrid). Son papier, intitulé « Fractal potential of ‘emptiness’ in Japanese dry rock gardens » (disponible ici), parlait d’« axes médians », et son but était de montrer le caractère fractal (ou plutôt arborescent) de la structure du vide dans les jardins zen (composés de gravier et de pierres). J’eus donc l’idée de réaliser ce que j’ai appelé plus tard une carte des distances par rapport à des « centres » correspondant aux pierres d’un jardin zen imaginaire :

I actually owe my first intuition of distance maps to Gert J. van Tonder’s paper at Ffractarq’04 (The 1st International Conference on Foundations for Fractal Architecture in the 21st Century, Madrid). His paper, titled «Fractal potential of ‘emptiness’ in Japanese dry rock gardens» (available here), was about «medial axes», and his aim was to show the fractal quality (or rather the tree-like one) of the strucure of the empty space in Japanese rock gardens. I therefore had the idea to compute what I later called a distance map with the «centres» being the rocks of an imaginary rock garden:

Je reviendrai sur cet exemple et ses implications. Dans la foulée, j’ai expérimenté les cartes de distances sur un certain nombre de configurations de centres :

I shall return later on this example and its implications. I experimented at the time other distance maps on some of configurations of centres:

2 points :

3 points :

12 points sur un cercle / 12 points on a circle :

plus de points sur un cercle / more points on a circle :

des points en spirale / points on a spiral :

plus de points sur une spirale / more points on a spiral :

une cardioïde /a cardioid:

où l'on voit apparaître fantomatiquement le cercle fixe autour duquel tourne le cercle qui permet de définir cette courbe comme trajectoire (explications ici).

where we can see the ghost of the circle around which rolls the circle that permits to define this curve (explanations here)

une autre cardioïde avec moins de points /another cardioid with less points:

A noter que dans ces images, j'ai grossi la taille des centres (points rouges) pour une meilleure visibilité. En réalité, ils font seulement un pixel.

Let's remark that in those pictures I enlarged the centres (red dots) in order to better see them. Their size is actually one pixel.

cartes de distances / distance maps

Frei Otto commence son étude par l’occupation, ou plutôt la répartition de points sur une ligne, sur une surface, ou dans l’espace, en observant des oiseaux sur un fil électrique, des gouttes de rosée sur des toiles d’araignées, ou encore des arbres dans une forêt ou des gens dispersés sur une plage, etc. Tout de suite, il évoque les « territoires » que ces points dispersés génèrent. Et il dessine ce croquis:

Frei Otto begins his study with the occupation, or rather the distribution, of points on a line, on a surface, or in space, by observing birds on a wire, dew droplets on spiderwebs, trees in a wood or people on a beach, and so on. Very soon, he evokes the «territories» generated by these distributed points. And he draws this sketch:

La manière de démarquer ces territoires est de tracer les médiatrices entre points les plus proches, et, même si Otto ne le mentionne pas, il s’agit de générer ce que l’on appelle les diagrammes de Voronoï (ou cellules de Voronoï).

The demarcation of these territories consists in drawing perpendicular bisectors of nearest points, and, even if Otto does not mention it, it generates what are called Voronoï diagrams (or Voronoï cells).

Le calcul des diagrammes de Voronoï peut être assez compliqué, mais il y a un moyen très simple de les obtenir, et que j’appelle « carte des distances ». En partant d’un bitmap et d’une distribution de points appelés « centres » (en rouge), on affecte à chaque pixel un niveau de gris proportionnel à sa distance au centre le plus proche. Et les cellules de Voronoï apparaissent très clairement. En voici un exemple, avec 20 centres répartis aléatoirement:

Computing Voronoï diagrams may be tricky, but there is a very easy way to get them, that I call «distance map». Starting from a bitmap and a distribution of points called centres (in red), one affects to each pixel a level of grey in proportion to its distance from the nearest centre. And Voronoï cells appear very clearly. Here is an example, with 20 centres randomly distributed:

Asuivre...

To be continued...