连续地图（例如多边形）的寻路算法
Pathfinding algorithms for continuous maps (e.g. polygons)
我尝试研究具有多边形障碍物的平面中两点之间的短路径的不同算法。
我发现的绝大多数算法都使用离散图（网格图、可见性图、Voronoi 路线图等）。
有些书（比如 Ben-Ari 的“Elements of Robotics”或者 Nikolaus Correll 的“Introduction to Autonomous Robots”）提到了连续地图（例如原始多边形数据），但没有解释相应的算法。他们声称内存或效率优势对于少数和简单的障碍，这对我来说可能非常有趣。
我相信，应该有一个聪明的方法使用几何计算（例如交叉点检测）和一些算法范式（例如最小成本分支定界），但我不想重新发明轮子。
是否有一些使用连续地图或有用关键字搜索的最短（最）路径算法的资源？
如建议的那样，我尝试指定我使用的一些术语：
- 连续贴图
指几何形状的（连续）实数值的存储。 Obstacle/Triangle I. 将存储为：A = (3,2), B=(7,5), C=(7,2).
- 离散映射
指的是细分为块（离散化，例如在网格图中）。 Obstacle/Triangle I. 现在将存储为单元格索引：
(3,2), (4,2), (5,2), (6,2), (5,3), (6,3), (6,4)
离散地图中的寻路通常是通过基于图的算法完成的，例如 Dijkstra 或 A*。
- 几何计算 只是我用于计算几何运算的模糊术语，我希望在连续的寻路算法中使用地图。 （例如平移、垂直距离、交点检测）
对于你所说的“连续映射”，只需在所有顶点上使用 Dijkstra。
唯一的区别是在计算节点之间的距离时必须检查裁剪。
我的问题的另一个更常用的术语似乎是欧几里得最短路径。 连续映射和离散映射算法之间的区别对我来说似乎有点模棱两可。
然而，我发现最接近连续映射算法的是 Mitchell 的连续 Dijkstra 问题算法（或连续 Dijkstra 方法）。
该算法使用从起点均匀分布的小波。通过小波的“衍射”，它们到达无法直接到达的区域。这将创建一个 shortest-path 映射，可用于识别到连续配置中任意点的欧几里德最短路径 space。
更多请看：
- F. Li 和 R. Klette 的“欧几里德最短路径精确或近似算法”
- nice but a bit buggy animation by Ivan Chen
- application by Anton Kovsharov
有人可能会争辩说，创建的 shortest-path 地图只是连续配置 space 的另一种离散化。但是，我猜 shortest-path 映射只是一个可以得到的结果，如果算法应用于整个配置 space。如果只需要两点之间的最短路径，算法可以在到达目标点后停止。
我仍然不确定这些算法的分类，但这应该可以回答我的问题。
我尝试研究具有多边形障碍物的平面中两点之间的短路径的不同算法。
我发现的绝大多数算法都使用离散图（网格图、可见性图、Voronoi 路线图等）。
有些书（比如 Ben-Ari 的“Elements of Robotics”或者 Nikolaus Correll 的“Introduction to Autonomous Robots”）提到了连续地图（例如原始多边形数据），但没有解释相应的算法。他们声称内存或效率优势对于少数和简单的障碍，这对我来说可能非常有趣。
我相信，应该有一个聪明的方法使用几何计算（例如交叉点检测）和一些算法范式（例如最小成本分支定界），但我不想重新发明轮子。
是否有一些使用连续地图或有用关键字搜索的最短（最）路径算法的资源？
如建议的那样，我尝试指定我使用的一些术语：
- 连续贴图
指几何形状的（连续）实数值的存储。 Obstacle/Triangle I. 将存储为：A = (3,2), B=(7,5), C=(7,2).
- 离散映射
(3,2), (4,2), (5,2), (6,2), (5,3), (6,3), (6,4)
离散地图中的寻路通常是通过基于图的算法完成的，例如 Dijkstra 或 A*。
- 几何计算 只是我用于计算几何运算的模糊术语，我希望在连续的寻路算法中使用地图。 （例如平移、垂直距离、交点检测）
对于你所说的“连续映射”，只需在所有顶点上使用 Dijkstra。 唯一的区别是在计算节点之间的距离时必须检查裁剪。
我的问题的另一个更常用的术语似乎是欧几里得最短路径。 连续映射和离散映射算法之间的区别对我来说似乎有点模棱两可。
然而，我发现最接近连续映射算法的是 Mitchell 的连续 Dijkstra 问题算法（或连续 Dijkstra 方法）。 该算法使用从起点均匀分布的小波。通过小波的“衍射”，它们到达无法直接到达的区域。这将创建一个 shortest-path 映射，可用于识别到连续配置中任意点的欧几里德最短路径 space。
更多请看：
- F. Li 和 R. Klette 的“欧几里德最短路径精确或近似算法”
- nice but a bit buggy animation by Ivan Chen
- application by Anton Kovsharov
有人可能会争辩说，创建的 shortest-path 地图只是连续配置 space 的另一种离散化。但是，我猜 shortest-path 映射只是一个可以得到的结果，如果算法应用于整个配置 space。如果只需要两点之间的最短路径，算法可以在到达目标点后停止。 我仍然不确定这些算法的分类，但这应该可以回答我的问题。