Medial Axis Transformation for Building Floor Plans

Overview

The Medial Axis Transformation (MAT) is a method that converts the two-dimensional layout of a building's interior space into a one-dimensional representation. This transformation is crucial because it reduces the complexity of the data while preserving essential information about the space's structure, including both circulation and partition details. This simplification facilitates easier computational analysis of complex building geometries.

This project implements the Medial Axis Transformation for building floor plans inside the Rhino / Grasshopper environment, with the goal of producing a robust, vector-based representation of interior space that supports downstream data-driven and machine learning applications.

Motivation

One of the primary motivations for using the Medial Axis is that most modern buildings are unique, making systematic and automated analysis challenging. The Medial Axis provides an automated method for identifying the inherent structure of interior space.

By capturing underlying structural and circulation information, the MAT opens up pathways for advanced applications in architecture, urbanism, and real estate, such as:

• Prediction of social or functional information (e.g., room usage levels)
• Classification of building layouts
• Generative design using Graph Neural Networks (GNNs)

Project Objective

The core objective of this project is to develop a custom implementation of the Medial Axis Transformation capable of handling complex shapes commonly found in real building floor plans, particularly polygons with interior holes.

Key requirements of the implementation include:

• A vector-based (non-raster) representation to maintain geometric precision
• Robust handling of highly symmetrical geometries without producing unstable results
• Seamless integration into the Rhinoceros–Grasshopper environment
• A graph-based output suitable for computational and data-driven analysis

Theoretical Background

The Medial Axis of a polygon is closely related to the Voronoi diagram of its boundary geometry. For floor plans represented as line segments, the Voronoi diagram provides a natural computational foundation for extracting medial axis segments.

However, Voronoi diagrams generated from boundary segments contain additional geometry that does not belong to the true medial axis. A substantial portion of this project therefore focuses on post-processing, classification, and filtering of Voronoi output to recover only the meaningful medial axis structure.

Implementation Overview

Two primary implementation paths were pursued in parallel.

Method 1: PyVoronoi-Based Implementation

This approach leverages PyVoronoi, a Python wrapper around Boost’s computational geometry algorithms, to generate Voronoi diagrams from floor plan line segments directly inside Grasshopper.

Tools

• Custom Grasshopper Python component
• Python 3
• PyVoronoi (Python port of Boost C++ computational geometry)

Input Representation

• Floor plans represented as integer-based line segments
• Includes both:
• Exterior polygon boundaries
• Interior holes and partitions

Processing Pipeline

1. Voronoi Diagram Generation
   A 2D Voronoi diagram is computed from the floor plan boundary segments.

2. Voronoi Cell Classification
   Voronoi edges are classified based on the originating boundary feature types, including:

3. Concave
4. Convex–Convex
5. Convex–Line

6. Line–Line

7. Medial Axis Extraction
   Voronoi geometry that does not correspond to the true medial axis is filtered out, leaving only valid medial axis segments.

8. Graph Construction
   The remaining medial axis segments are treated as nodes, adjacency relationships are computed, and a complete graph representation of the interior space is constructed.

Method 2: CGAL Library Port

The second implementation path focuses on utilizing CGAL (Computational Geometry Algorithms Library) to perform medial axis computation with greater robustness.

Architecture

A multi-layered framework bridges native CGAL C++ code into Rhino’s .NET environment:

1. Native C++ Layer
   Selected CGAL algorithms are compiled and exposed through a stable Application Binary Interface (ABI).

2. Native Interop Layer (.NET)
   Platform Invocation (P/Invoke) is used to call the native C++ functions.

3. .NET Bridge Layer
   CGAL data structures are converted into Rhino-compatible primitive types.

4. Grasshopper Component
   A user-facing component exposes the functionality within the Grasshopper interface.

Current Status

• The full framework has been successfully established using .NET 7, which is compatible with Rhino.
• The next milestone is the integration of 2D Voronoi segment computation, which forms the basis of the Medial Axis Transformation.
• More info here: https://github.com/VIP-SMUR/25Fa-MedialAxis/blob/main/cgal_port_2/README.md

Graph Representation

Once the medial axis segments are extracted and classified, they are used to build a graph structure that encodes the connectivity and topology of the building’s interior space.

This graph representation captures: - Circulation paths
- Spatial adjacency
- Topological structure of interior partitions

The resulting graph serves as the primary interface for downstream computational analysis and machine learning workflows.

Future Work

Data Integration and Machine Learning

Planned future work includes:

• Encoding semantic or social information directly onto the medial axis graph
• Converting graphs into Directed Acyclic Graphs (DAGs) where appropriate
• Training Graph Neural Networks (GNNs) for:
• Prediction tasks
• Building classification
• Generative architectural design

Presentation

Team