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?
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.
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.
