The Research On Algorithm To Solve ESP Problem In A Given LR-Visibility Polygon

ESP(Euclidean shortest path) problem is a typical problem in Computational Geometry. This paper designs a simple and workable algorithm in terms of the algorithm research of the ESP problem in a given LR-visibility polygon, which provides technical support to solve some practical applications’problems, such as Watchman Route Problems and Robot motion planning problem etc. Therefore, the research on this problem has not only the theoretical significance, but also the practical value.This paper does a research on the ESP problem in a given LR-visibility polygon P to find a shortest path from a starting point s to another terminal point t inside P which is a LR-visibility polygon with respect to boundary points s and t.To solve the problem, this paper first gives a detailed introduction to the basic knowledge and algorithms in the field of Computational Geometry in relation to this problem. Then by analysising the relationship between the properties of LR-visibility polygon and the shortest path, this paper have come up with an idea about an algorithm which can compute the shortest path based on convex path. On this basis, this paper presents a shortest path algorithm computes the SP(s, t) by analysing the relationship between concave vertices of L chain and right convex path based on R chain of the LR-visibility polygon to determine which concave vertices of L chain belong to the SP(s, t). In order to verify effectiveness of the algorithm, this paper implements the algorithm using the representative test data and tests the running results.The results show that the algorithm is effective, and can compute the SP(s, t) from the given starting point s to the given terminal point t in terms of possible ESP problems in the LR-visibility polygons.