créations numériques - modèles génératifs - architecture et mathématiques

digital creations - generative models - architecture and mathematics

marie-pascale corcuff







2022-01-17

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:




2022-01-11

Bonne année! Happy new year!

 


Je reprends ce blog abandonné depuis si longtemps...
Carte de vœux vaguement inspirée des polices voronoï d'Erik Demaine.

Back to this blog left stranded much too long...

New year card roughly inspired by voronoi fonts by Erik Demaine.

2014-08-19

ordre et désordre / order and disorder


Ce sujet est fondé sur l'article de Jennifer Galanis et Martin Ehler publié en 2011 à generative art
This issue is based upon the 2011 paper by Jennifer Galanis and Martin Ehler in generative art

J'étais particulièrement charmée par la beauté de la figure 1b, due à la corrélation entre l'orientation des segments et leur couleur.
I was particularly seduced by the beauty of figure 1b, due to the correlation between orientation and colour of rods.

Le principe consiste à partir d'une configuration aléatoire (en position et orientation) de segments et à les réarranger pour éviter les intersections. Le réarrangement dans cette version consiste à détecter les segments qui intersectent tel ou tel segment et à les faire pivoter un peu (0.05 radians) de façon à tendre à éviter l'intersection.
The principle consists in starting from a random (as well in position as in orientation) configuration of rods, and in rearranging them in order to avoid intersections. The rearrangement here consists in detecting those rods that intersect one particular rod, and in pivoting them a little (0.05 rad) in order to tend to avoid the intersection.

J'ai créé un objet appelé segment dans un sketch processing ; la classe segment a deux arguments : la position du milieu, et l'angle de l'orientation (comprise entre 0 et pi). Les segments sont membres d'un tableau dynamique (arrayList).
I created an object called segment in a processing sketch ; the segment class has got two arguments : the middle point position and the orientation angle (between 0 an pi). The segments are part of a dynamic array (arrayList).

Voir ci-dessous quelques résultats.
See below a few results.

  





A bientôt pour une discussion plus approfondie.
Some more discussion to come.
 
Et pour voir le programme en action if you want to see the process : http://www.openprocessing.org/sketch/157847

 

 


2013-05-12

TSP #1


« TSP » vaut pour « Travelling Salesman Problem » (ou « Travelling Salesperson Problem » si on veut être « genderly » correct) qui peut se traduire en « problème du voyageur de commerce », et désigne le problème suivant : étant donné un certain nombre de points, quel est le plus court chemin qui relie tous ces points ?

« TSP » stands for « Travelling Salesman Problem » (or « Travelling Salesperson Problem » to be « genderly » correct) and refers to the following problem: given a set of points, what is the shortest route that links all those points?

Une condition supplémentaire est que le chemin revient à son point de départ : il s’agit d’un circuit, et donc d’un polygone. Une conséquence de la minimisation de la longueur du circuit est que ce polygone est non croisé : on peut en effet montrer que si deux segments se croisent, alors le polygone obtenu en « décroisant » est plus court (la somme de deux côtés opposés d’un quadrilatère est toujours inférieure à celle des diagonales).

A further condition is that the route must return to the starting point: it is a tour, or circuit, and as such a polygon. A consequence of the minimization of the length of the route is that the polygon is not self-intersecting (simple) : it can be demonstrated that if two segments intersects, the polygon obtained by suppressing this intersection is shorter (the sum of two opposed edges of a quadrilateral is always less than the sum of the diagonals).

Même si l’on n’insiste pas sur la condition de minimisation, résoudre ce problème est intéressant, ne serait-ce que pour obtenir un polygone non croisé à partir d’un ensemble de sommets.
Even without stressing on the condition of minimization, solving this problem is interesting in order to obtain a simple polygon from a given set of vertices.

J’ai été sensibilisée à ce problème et au côté esthétique de ses résultats par la conférence de Philip Galanter à GA 2004 intitulée « What is Emergence ?» (voir article ici). J’avais étudié ce problème à l’époque, mais je m’y suis remise récemment à l'occasion de discussions avec un ancien étudiant sur la génération de polygones dont l’aire doit respecter certaines contraintes, la première étape consistant de toutes façons à générer un polygone non croisé.
I was made sensitive to this problem and its aesthetic side by Philip Galanter’s lecture at GA 2004 : «What is Emergence ?» (see paper here). I had looked at the problem at that time, but I was reminded of it recently when discussing with a former student the generation of polygons the area of which must obey constraints, the first step consisting of generating a simple polygon anyway.

Le problème TSP, qui s’énonce très simplement, est plus compliqué qu’il n’y paraît, surtout si l’on veut optimiser le temps de résolution. L’algorithme que j’avais mis en œuvre se décrit ainsi : on commence par faire un circuit convexe qui circonscrit l’ensemble des points, puis on ajoute les points restants un à un en choisissant à chaque fois le point dont l’insertion entre deux points du circuit génère la plus petite augmentation de la longueur totale.
The TSP problem, though simple in its formulation, is more complicated than it seems, more over if one wants to optimize the solving time. The algorithm I had used consists in this : one begins with a convex circuit that circumscribes the set of points, then one adds the other points one by one by choosing the points that yields the least augmentation of the total length when inserted between two points of the circuit.

On peut même le mettre en œuvre manuellement : on plante des clous dans une planche ou une plaque de carton, on les entoure avec un élastique, puis on fait passer l’élastique par le clou qui nous semble l’allonger le moins, et on recommence jusqu’au dernier clou.
One can even do this «by hand» : hammer a few nails in a wood or cardboard plate, put a rubber band around them, then shift the rubber band around the nail that seems to elongate it the least, and do it again till the last nail.


La version calculée de ce processus inverse les difficultés : s’il est évident de mettre l’élastique autour des clous, calculer le circuit convexe circonscrit est plus laborieux. Je commence par trouver le point le plus à droite (par exemple) puis par une comparaison des angles que font les autres points avec celui-ci, je trouve le deuxième, etc.
The computed version of this process reverses the difficulties : while it is straightforward to put the rubber band around the nails, it is more laborious to calculate the convex circuit that circumscribes the set of points. I start with the point which is the farthest on the right (for instance) then I compare angles for the other points in order to find the second point, and so on.

Par contre, si choisir le clou qui génère la plus petite élongation de l’élastique est un peu hasardeuse, calculer et comparer la différence entre la somme des distances entre tel point et deux sommets successifs du circuit d’une part et la distance entre ces deux sommets d’autre part, est simple à mettre en œuvre.
On the contrary, while the choice of the nail that generates the least elongation of the rubber band is somewhat uncertain, the computation of the difference between the sum of the distances between one point and two successive vertices of the circuit, on one hand, and the distance between those two vertices, on the other, is very easy.





Je ne suis pas sûre que cet algorithme donne vraiment le plus court circuit, ni qu’il soit optimal en temps de calcul, mais son résultat me satisfait tout de même, en ce qu’il est bien un polygone non croisé joignant un ensemble donné de points.
I am not sure that this algorithm yields the shortest circuit, nor that it optimizes the computing time, but its result is satisfying enough anyway, as it is a simple polygon linking a given set of points.

2012-01-28

dragon 2012














[cliquer sur l'image pour voir l'animation Click on the picture in order to see the animation]

Une courbe du dragon pour l'année du dragon... Bonne année!
A dragon curve for the year of the dragon... Happy new year!

2011-10-14

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, 2nd 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 larchitecture, 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:















   






2011-10-05

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.