[lch]

Oh, you don't want the cells to be the finished provinces, okay, you're free to do that. Otherwise I'd assume that you get strange effects because I'd assume that the game interprets the provinces as being voronoi cells, so that mouse-clicks on the map can be efficiently calculated to the province they're meant for, by only saving and using one point per province instead of a whole polygon.

I still guess there's quite alot of good software around, but either you'll have to program the stuff yourself or use some library which does tons of other algorithmic geometry stuff aswell (like CGAL), yeah.