If you are designing your game to use hexagon tiles, then it might not be bad to check how Widelands (Settlers 2 clone) map is gnerated. While Widelands use triangles (vertex approach) for map representation you can always create hexagon tiles by combining 6 triangles.

On link below you can see a bit more information about how it is done, including the way for calculating regions. I hoe it would come in handy to you:
http://widelands.svn.sourceforge.net...ry/index.xhtml