I am looking to try and create a flood-fill type algorithm, but one which will break the space into convex regions.
In terms of what my application has in terms of data, all it has is a grid of squares where each square contains connections to the surrounding squares in the cardinal direction. If a square is blocked or invalid in some way, then the square I'm testing won't have a connection in that direction. Screenshot below illustrates what I mean, where black squares are invalid and represent the boundaries of objects:
What I want to do now is try to come up with an algorithm which means I can tag each grid square as belonging to a convex region, ideally with as few areas as possible (i.e. favouring larger convex areas rather than lots of little fragments). Something like the below where each colour represents a different convex region:
Is there a known algorithm for this? I've looked at a few flood-fill algorithms, but none of them seem to be able to form convex shapes like this.
Thanks!
