生成连接的凸多边形的图

Question

我正在尝试绘制诸如 这个, ，并将其变成连接的凸多边形的图。多边形应在保持连接时尽可能大且尽可能简单。所得图将用于探路。谁能指向正确的方向？

Answer 1

我无法发布链接非常烦人。很难成为潜伏者，唯一的偶尔参与者。

我最终使用了以下技术：

首先，创建一个距离变换。我使用了此处描述的算法[无法链接]，从而产生了这样的图像[无法链接]。然后，创建DT的分水岭转换，将其划分为区域。这需要一些工作，但是目前看起来像这样[无法链接]，然后使用连接每对区域的polyline的中点，创建一个路点图。

结果

流域分区尚不完美，请注意引起频带的混叠，但我最终获得了这张128x128地图的181个区域和281个路点。

Answer 2

这不是您要求的，但这里还有其他一些解决这个2D路径计划问题的想法：

• 用一个*。这产生了最短的自由碰撞路径。性能可能还可以，即使没有简化位图。

• 用一个 基于抽样的路线图. 。这是除多边形以外的另一个离散表示。由于您的搜索空间很小，因此您可以遍历整个位图，以验证每个点可以连接到路线图。如果一个 袖珍的 路线图很重要（但没有短路）， 可见性路线图 可以使用技术。

由于您必须处理图形表示和图形搜索，因此这些技术似乎比多边形提取容易得多。我挖了一些问题，以解决这个问题：

• 将位图转换为多边形
• 如何将简单的形状位图转换为向量

当该空间由多边形映射（可能使用工具）时，可以将其分为凸多边形或可以搜索的其他一些表示。 Lavalle也讨论了这一点：

• 垂直（梯形）细胞分解
• 最短的路线图