Research On Algorithms Of Finding A Shortest Path About The Point Set Given In A Simple Polygon

In this paper,we mainly study the shortest path in simply polygon through some known points,and come up with a method to solve it.We already know a set P of n points,the starting point s and the ending point t.We need to find the shortest path from s to t through some points of P.If such a path exists,then output it.Otherwise,output not exist.This problem is the deformation problem of TSP problem,but also is the abstract model of a lot of applications.So,the research of this problem not only has theoretical significance,but also has great practical value.This paper firstly analyzes the relationship between visibility and the shortest path calculation,then through analyzing the characteristic of convex and concave of simple polygon vertices,dividing the simple polygon into some side chains.Find the visible set corresponding to the side chain and the points distribution to each visible set are visible.Then compute all the visible points of given point set and calculate the shortest path from s to t.Because the given point set is arbitrary,the shortest path may not exist.This paper makes a detailed analysis of the existence of the shortest path and design the corresponding algorithm to find the shortest path.In order to verify the validity of the designed algorithm,this paper achieve the algorithm and analyze the result of the algorithm.The.result shows that the designed algorithm is efficient and the performance is better than the output-sensitive algorithm.