Hello, I am trying to implement a shortest path algorithm between two points with obstacles. I found this algorithm on the web and it works very well, it is what I need, but the algorithm is extremely slow. http://alienryderflex.com/shortest_path/ For example, using a polygon with 5 vertices, the algorithm compare the information 186 times because of its loop. Any advise on how can I resolve this kind of problem? Can I joint all the points and use the A* algorithm? This picture below shows what I need to do. The yellow green points are the vertices of my polygon, the black lines are the sides of my polygon, the yellow point are the start point and the end point and the blue lines are the result, the shortest path between the start point and the end point. The algorithm gives me the list of the points (vertices) that gives me the shortest path. BTW, How can I post a picture?

Your picture doesn't seem like a shortest path, unless I am not understanding what the obstacles are...

You can use html to post an image:

I haven't looked closely at the page you linked to, but the general technique to use would be,

1. Generate the visibility graph for the polygon. Its nodes are (set notation): {the polygon vertices} U {the start point} U {the end point}, and an edge exists between any two nodes in the graph IFF the line segment between them does not intersect any obstacles (or, in your case, "does not go outside the polygon-with-holes").

2. Do a graph search (e.g., A*) to find the shortest path on the visibility graph.

The question is: How to do #1? Quoting this paper,

Quote:

For general polygons (with holes), Overmars and Welzl [21] obtained a relatively simple O(k log n)-time method, requiring O(n) space. Then, Ghosh and Mount [13] obtained an O(k +n log n)-time algorithm, using O(k) storage. Pocchiola and Vegter [23] have improved the space bound to optimal using the concept of the visibility com- plex; their algorithm requires time O(k + n log n) and uses O(n) space.

where the referenced papers are

Quote:

[13] S. K. Ghosh and D. M. Mount. An output-sensitive algorithm for computing visibility graphs. SIAM J. Com- put., 20:888{910, 1991. [21] M. H. Overmars and E. Welzl. New methods for computing visibility graphs. In Proc. 4th Annu. ACM Sym- pos. Comput. Geom., pages 164{171, 1988. [23] M. Pocchiola and G. Vegter. Topologically sweeping visibility complexes via pseudo-triangulations. Discrete Comput. Geom., 16:419{453, Dec. 1996.

You might also want to take a look at this book.

However, in fact, even if you do #2 in an inefficient way, it may not matter, (e.g., an O(n) point-to-point visibility test for each of O(n^2) pairs of points, to yield an O(n^3) algorithm) since computing visibility between all pairs excluding the start and end nodes could be done as a preprocessing step. Then, adding your start and goal nodes to the graph can be done naively in O(n) time (and more efficiently using some of the algorithms described in the book I just mentioned), which is dominated anyway by the O(n^2) graph search that you do subsequently.

[Edited by - Emergent on April 3, 2009 11:01:34 AM]

Quote:

Your picture doesn't seem like a shortest path

You are right, mi mistake experimenting with the code, but the code is working fine. Here is the shortest path:



Emergent
Thank you for the explanation, but I think that the visibility graph it would be a complex solution for using in this problem. It must exist an algorithm than can be applyed to this problem.

I would try to optimize the "Shortest path" algorithm from Darel, but let me know if you have other ideas please.

Thanks.

If you use the algorithm in the link, but precompute the visibility graph instead of checking every node against every other in the pathfinding loop, it should be quite fast.

ok, you were right!!! Visibily graph is the answer to my problem. Thank you.

http://www.visilibity.org/