Polices Voronoï Voronoi Fonts

Pour la carte de vœux publiée dans le billet précédent, j'ai emprunté l'idée de police Voronoï à Erik Demaine, mais en adoptant la forme de la carte de distance déjà montrée ici.

L'algorithme consiste, par rapport à un certain nombre de sites, ou centres, à donner à chaque pixel un niveau de gris proportionnel à sa distance au site le plus proche. A noter que je considère aussi les bords, afin d'avoir une meilleure lisibilité: si la distance au bord est inférieure à celle à n'importe quel site, c'est cette distance qui affecte le niveau de gris. Ci-dessous la version avec les sites:

The new year animation published in the last post borrows the idea of Voronoi fonts from Erik Demaine, but with the form of distance map already exposed here.

The algorithm consists in, given a certain number of sites, coloring each pixel with a level of grey proportionnal to its distance from the nearest site. Note that borders are taken into consideration for a better readibility: if the distance from a border is smaller than the distance from any site, it is this distance that is taken into annount. Below the version with the sites: 

Les cellules de Voronoï sont perceptibles à travers les frontières blanches. Une version plus proche de la proposition d'Erik Demaine consiste à affecter à chaque pixel une couleur correspondant au site le plus proche (ou au bord, le cas échéant). En voici un résultat ci-dessous:

The Voronoi cells appear through the white borders. A version more similar toErik Demaine's proposition consists in colouring each pixel with a colour specific to the closest site (or the border). Below is one such result:

cartes de distances et champs spatiaux/distance maps and spatial fields

L’une des utilisations des cartes de distance que j’avais en tête était de les confronter à certaines analyses architecturales, telles que les « champs spatiaux » de Ching (Ching, Francis D. K., Architecture: Form, Space & Order, 2^nd Ed., John Wiley & Sons, Inc., 1996), ou les « champs de forces » de von Meiss (von Meiss, Pierre, De la forme au lieu: une introduction à l’étude de l’architecture, Presses polytechniques romandes, Lausanne, Suisse, 1986):

One use of distance maps I had in mind was to confront them to some architectural analyses, such as Ching’s «fields of space» or von Meiss’ «force fields»:

Ching, p. 151

Ching, p. 168

von Meiss, p. 125

Je fis donc quelques expériences en regroupant les points de référence en lignes continues reproduisant en plan certaines configurations étudiées par les auteurs cités:

I experimented by aggregating reference points into continuous lines forming some of the configurations that were studied by those authors:



   



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...