我正在尝试获取诸如this的密集点图，并将其转换为连接的凸多边形图。多边形应尽可能大且尽可能简单，同时保持连接。结果图将用于寻路。谁能指出我正确的方向？
问问题
940 次
2 回答
1
我不能发布链接非常烦人。很难成为潜伏者和偶尔的参与者。
我最终使用了以下技术：
首先，创建一个距离变换。我使用了此处描述的算法[无法链接]，得到了这样的图像[无法链接]。然后，创建 DT 的分水岭变换以将其划分为多个区域。这需要一些工作，但目前看起来像这样 [无法链接] 然后，使用连接每对区域的折线的中点来创建航点图。
分水岭划分还不完美，请注意导致条带的混叠，但我最终得到了这张 128x128 地图的 181 个区域和 281 个航点。
于 2011-02-02T05:16:40.297 回答
0
这不是您要求的，但这里有一些解决此 2D 路径规划问题的其他想法：
用一个*。这会产生最短的无碰撞路径。即使没有简化位图，性能也可能还可以。
使用基于抽样的路线图。这是不同于多边形的另一种离散表示。由于您的搜索空间很小，您可以遍历整个位图，以验证每个点都可以连接到路线图。如果紧凑的路线图很重要（但短路径不重要），则可以使用可见性路线图技术。
由于无论如何您都必须处理图形表示和图形搜索，因此这些技术似乎比多边形提取容易得多。我为这个问题挖了一些 SO 问题：
当空间已被多边形映射（可能使用工具）时，可以将其拆分为凸多边形或其他可以搜索的表示。LaValle 也讨论了这一点：
于 2011-01-21T02:47:11.867 回答