236
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Algorithms"
SCI/FreeSCI/Pathfinding/Algorithms (view source)
Revision as of 02:26, 30 January 2009
, 02:26, 30 January 2009Fixed a reference link that was broken, replaced it by another source. Added source to another.
m (Adding ISBN, SOI and ISSN links) |
m (Fixed a reference link that was broken, replaced it by another source. Added source to another.) |
||
| Line 4: | Line 4: | ||
==Pathfinding== | ==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. | 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 <ref> | An optimal O(n log n) shortest path algorithm was discovered by Hershberger and Suri <ref>John Hershberger, Subhash Suri, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2037 "An optimal algorithm for Euclidean shortest 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. [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>. | 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>. | ||
| Line 19: | Line 18: | ||
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. | 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> | However, we recently found claims to the contrary <ref>Dan Sunday. [http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm Fast Winding Number Inclusion of a Point in a Polygon], 2001.</ref>. 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 <i>p</i> intersects | 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 <i>p</i> intersects | ||