A Study Of Online Exploring Strategies For The Polygon With A Hole

Based on the solution thoughts of Watchman Route Problem(WRP),part shortest path and other problems,with the achievements in the field of polygon exploration,this paper studies the online exploration problem with polygons on the plane.The goal is to design an online exploration strategy to make the robot to find a closed path start from a given starting point in a polygon with holes and see all the areas inside the polygon.The research of the Online exploration problems involves basic foundation knowledge such as dynamic search,optimal path planning,algorithm design and analysis.It is a theoretical subject in the field of computational geometry and has high theoretical research value.At the same time,Online exploration problem has a widely application prospect in practical applications such as robot target search and exploration the unknown areas.This paper first discusses the basic knowledge and basic algorithms related to Online exploration problems,and analyzes the existing research results of polygon exploration problems,such as key image points and the access to the key cuts methods.Based on these,combined with the geometric information of polygons with holes,after analysis we proposes a solution to transform the online exploration problem with a polygon into a plurality of simple polygons and then explore separately.To this end,this paper first studies the simple polygon exploration algorithm without holes,and then analyzes the state attribute of the "holes" in the exploration problem with the polygon.By dividing the state attribute,select the appropriate construction method and transform it into simple polygon.The polygon is been transformed into a simple polygon after transformation,and we call simple polygon exploration algorithm to complete the exploration.Finally,combine with the exploration algorithms of each simple polygons,the online exploration algorithm for polygons with one hole has designed.The designed algorithm has analyzed and the algorithm visualization operation has given.The experiment results show that the online exploration strategy for the polygons on the plan is an effective algorithm.