生成连通凸多边形图
我正在尝试绘制诸如 this 等点的密集图形，并将其转换为图形连接的凸多边形。多边形应尽可能大且尽可能简单，同时保持连接。生成的图形将用于寻路。有人能指出我正确的方向吗？
I'm trying to take a dense graph of points such as this, and turn it into a graph of connected convex polygons. The polygons should be as large and as simple as possible while staying connected. The resultant graph will be used for pathfinding. Can anyone point me in the right direction?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
很烦人的是我无法发布链接。使得成为潜伏者变得困难&只是偶尔的参与者。
我最终使用了以下技术：
首先，创建距离变换。我使用了此处描述的算法[无法链接]，产生了这样的图像[无法链接]。然后，创建 DT 的分水岭变换，将其划分为多个区域。这需要一些工作，但目前看起来像这样[无法链接] 然后，使用连接每对区域的折线的中点来创建航点图。
结果
分水岭分区还不完美，请注意导致条带的锯齿，但我最终得到 181这张 128x128 地图的区域和 281 个航路点。
It is very annoying that I can't post links. Makes it hard to be a lurker & only occasional participator.
I ended up using the following techniques:
First, create a distance transform. I used the algorithm described here [can't link], resulting in an image like this [can't link]. Then, create a watershed transform of the DT to partition it into areas. This needs some work, but currently looks like this [can't link] Then, use the midpoints of the polylines connecting each pair of areas, to create a waypoint graph.
Result
The watershed partitioning isn't perfect yet, note the aliasing causing banding but I end up with 181 areas and 281 waypoints for this 128x128 map.
这不是您所要求的，但这里有一些解决此 2D 路径规划问题的其他想法：
使用 A*。这产生最短的无碰撞路径。即使不简化位图，性能也可能还不错。
使用基于采样的路线图。这是除多边形之外的另一种离散表示。由于您的搜索空间很小，因此您可以遍历整个位图来验证每个点都可以连接到路线图。如果紧凑路线图很重要（但短路径则不重要），则可以使用可见性路线图技术。
由于无论如何您都必须处理图形表示和图形搜索，因此这些技术看起来比多边形提取容易得多。我针对该问题挖掘了一些SO问题：
空间已被多边形映射（可能使用工具），它可以被分割成凸多边形或其他可以搜索的表示。 LaValle 也对此进行了讨论：
This is not what you asked for, but here are some other ideas for solving this 2D path planning problem:
Use A*. This yields the shortest collision free path. Performance might be OK, even with no simplification of the bitmap.
Use a sampling-based roadmap. This is another discretized representation than polygons. Since your search space is small, you can traverse the entire bitmap to verify that every point can be connected to the roadmap. If a compact roadmap is important (but short paths are not), the visibility roadmap technique can be used.
Since you have to deal with graph representation and graph searching anyway, these techniques seem much easier than polygon extraction. I dug up some SO questions for that problem:
When the space has been mapped by polygons (possibly using a tool), it can be split into convex polygons or some other representation that can be searched. This is also discussed by LaValle: