This paper presents a novel approach to create polygonal maps from 3D point cloud data. The gained map is augmented with an interpretation of the scene. Our procedure produces accurate maps of indoor environments fast and reliably. These maps are successfully used by different robots with varying sensor configurations for reliable self localization.