SCI/FreeSCI/Pathfinding/Algorithms
Algorithms
In this section we discuss the algorithms that were considered and motivate our final choice. We describe the pathfinding algorithms in Section 5.1 and the polygon containment algorithms in Section 5.2.
Pathfinding
We learnt by observation that the input size generally does not exceed 100 nodes. At these small input sizes the asymptotic performance of an algorithm is not very significant. We decided that we did not want to sacrifice ease of implementation for an algorithm with better asymptotic behaviour. We also decided to limit ourselves to true shortest path solutions, as we want Ego to take the shortest path to his destination. An optimal O(n log n) shortest path algorithm was discovered by Hershberger and Suri [1], but it is too complex to implement in such a short time frame. Simpler algorithms exist that are based on visibility graphs. For a polygon set P a visibility graph G contains all vertices of the polygons in P. The start and end point are added to G.G has an edge between two vertices v and w if the line (v, w) does not intersect the interior of any polygon in P. Once the visibility graph has been constructed the shortest path can be found by using an algorithm for determining the shortest path in a graph, such as Dijkstra’s algorithm. The visibility graph on n vertices contains n2 edges in the worst case. This means that any shortest path algorithm based on visibility graphs will have at least O(n2) running time. The trivial algorithm determines the visibility of two vertices v and w by testing for an intersection between the line (v, w) and all edges in the input set, leading to O(n3) running time.
Optimal O(n2) visibility graph algorithms based on arrangements have been found [2] [3].
Ghosh and Mount discovered an output sensitive O(E + n log n) algorithm [4], where E is the number of edges in the visibility graph. We finally opted to use an O(n2 log n) algorithm by Lee. This algorithm is relatively easy to implement and is fast enough for the small input sizes we are dealing with in this application.
The algorithm iterates over the vertices and determines for each vertex v the set of vertices that is visible from v. The basic idea is to rotate a sweeping line clockwise around v. All edges that are currently intersected by the sweeping line are maintained in a tree T which is updated as the line rotates. The edges in T are ordered by distance from v. The sweeping line is implemented by sorting the vertices by angle around v and then processing them in that order.
For each vertex w in the sorted list the visibility is computed and T is updated by removing edges incident to w in anticlockwise direction, and adding edges incident to w in clockwise direction. Vertex w is visible if the following two conditions hold. The first condition is that the line (v, w) does not intersect the inside of the polygon of which w is a vertex, locally at w. The second is that the edge in T closest to v does not properly intersect the line (v, w). There are a few degenerate cases which we will not discuss here. A more in-depth discussion of this algorithm can be found in [5].
Polygon containment
For a point p and a possibly non-convex polygon P we need to be able to determine whether p is contained in P. One common method for solving this problem is the winding number approach. The winding number of a point p and a polygon P is the number of times P winds around p. For simple polygons this number is 1 when p is contained in P and 0 when p is not contained in P. We decided not to use this method based on a claim in [6] that it is very inefficient.
However, we recently found claims to the contrary [7]. In hindsight dismissing this method was premature.
The method we used is called the ray crossings approach. This method is based on counting the number of times a ray extending right from p intersects the boundary of P. p is contained in P if the number of ray crossings is odd.
In its basic form this algorithm considers points on bottom and left edges to be contained in P, and points on top and right edges not to be contained in P.
This property is desirable for some applications, but as we have seen in Section 3.4, we need a point on any edge of P to be considered to be contained in P. In order to overcome this we used an extended version of this algorithm [6] that has the semantics we require.
References
- ↑ J. Hershberger and S Suri. An Optimal Algorithm for Euclidean Shortest Paths in the Plane, SIAM Journal on Computing, Vol. 28 , No. 6, pp. 2215-2256, December 1999.
- ↑ T. Asano, T. Asano, L. J. Guibas, J. Hershberger and H. Imai. Visibility of disjoint polygons, Algorithmica, Vol. 1, pp 49-63, 1986. ISSN 1432-0541
- ↑ E. Welzl. Constructing the visibility graph for n line segments in O(n2) time, Information Processing Letters, Volume 20, Issue 4, 10 May 1985, Pages 167-171, Doi:10.1016/0020-0190(85)90044-4
- ↑ S. K. Ghosh and D. M. Mount. An output-sensitive algorithm for computing visibility graphs, SIAM Journal on Computing, Vol. 20, No. 5, pp. 888 -910, October 1991, ISSN 0097-5397.
- ↑ M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf. Computational geometry: Algorithms and applications, Section 15.2, Springer-Verlag, Berlin, 1997, ISBN 3540-65620-0.
- ↑ 6.0 6.1 J. O’Rourke. Computational geometry in C, second edition, Cambridge University Press, Cambridge, 1998, ISBN 0521640105.
- ↑ B. Sunday. Fast Winding Number Inclusion of a Point in a Polygon, http://www.geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm, 2001.