Fast routing graph extraction from floor plans

A routing graph allows to find paths in buildings quickly. Raster images of floor plans are simple to obtain but display poor performance. A manually constructed graph is quite optimal if designed by an informed person, but the process is time consuming and expensive. We describe a fast method to calculate a 2D routing graph from raster images. We adapt image processing techniques and apply a conditional erosion technique. A conditional query of every pixel by means of a predefined 3×3 image matrix calculates an approximation of common walkways through corridors and rooms. We translate the image processing idea into propositional logic formulas and simplify them. Compared to our previous work, we reduce the run time by about 90 % and the amount of needed matrices from 29 to eight or even four, depending on the specific application. We also present a parallel version at the cost of redundant edges in the resulting routing graph.