This problem is a classic topic in the geometry: the shortest path problem with obstacles (ESP0)
The ESPO can be described below: two points S and T, and the polygonal disorder set ω = {ω1, ω2, ..., ω k}, requiring the shortest path of all obstacles by S to T.
The ESPO problem in the plane can solve in the polynomial time, while the problem of determining the shortest path length when there is a multi-facet obstacle in E ^ 3 is NP.
A simple algorithm is as follows: The shortest path of S to T is a fold line chain, the vertex of the chain is the vertex of the polygonal obstacle. Using Dijkstra's shortest circuit algorithm and viewing algorithm can solve the ESPO problem, with a time complexity of 0 (n ^ 2). If the view is sparse, the solution can be determined within the O (M NLOGN) time, where M is the number of views.
There are also some better algorithms for this issue, and simply introduce: Using the shortest path mapping spm (s, ω) in O (n (k logn)) time to solve the eSPO problem of ease polygonal obstacles The method is proposed by REIF and Storer. If a given SPM (S, Ω), the domain containing T can be determined within the O (LOGN) time, and the path to T can be determined within the 0 (B logn) time, where B is the number of line segments on the path. . Welzl et al. Utilizes an algorithm for the ESPO problem of the N line segment on the plane, which requires 0 (n ^ 2) time. It is not difficult to modify this algorithm to process polygon obstacles and have the same time complexity. Note that if the viewing method is used, the limit 0 (n ^ 2) will not be improved. The 0 (n ^ 2) algorithm of the shortest path between the two objects (rather than point) in the polygon object is known. When N is a set of parallel lines, Lee and Preparata propose an θ (NLOGN) plane scan algorithm. The line segment passes through the scan line and map the shortest path to the scan line. A 0 (n ^ 2) algorithm without the shortest path on the plane can handle the line segment that avoids N. Rohnert gives an algorithm for avoiding the O (NLOGN K ^ 2) time of the minimum path of the K m-axis. This time limit is achieved under the conditions of O (k ^ 2 Logn N) time and O (N K ^ 2) space pre-treatment obstacles. The pretreatment includes a sub-map for constructing a view. Rohnert also gives an algorithm that avoids the o (knlogn) time and O (n) space of the minimum path of the k molt barrier. The latter does not need to pre-treat obstacles, but use the Dijkstra shortest path algorithm to calculate the visibility online. When there is k m-axes in the plane and its boundary, the algorithm given by Rohnert can find the shortest path between two points in the plane, with a time complexity of O (NLOGN K ^ 2). This time limit is achieved under the conditions of O (NLOGN K ^ 3) time and O (N K ^ 2) space pretreatment obstacles.
The above algorithms you can refer to the relevant papers. (Go to http://cora.whizBang.com/ Search "ESPO" keyword) For the case of multifaceted obstacles in E ^ 3, because it is NP, it does not discuss it, but now there is a lot of mature polynomial times. Approximate algorithm.
