Pathfinding algorithms for continuous maps (e.g. polygons)

Question

I try to investigate different algorithms for a short path between two points in a plane with polygonal obstacles.

The vast majority of algorithms I found use discrete maps (Grid Map, visibility graph, Voronoi Roadmap, etc.).

Some books (like “Elements of Robotics” by Ben-Ari or “Introduction to Autonomous Robots” by Nikolaus Correll) mention continuous maps (e.g. raw polygon data), but do not explain corresponding algorithms. They claim memory or efficiency advantages for few and simple obstacles, which could be very interesting for me.

I believe, there should be a clever approach using geometric calculation (e.g. intersection detection) and some algorithmic paradigm (e.g. least cost branch and bound), but I do not want to poorly reinvent the wheel.

Are there any resources for some short(est) path algorithms using continuous maps or useful keywords to search for?

---

Like suggested, I try to specify some of the terms I used:

1. Continuous maps

refer to the storage of (continuous) real number values of geometric shapes. Obstacle/Triangle I. would be stored as: A = (3,2), B=(7,5), C=(7,2).

2. Discrete maps

refer to the sub-division into chunks (discretization, e.g. like in a grid map). Obstacle/Triangle I. would now be stored as cell indices:

(3,2), (4,2), (5,2), (6,2), (5,3), (6,3), (6,4)

path-finding in discrete maps is often accomplish by graph based algorithms like Dijkstra or A*.

3. Geometric calculation is just a vague term I use for operations of computational geometry I would expect in a path-finding algorithm for continuous maps. (e.g. Translation, perpendicular distance, intersection detection)

Answer 1

Another, more often used, term for my problem seem to be Euclidean Shortest Path(s). The distinction between algorithms for Continuous maps and Discrete maps seems to be a bit ambiguous to me.

However, the nearest thing I found to an algorithm for a continuous map is Mitchell’s Algorithm for the Continuous Dijkstra Problem (or continuous Dijkstra method). This algorithm uses wavelets that spread evenly from the starting point. By “diffraction” of the wavelets, they reach areas that cannot be reached directly. This creates a shortest-path map which can be used to identify the Euclidean shortest path to any point in the continuous configuration space.

For more see:

• "Euclidean Shortest Paths Exact or Approximate Algorithms" by F. Li and R. Klette
• nice but a bit buggy animation by Ivan Chen
• application by Anton Kovsharov

One may argue, that the created shortest-path map is just a another discretisation of the continuous configuration space. However, I guess the shortest-path map is just an result which can be obtained, if the algorithm is applied to the entire configuration space. If just the shortest path between two points is wanted, the algorithm could stop after reaching the target point. I remain unsure about the classification of these algorithms but this should answer my question.

Answer 2

For the "continuous maps" as you called it, just use Dijkstra on all of you vertices. The only difference is that you have to check for clipping when calculating the distance between nodes.