ALGORITHM FOR GRAPH VISIBILITY OBTAINMENT FROM A MAP OF NON-CONVEX POLYGONS

Abstract

Visibility gr aphs 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 providessupport 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 obstaclesin the environment. The cost of these algorithms tend to be quite low. The most sensitive issueof obtaining visibility between polygons is in cases in which the polygons are non-convex. Insuch 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 situationsin a simple way, issue that was not possible up to now. To obtain the visibility of non-convexpolygons, the authors have developed a visual and intuitive method which gives the machine theability to interpret the visibility with a simplicity similar to the human mind.