Generate Graph of Connected Convex Polygons

Question

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?

Answer 1

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.

Answer 2

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:

• Convert Bitmap to Polygon
• How can i convert simple shape bitmap to vector

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:

• Vertical (trapezoidal) Cell Decomposition
• Shortest-Path Roadmaps