Jump to content
  • Advertisement

How to determine whether a region of a tiled hexmap is convex?

This topic is 530 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Edited by Galdred

Share this post

Link to post
Share on other sites


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




Edited by Galdred

Share this post

Link to post
Share on other sites

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

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!