The world editor of Chaos Chronicles features automatic (p0lygonal) navmesh generation. We make use of that navigation mesh to compute a game hexagon board for combats. To do this we basically just have to lay a 2d grid of potential board fields on the navmesh polygons, and use navmesh raycasts to test in which directions they should be connected to their neighbours.
We had a prototype up and running rather quickly and from there it was a long way of improving data structures and implementing algorithms to make use of the board data, i.e. path search, flooding with weighing of fields, etc. and to get the board (including combat animations and stuff) neatly visualized (neither being overly prominent, nor to technical, nor too hard to see and so on).
Hexagons were definitely the right choice for our game world, as you can just build levels looking as naturally as you expect them to, and the hexes will mostly fit themselves into it like a charm.
