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