生成连接的凸多边形的图形

我试图采用诸如this的点的密集图形，并将其变成连接的凸多边形的图形。在保持连接的同时，多边形应该尽可能大且尽可能简单。结果图将用于寻路。任何人都可以将我指向正确的方向吗？生成连接的凸多边形的图形

2011-01-20 Anthony

我无法想象这之前没有问过。请先搜索一下，这可能会给你一些想法。或者你可以通过解释为什么找到的解决方案不符合你的要求来更好地制定你的问题。 – 2011-01-20 21:35:22

看起来像星际争霸的地图... –

这完全是一个星际争霸地图。它是导航网格的自顶向下视图，可用作2D碰撞图的设置。我可以通过使用潜在字段来避免局部冲突，但是我需要一个真正的寻路解决方案来避免局部最优。本质上我需要凸多边形，以便我可以使用共享边的中点来查找路径。三角形也会起作用，但会产生更多的观点。 – Anthony

这是很烦人的，我不能发布链接。使其很难成为一名潜伏者&偶尔参与者。

我结束了使用以下技术：

首先，创建一个距离变换。我用这里描述的算法[无法链接]，导致像这样的图像[无法链接]。然后，创建DT的分水岭变换以将其分区。这需要一些工作，但目前看起来像这样[无法链接]然后，使用连接每对区域的多段线的中点来创建航点图。

分水岭划分尚不完善，需要注意的混杂造成绑扎，但我最终的181个区和281个航路点这个128x128的地图。

2011-02-02 05:16:40 Anthony

这不是你问什么，但这里有一些其他的想法解决这个二维路径规划问题：

使用*。这产生了最短的无碰撞路径。即使没有简化位图，性能也可能正常。
使用sampling-based roadmap。这是另一个离散的表示，而不是多边形。由于您的搜索空间很小，您可以遍历整个位图以验证每个点都可以连接到路线图。如果紧凑型路线图很重要（但短路径不重要），则可以使用visibility roadmap技术。

既然你要处理反正图表示和图搜索，这些技术似乎比多边形提取容易得多。我挖出该问题的一些SO问题：

当空间已经由多边形（可能使用的工具）映射，它可以分割成凸多边形或可以搜索的一些其他表示。这也由拉瓦列讨论：

2011-01-21 02:47:11 antonakos

回答