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

digital creations - generative models - architecture and mathematics

marie-pascale corcuff







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.

2011-09-13

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

"Occupying and Connecting", Frei Otto

Frei Otto, Occupying and Connecting. Thoughts on Territories and Spheres of Influence with Particular Reference to Human Settlement, Ed. Axel Menges, 2009

Ce petit livre (dont le titre peut se traduire: Occuper et connecter. Penser les territoires et les sphères d’influence et particulièrement les installations humaines) est l’un des ouvrages les plus stimulants que j’aie eu entre les mains depuis longtemps. L’architecte Frei Otto est bien connu pour son travail sur les structures légères et les surfaces minimales, et pour ses constructions empruntant aux arbres et autres formes naturelles, ce que l’on peut appeler la bionique (voir Architecture et Bionique. Constructions naturelles, Delta et Spes, 1985). Mais ici il explore les mécanismes fondamentaux régissant la répartition de points (sur une ligne, une surface ou dans l’espace), la formation de territoires à partir des ces points et leur confrontation, et enfin les types de liaisons qui peuvent se créer entre ces points. Le but de Frei Otto est de contribuer à un urbanisme non planifié, ou du moins qui suivrait des règles plus conformes aux lois de l’espace et plus soucieuses des comportements humains. Mais la question de l’occupation de l’espace et des connexions entre les lieux est plus fondamentale et contribue en fait à notre pensée des formes et de l’espace, et peut s’appliquer à bien d’autres domaines que l’urbanisme.
This book is one of the most stimulating books I happened to read recently. Architect Frei Otto is well known for his work on light weight structures and minimal surfaces, and for his constructions inspired by trees and other natural forms, what can be called bionatics (see Architecture et Bionique. Constructions naturelles, Delta et Spes, 1985). But here he explores the fundamental mechanisms that govern the distribution of points (on a line, a surface, or in space), the formation of territories from these points and their confrontation, and finally the kinds of connections that can be made between those points. Frei Otto’s aim is to contribute to unplanned urbanism, or at least to an urbanism which would follow rules more conform to laws of space and more concerned by human behaviour. But the issue of occupying space and connecting places is much more fundamental and contributes grandly to our thoughts about forms and space, and can apply to many other fields than urbanism.
Frei Otto illustre son livre avec des croquis et des photos de résultats d’expériences matérielles. Les croquis, assez grossiers, transmettent tout de même clairement les idées exprimées dans le texte. Les expériences sont menées à l’aide de dispositifs très simples impliquant par exemple des aiguilles aimantées et des billes de polystyrène flottant sur l’eau, ou du sable s’écoulant par des trous, etc. L’auteur n’utilise pas l’ordinateur et ignore les algorithmes susceptibles de simuler les processus qu’il décrit. Mais il est évident que les mécanismes spatiaux ici inventoriés sont pour la plupart transposables dans le monde numérique, et d’ailleurs j’y ai retrouvé un bon nombre de modèles que j’ai moi-même programmés. Cette lecture « numérique » de ce livre fera l’objet des prochains messages de ce blog.
Frei Otto illustrates his book with sketches and photos of results from material experiments. The rough sketches nevertheless transmit clearly the ideas expressed in the text. The experiments are made with devices implying for instance magnetized needles and balls of polystyrene floating on water, or sand flowing through holes, and so on. The author does not use computers and ignores the algorithms that could simulate the processes he describes. But it is obvious that the spatial mechanisms involved are for the most part translatable into the digital world, and I actually rediscovered a lot of models I programmed earlier. This «digital» reading of the book will be the topics of next posts here.
Frei Otto, et s’est sans doute le seul défaut que l’on peut trouver à ce livre, est un peu « autiste », et ne cite pratiquement pas d’autres sources (à l’exception notable de d’Arcy Thompson, mais qui ne doit quelque chose à cet immense auteur?)que lui-même ou l’institut qu’il dirige (Institut für leichte Flächentragwerke à Stuttgart). Les messages qui suivront combleront dans la mesure du possible ce manque.
Frei Otto, and this is the only fault of his book, is a little «autistic», and refers practically only (with the notable exception of d’Arcy Thompson, but who does not owe something to this great author?) to his own work or that of his institute (Institut für leichte Flächentragwerke in Stuttgart). The following posts will try to correct that as much as possible.
A suivre, donc... Ce livre et les sujets qu'il traite seront référencés comme « O+C. »
To be followed, then... This book and its topics will be referred as «O+C».