Most of the existing staged evacuation algorithms only consider the impact of crowd density on evacuation partition, but do not take into account the influence of the spatial distribution of occupants and the capacity of exits on the total evacuation time (TET). Therefore, a novel indoor emergency evacuation algorithm based on time equalization is proposed in this paper. All factors affecting TET such as the position and size of each group and the capacity of exits are fully considered in the proposed algorithm, which are uniformly converted into the occupancy time of each exit. An improved Dijkstra algorithm is used to generate evacuation zones according to the proximity relationship and the occupancy time of different exits. The strategy of waiting at the starting point is adopted to ensure that all evacuees are free from congestion during the escape process. In addition, the method of group merging is proposed to further increase the balance among all zones during the partitioning process. The objectives of the proposed algorithm include minimizing the TET of all evacuees, the path length of each escape group, avoiding congestion during the escape process. The experimental results show that the proposed algorithm effectively reduces TET and the path length of groups compared with existing algorithms, which improves the efficiency of evacuation and utilization of all exits and can be applied to the various distribution and density of evacuees.

Indoor space information is the basis of indoor location services such as indoor navigation, path planning, emergency evacuation, etc. Focusing on indoor navigation needs, this paper proposes a fast construction algorithm for a complex indoor space topology model based on disjoint set for the problem of lacking polygon description and topological relationship expression of indoor space entity objects in building plan drawings. Firstly, the Tarjan algorithm is used for identifying the hanging edges existing in the indoor space. Secondly, each edge is stored as two different edges belonging to two adjacent polygons that share the edge. A ring structure is introduced to judge the geometric position of walls, and then an efficient disjoint set algorithm is used to perform set merging. After that, disjoint set is queried to obtain all indoor space contours and external boundary contours, thereby the complete indoor space topological relationship at multiple levels is established. Finally, the connectivity theory of graph is used for solving the problem of a complex isolated polygon in topology information generation. The experimental results show that the proposed algorithm has generality to efficiently complete the automatic construction of a topological model for complex scenarios, and effectively acquire and organize indoor space information, thus providing a good spatial cognition mode for indoor navigation.