I have a set of tiles in an hexagonal coordinate system, and I want to see whether it forms an "almost convex" region. By almost convex, I mean that a square with zigzaging hex edges would still count as convex.

The idea is to split non convex regions into convex ones, and merge small regions into larger convex ones.

What I don't want is merging a corridor with a room or 2 rooms separated by a wall together.

I was thinking about sweeping a line along 2 axis and see whether it goes through any missing tile (in case of diagonal, the check would fail only if both tiles are missing).

Would that work?

Edit: it wouldn't, as a L or cross shaped area would pass.

How can I do it?

I found a way to do it:

First of all, tiles that were surrounded by 4 tiles of another region were converted to this region to avoid weird borders, until there was no such tile left.

The polygon theorem says that all the angles of a polygon should be clockwise or counter clockwise.

In a hexmap, that would translate more or less to: no hexagon that is not in the area should be adjacent to 3 or more hexagons of the area.

If we didn't care about the quasi convex corner cases, just checking that no neighbors  is close to 3 region hex would be enough, but we also have to make sure our algorithm does not throw away cases we want to keep.

One way to do that would be to check that the region does not cross the zigzaging line passing through one of these neighbors:(cf image convex3b.png) 

In my game, I chose to accept a more lenient check that still result in reasonably

shaped areas. (because it works better with the shape of my walls).

I think you could also consider just the centroid of each hexagon and then use the usual algorithms like gift wrapping.

Indee,d that is what I planned to do first. One nice property is that it would work well with the zigzaging vertical lines indeed,, but then, I would still have to floodfill to check whether all tiles inside the convex hull are inside the area (by floodfilling?) to see whether it is convex,, no?

And it seems slower than just checking the border tiles and check their neighbors (especially since I already had to track them).