Food for thought. I've had very good results with FastPixelPerfect collision detection. With this, however, your challenge will change to: how do I break up the territories neatly, make them into images (sprites), and then puzzle their bounding rects together just as neatly.
http://www.pygame.org/wiki/FastPixelPerfect?parent=CookBook Gumm
