面向含多边形障碍物平面的连续地图最短路径算法资源问询

Great question—focusing on continuous-space solutions for sparse, simple obstacles is a smart move when you want to skip the memory and computation overhead of discretization (like grids or pre-built visibility graphs). Below are targeted keywords, algorithms, and resources to avoid reinventing the wheel:

Core Search Keywords #

These will help you find exactly the continuous-space, geometry-focused work you're looking for:

• Continuous-space shortest path planning
• Exact shortest path in polygonal domains
• Polygon obstacle shortest path (no discretization)
• Branch-and-bound geometric path planning
• Funnel algorithm shortest path
• Lee-Preparata algorithm

Key Algorithms to Explore #

All of these operate directly on continuous polygon data (no pre-discretization) and leverage geometric operations like intersection testing and visibility checks:

• Lee-Preparata Algorithm: A classic exact shortest path algorithm for polygonal obstacles. It constructs a "funnel" structure along the path, using real-time visibility checks and intersection detection to prune non-optimal paths. Perfect for sparse, simple obstacle scenarios since it avoids building a full visibility graph.
• Funnel Algorithm: A lightweight, incremental approach that refines the shortest path by maintaining a convex region (funnel) of feasible directions. It uses geometric calculations to shrink the funnel as it moves toward the goal, with minimal memory overhead.
• Lipschitz-Based Branch-and-Bound: These algorithms use geometric constraints (like the Lipschitz constant of the path cost) to compute lower bounds on potential paths, pruning branches that can't possibly be shorter than the current best. They pair perfectly with real-time intersection testing to validate continuous path segments.

Essential Resources #

• Book: Computational Geometry: Algorithms and Applications (de Berg et al.): Chapter 15 is dedicated to shortest paths in polygonal domains. It breaks down exact continuous-space algorithms step-by-step, including Lee-Preparata, and explains all required geometric operations (intersection detection, visibility queries) in detail.
• Book: Planning Algorithms (Steven LaValle): Chapter 12 covers exact shortest paths in continuous polygonal environments. It focuses on avoiding discretization and includes deep dives into visibility-based continuous planning and funnel algorithms.
• CGAL Library: The Computational Geometry Algorithms Library has a pre-built Polygon_mesh_processing::shortest_path module that implements exact continuous-space shortest paths for polygonal obstacles. It handles all the geometric heavy lifting, so you don't have to code intersection tests or funnel logic from scratch.

Pro Tip for Your Use Case #

Since you're targeting scenarios with few, simple obstacles, prioritize algorithms that avoid precomputing full visibility graphs. Lee-Preparata and funnel-based methods are ideal here—they only compute visibility on-the-fly, keeping memory usage low and runtime fast.

内容的提问来源于stack exchange，提问作者umfundi