Topological Mapping

In this research, I employ an elevation map to construct a topological map. Initially, the occupancy grid map is generated using the elevation map, delineating the areas that were occupied and unoccupied. Then, the Voronoi graph of the occupancy grid map was computed. To calculate the Voronoi graph, the Voronoi grids which have more than one nearest obstacle grids are first found. Then the critical grids which are the Voronoi grids with the local minimum distance to the nearest obstacle grids are generated. The critical lines are the lines connecting critical grids and corresponding nearest obstacle grids. The regions are surrounded by the critical lines and the obstacles. To simplify the division of regions, the adjacent regions are merged based on the convexity of the merged region. Finally, I utilize line fitting techniques to represent obstacles and connect region centers and the critical points to demonstrate safe paths within the map. Dijkstra shortest path algorithm can be applied to generate the shortest path from one node to another in the topological map with the safe paths.