Traversable Region Model and Its Automatic Extraction Algorithm for Indoor Navigation

For the application requirement of route planning and navigation in indoor Location-based-service, we propose a traversable region model based on grid space and its automatic extraction algorithm. Firstly, this paper introduces adjoin grid and traversing grids based on grid model, expounds the basic principle of traversable region model through specific example. Then, according to the characteristics of indoor map data, through indoor grid model initialization, traversable region preliminary extraction and adjoin region merge, it designs traversable region automatic extraction algorithm. Finally, taking Xidan Joy City first floor indoor map data as an example, we perform different grid scale traversable region automatic extraction and route planning experiment. Results show that the automatic extraction algorithm has preferable applicability to deal with complex indoor environment which has barrier in the corridor and so on. Compared with network model, the route planning results of traversable region model are more conformed to the route walking feature of complex indoor environment.