A Computational Method For Generating Convex Maps Using the Medial Axis Transform

Convex maps were first introduced by Hillier and Hanson in “The social logic of space”, and have since become a standard diagram of space syntax, particularly in the analysis of interior of buildings. Despite of their extensive use, the computer generation of convex maps turns out to be quite difficult. An algorithmic description of the process would afford an objective form of reproducing analysis results and the consistent application of the same method on a set of data; unfortunately the original guidelines to draw convex maps by hand have been shown to be impossible to translate into a formal description of the type necessary for a computer program. Thus, rather than attempting a translation of the original procedure, we have looked at alternatives methods for producing convex maps in the field of shape analysis. In particular we have studied a set of problems which deal with the decomposition of shapes into simpler parts and their organisation,and which are conceptually related to the convex map. We have accordingly developed a method for subdividing architectural plans into non overlapping, convex partitions that captures their most salient organisational features, based on the medial axis transform, a well known shape descriptor first proposed by H.Blum in 1967. Our method is based on adding the simpler convex regions defined through the segments and branching points of the medial axis according to different priorities, under the condition that these additions remain convex. In space syntax the automatic production of convex spaces has often focused on their instrumentality in the calculation of axial maps, and has not have the convex map as the final objective.The method we have developed, in the other hand, produces convincing convex partitions and maps, which often coincide with those resulting from following the original hand-drown method description. Its results can be used for representing the organisation of spaces at the level of simplicity and abstraction of the original convex partitions proposed by Hillier and Hanson, and to allow the study of their configuration through the application of different graph measures and visualisation techniques. We have implemented our methods in C++. The effective calculation of the medial axis required the use of robust and reliable computational geometry libraries, and consequently we have based most of our geometric data-structures and algorithms in those provided by CGAL, a well tested and widely used library distributed under GPL/LGPL license. Besides CGAL our tests and demonstration programs also use a number of different libraries, such as Dime, for dxf input and output or Qt, for GUI and interaction.Approved for publication via Diva by Conference Organisers. QC 20140103