The following map is used to illustrate the algorithm:
-
Safety Buffer Addition:
- Compute the distance transform of the free space to determine the shortest distance to the nearest obstacle for each free pixel.
- Mark pixels within the safety buffer as obstacles.
-
Skeleton Graph Construction:
- Build the graph based on the skeleton of the map.
- Identify branches in the skeleton and add nodes from one end to the other, connecting consecutive nodes.
-
Boundary Node Creation:
- Increase the safety buffer around obstacles.
- Identify contours of the obstacles and add nodes along these contours to improve node distribution near obstacles.
-
Node Placement in Free Space:
- Compute the distance transform of the free space to existing nodes.
- Place nodes at local maxima that are sufficiently distant from existing nodes.
- Repeat until no more suitable local maxima are found.
-
Triangulation and Edge Addition:
- Perform Delaunay triangulation on the nodes.
- Add edges between nodes connected by the triangulation.
-
Graph Pruning:
- Remove isolated nodes, small subgraphs, and node clusters to refine the graph.
