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.

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!

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

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

"Subnature. Architecture's other Environments", David Gissen

Ce livre (David Gissen, Subnature. Architecture's other Environments, Princeton Architectural Press, 2009) entend traiter d'aspects qui sont négligés dans la théorie et les débats sur les relations entre architecture et nature. Il ne s'agit pas ici d'architecture "verte", mais plutôt "marron" ou "grise". Ce regard décalé et légèrement ironique sur la nature est très rafraîchissant.
This book (David Gissen, Subnature. Architecture's other Environments, Princeton Architectural Press, 2009) intends to consider aspects of the relationships between architecture and nature that are "wholly undertheorized, underdiscussed, and undervisualized" (p. 21). Indeed, it is not a "green", but rather a "brown" or, a "grey", architecture that is addressed here. This slanted, slightly ironic, way of looking at nature is very refreshing.
On peut lire des extraits du livre là, et d'autres recensions là, là et là.
One can read extracts from the book here, and other reviews here, here and here.

On peut s'interroger sur le choix des douze sujets qui composent le livre. L'auteur explique que, ayant rassemblé une nombreuse documentation sur les rapports entre nature et architecture pour sa thèse (sur la nature dans les bâtiments des années 1970 à New York), il voulait exploiter les documents laissés de côté. Le plan du livre est donc le résultat d'une classification de ces documents, complétés par de nouvelles données. Ces sujets a priori bizarres et éclectiques constituent douze chapitres organisés en trois parties qui tentent de rationaliser cette liste :

Atmosphères : Dankness* Fumée Gaz Gaz d'échappement

Matière : Poussière Flaques Boue Décombres

Vie : Mauvaises herbes Insectes Pigeons Foules

* Dankness est difficile à traduire ; il s'agit de l'atmosphère humide et froide que l'on trouve dans les grottes et cavernes, mais aussi les caves, égoûts, etc.
One may question the choice of the twelve items that compose the book. The author explains that having gathered a lot of documentation on the relationship between nature and architecture for his thesis (on nature in modern buildings in New York City in the 1970s), he wanted to exploit some of his "secondary material" . The table of contents is then the result of a classification of those documents, supplemented by new material. These apparently weird and eclectic subjects constitute twelve chapters that are organized in three parts as a way to attempt to give some logic to this list:
Atmospheres: Dankness Smoke Gas Exhaust
Matter: Dust Puddles Mud Debris
Life: Weeds Insects Pigeons Crowd
A considérer cette liste, il apparaît que le sous-titre du livre (« autres » environnements) est plus pertinent pour qualifier son contenu. Les gaz d’échappement et les décombres (l’auteur emploie le mot français « débris ») ne sont certainement pas des produits naturels. Ce que tous ces éléments ont en commun, c’est de faire partie de notre environnement, mais d’être non souhaités, du moins là où ils sont : les mauvaises herbes ne sont pas définissables autrement que comme des herbes qui poussent là où elles ne devraient pas, la boue n’a rien de mauvais en elle-même mais on n’en veut pas en ville, etc. Tous ces éléments de l’environnement sont rejetés comme sales, dégoûtants, polluants. Citant Mary Douglas (Purity and Danger: An Analysis of Concepts of Pollution and Taboo, Routledge, 1966), David Gissen remarque que les choses, les personnes, et les pratiques ne sont pas "sales" en soi, mais sont considérées comme telles quand elles ne sont pas à leur place.
Considering this list, one sees that the subtitle of the book (« Other environments ») is more pertinent to qualify its contents. Exhaust and debris are certainly not natural. What all these items share is to be unwanted, at least where they are: weeds are only defined as plants that grow where they should not, mud is not mad as such, but we don’t want it in town, and so on. All these components of our environment are discarded as dirty, filthy, polluting. Quoting Mary Douglas (Purity and Danger: An Analysis of Concepts of Pollution and Taboo, Routledge, 1966), Gissen asserts that "things, people, and practises become dirty when they are "matter out of place""(p. 150).

L’auteur interroge l’attitude adoptée par les architectes par rapport à ces « tabous » à travers les âges. Chaque chapitre commence par une exploration historique et théorique du sujet, où l’on découvre des références et des réflexions très instructives. L’auteur nous mène jusqu’à la période contemporaine, pour laquelle il privilégie quelques projets extrêmes, souvent provocateurs, dans lesquels la vision généralement manichéenne et hygiéniste du passé se transforme en une acceptation et une intégration dans le projet, parfois jusqu’à l’absurde. Ainsi par exemple le projet B_mu Tower de R&Sie(n), qui comporte une enveloppe électrostatique sur laquelle les gaz d’échappement se fixent, et croissent pour former une sorte de fourrure...

The author questions the attitude that has been adopted by architects towards these « taboos » troughout ages. Each chapter begins with an historical and theoretical exploration of each subject, which permits to discover very enlightening references and reflections. The author leads us towards the contemporary period, for which he focuses on some extreme, often provocative, projects, in which the mainly manicheist and hygienist previous attitude changes into an acceptation and an integration in the project, sometimes till absurdness. See for instance B_mu Tower by R&Sie(n) which comports an electrostatic skin on which exhaust is drawn, and grows to form a kind of fur...

Ce livre est très bien écrit, érudit sans être ennuyeux, illustré par des références très pertinentes et originales. C’est donc une lecture à recommander, qui change vraiment notre regard sur les rapports de l’architecture avec son environnement. Mais pourquoi en parler dans un lieu dédié aux modèles mathématiques et génératifs ? En fait, un certain nombre projets sont aussi intéressants de ce point de vue.

This book is excellently written, erudite without being annoying, illustrated with pertinent and original references. It is then highly commendable, it actually changes our way of looking at the relationships between architecture and its environment. But why mention it on this blog which is about mathematical and generative models? Some projects are actually interesting from that point of view too.

On y trouve par exemple une nouvelle version de bouteille de Klein avec le projet Mosquito Bottleneck par R&Sie(n) :
There is for instance another version of Klein's Bottle with Mosquito Bottleneck by R&Sie(n):

et une grotte à base de cristaux irréguliers par Aranda\Lasch :
and a grotto based upon irregular crystals be Arand\Lasch:

Plusieurs projets intègrent des processus de croissance, en particulier B_mu Tower par R&Sie(n), que l’on pourrait sans doute simuler par un modèle de type DLA :
Some projects comport growth processes, for instance B_mu Tower by R&Sie(n), which one could probably simulate a DLA model:

Ce livre est donc aussi une source d’inspiration pour l’application de modèles mathématiques et génératifs.

This book is then also a source of inspiration for the use of mathematical and generative models.