Algorithm for Graph Visibility Obtainment from a Map of Non-Convex Polygons Articles uri icon

publication date

  • April 2014

start page

  • 150

end page

  • 170


  • 2


  • 3

International Standard Serial Number (ISSN)

  • 2278-0149


  • Disponible en: ---Abstract: Visibility graphs are basic planning algorithms,widely used in mobile robotics and other disciplines. The construction of a visibility graph can be considered a tool based on geometry that provides support to planning strategies in mobile robots. Visually, the method is used to solve that planning, which is quite extended due to the simplicity of operating with polygons, that represent obstacles in the environment. The cost of these algorithms tend to be quite low. The most sensitive issue of obtaining visibility between polygons is in cases in which the polygons are non-convex. In such cases, it is obligatory to know whether the area where one vertex of the polygon is found, is located in a convex or non-convex area, being desirable to distinguish between both situations in a simple way, issue that was not possible up to now. To obtain the visibility of non-convex polygons, the authors have developed a visual and intuitive method which gives the machine the ability to interpret the visibility with a simplicity similar to the human mind.


  • path planning algorithm; mobile robots algorithm; visibility graph; visibility in non-convex polygons