Difference between revisions of "SCI/FreeSCI/Pathfinding/Algorithms"

SCI/FreeSCI/Pathfinding/Algorithms (view source)

Revision as of 18:02, 29 January 2009

264 bytes added , 18:02, 29 January 2009

m

Adding ISBN, SOI and ISSN links

Timofonic

245

edits

@@ Line 7: / Line 7: @@
 Paths in the Plane, SIAM Journal on Computing, Vol. 28 , No. 6, pp. 2215-2256, December 1999.</ref>, 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 <i>P</i> a visibility graph <i>G</i> contains all vertices of the polygons in <i>P</i>. The start and end point are added to <i>G</i>.<i>G</i> has an edge between two vertices <i>v</i> and <i>w</i> if the line (<i>v</i>, <i>w</i>) does not intersect the interior of any polygon in <i>P</i>. 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 <i>n</i> vertices contains n<sup>2</sup> edges in the worst case. This means that any shortest path algorithm based on visibility graphs will have at least <i>O(n<sup>2</sup>)</i> running time. The trivial algorithm determines the visibility of two vertices <i>v</i> and <i>w</i> by testing for an intersection between the line (<i>v</i>, <i>w</i>) and all edges in the input set, leading to <i>O(n<sup>3</sup>)</i> running time.
-Optimal <i>O(n<sup>2</sup>)</i> visibility graph algorithms based on arrangements have been found <ref>T. Asano, T. Asano, L. J. Guibas, J. Hershberger and H. Imai. Visibility of disjoint polygons, Algorithmica, Vol. 1, pp 49-63, 1986.</ref> <ref>E. Welzl. Constructing the visibility graph for <i>n</i> line segments in <i>O(n<sup>2</sup>)</i> time, Information Processing Letters, pp 167-171, 1985.</ref>. Ghosh and Mount discovered an output sensitive <i>O(E + n log n)</i> algorithm <ref>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.</ref>, where <i>E</i> is the number of edges in the visibility graph. We finally opted to use an <i>O(n<sub>2</sub> log n)</i> 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.
+Optimal <i>O(n<sup>2</sup>)</i> visibility graph algorithms based on arrangements have been found <ref>T. Asano, T. Asano, L. J. Guibas, J. Hershberger and H. Imai. Visibility of disjoint polygons, Algorithmica, Vol. 1, pp 49-63, 1986.   [http://www.worldcat.org/issn/0178-4617 ISSN 1432-0541]</ref> <ref>E. Welzl. Constructing the visibility graph for <i>n</i> line segments in <i>O(n<sup>2</sup>)</i> time, Information Processing Letters, Volume 20, Issue 4, 10 May 1985, Pages 167-171, [http://dx.doi.org/10.1016/0020-0190(85)90044-4 Doi:10.1016/0020-0190(85)90044-4]</ref>.
+Ghosh and Mount discovered an output sensitive <i>O(E + n log n)</i> algorithm <ref>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, [http://www.worldcat.org/issn/0097-5397 ISSN 0097-5397].</ref>, where <i>E</i> is the number of edges in the visibility graph. We finally opted to use an <i>O(n<sub>2</sub> log n)</i> 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 <i>v</i> the set of vertices that is visible from <i>v</i>. The basic idea is to rotate a sweeping line clockwise around <i>v</i>. All edges that are currently intersected by the sweeping line are maintained in a tree <i>T</i> which is updated as the line rotates. The edges in <i>T</i> are ordered by distance from <i>v</i>. The sweeping line is implemented by sorting the vertices by angle around <i>v</i> and then processing them in that order.
-For each vertex <i>w</i> in the sorted list the visibility is computed and <i>T</i> is updated by removing edges incident to <i>w</i> in anticlockwise direction, and adding edges incident to <i>w</i> in clockwise direction. Vertex <i>w</i> is visible if the following two conditions hold. The first condition is that the line (<i>v</i>, <i>w</i>) does not intersect the inside of the polygon of which <i>w</i> is a vertex, locally at <i>w</i>. The second is that the edge in <i>T</i> closest to <i>v</i> does not properly intersect the line (<i>v</i>, <i>w</i>). There are a few degenerate cases which we will not discuss here. A more in-depth discussion of this algorithm can be found in <ref>M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf. Computational geometry: Algorithms and applications, Section 15.2, Springer-Verlag, Berlin, 1997.</ref>.
+For each vertex <i>w</i> in the sorted list the visibility is computed and <i>T</i> is updated by removing edges incident to <i>w</i> in anticlockwise direction, and adding edges incident to <i>w</i> in clockwise direction. Vertex <i>w</i> is visible if the following two conditions hold. The first condition is that the line (<i>v</i>, <i>w</i>) does not intersect the inside of the polygon of which <i>w</i> is a vertex, locally at <i>w</i>. The second is that the edge in <i>T</i> closest to <i>v</i> does not properly intersect the line (<i>v</i>, <i>w</i>). There are a few degenerate cases which we will not discuss here. A more in-depth discussion of this algorithm can be found in <ref>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.</ref>.
 ==Polygon containment==
-For a point <i>p</i> and a possibly non-convex polygon <i>P</i> we need to be able to determine whether <i>p</i> is contained in <i>P</i>. One common method for solving this problem is the winding number approach. The winding number of a point <i>p</i> and a polygon <i>P</i> is the number of times <i>P</i> winds around <i>p</i>. For simple polygons this number is 1 when <i>p</i> is contained in <i>P</i> and 0 when <i>p</i> is not contained in <i>P</i>. We decided not to use this method based on a claim in <ref name="compgeo">J. O’Rourke. Computational geometry in C, second edition, Cambridge University Press, Cambridge, 1998.</ref> that it is very inefficient.
+For a point <i>p</i> and a possibly non-convex polygon <i>P</i> we need to be able to determine whether <i>p</i> is contained in <i>P</i>. One common method for solving this problem is the winding number approach. The winding number of a point <i>p</i> and a polygon <i>P</i> is the number of times <i>P</i> winds around <i>p</i>. For simple polygons this number is 1 when <i>p</i> is contained in <i>P</i> and 0 when <i>p</i> is not contained in <i>P</i>. We decided not to use this method based on a claim in <ref name="compgeo">J. O’Rourke. Computational geometry in C, second edition, Cambridge University Press, Cambridge, 1998, ISBN 0521640105.</ref> that it is very inefficient.
 However, we recently found claims to the contrary <ref>B. Sunday. Fast Winding Number Inclusion of a Point in a Polygon, http://www.geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm, 2001.</ref>. In hindsight dismissing this method was premature.