Uh, I am note sure what you mean with "Sort the polygons spatially in some way"? You mean drawing polygons one by one? This might be what they do cause there is a file that represents rectangles that define extreme borders of the province in question (left, top, bottom, right). In this way they know where to draw the province although I have not seen single province images. They might acquire them from the big map or somehow?

It's a matter of performance. You don't want to try to draw every province, army, arrow, etc every frame. Instead, you want to draw what the user can see. You're already on the right track: calculate axis-aligned bounding boxes and then sort them with some simple algorithm. Then, you can query your sorted bounding boxes to see which polygons lie in an area. You'll end up using this for a lot of things: for instance, in addition to rendering you could also use it to narrow down possibilities for which province was clicked, or have the AI use it to determine how many hostile armies are within range of a given province, and so on.

A really simple way to do this might be a balanced binary search tree sorted by the x or y axis. There are lots of tree variants though. Search "spatial partitioning" for more ideas.

I cant imagine an editor with indenpendetly drawn provinces? How do you control their precise position on map?[/quote]
You use your editor* (that you'll write to work with the game) to place provinces wherever you want. You would have two files: 1 is the map, which could be just a simple BMP. The second would define vertices that make up the provinces and possibly contain any particular details (for instance, starting points or region wealth or city locations, whatever features your game has) that can be changed via the editor.

* I've never used gleed2d so I don't know if it'll do what you want or not, but if it does that could save you a considerable amount of time.

All adjacent provinces are kept in a file similar to the one I described for hit testing. There is a province Id, followed by ids of adjacent provinces so its easy to know where you can go.[/quote]
That works. You could have the editor define that for you, or have the game engine figure it out while loading the map to make things a little more automatic. Either way.

I am not sure if Python has such library, I am even not sure can it be done in Python? But I need some more info about substance of working with maps like this one.
[/quote]
You could probably come up with your own solution pretty easily. I was getting ahead of myself and thinking about the editor automatically filing in oceans and unused areas, or randomly generating a set of provinces on any given map. A way to define polygons and a function to check if a point is inside any given polygon is really all you need or want at this point.