Visibility Road-Map planner
This visibility road-map planner uses Dijkstra method for graph search.
In the animation, the black lines are polygon obstacles,
red crosses are visibility nodes, and blue lines area collision free visibility graphs.
The red line is the final path searched by dijkstra algorithm frm the visibility graphs.
Algorithms
In this chapter, how does the visibility road map planner search a path.
We assume this planner can be provided these information in the below figure.
Start point (Red point)
Goal point (Blue point)
Obstacle polygons (Black lines)
Step1: Generate visibility nodes based on polygon obstacles
The nodes are generated by expanded these polygons vertexes like the below figure:
Each polygon vertex is expanded outward from the vector of adjacent vertices.
The start and goal point are included as nodes as well.
Step2: Generate visibility graphs connecting the nodes.
When connecting the nodes, the arc between two nodes is checked to collided or not to each obstacles.
If the arc is collided, the graph is removed.
The blue lines are generated visibility graphs in the figure:
Step3: Search the shortest path in the graphs using Dijkstra algorithm
The red line is searched path in the figure:
You can find the details of Dijkstra algorithm in Dijkstra algorithm.