Нужно быстро отрисовывать, менять цвет областей и определять их по клику на политическую карту.
Нашел нужную карту (карта Европы на июль 1914 с мелкими административными единицами) в растре, но так и не смог ее нормально распарсить.

Интересует, как это делается правильно. Хотелось бы получить что-то вроде вот этого.
Вариант «один цвет — одна область» (как в КГеографии, например) не подходит из-за большого количества областей и нечеткости их границ.

А нужный формат - это какой? В зависимости от задачи (и ее бюджета) можно использовать готовые решения. Скажем, есть библиотеки COM-объектов у ArcGIS и MapInfo (и других тоже, наверняка). Но они денег стоят. К ним же обычно прилагается ряд карт типа политической карты мира и прочее по мелочи. Наверное, можно найти и бесплатные библиотеки объектов. Для этого нужно порыться на форумах ГИС-комьюнити, их довольно много.
Но можно и самому, если запросы невеликию Определить с входным форматом сначала. Например, довольно просто читается SHP - бинарные, без особых наворотов, и карт в этом формате много.
Что касается технической стороны вопроса, то область (страна) - это просто полигон. Рисуешь полигон с заливкой и все. Определение "попал\не попал" - геометрическая задача "точка внутри полигона". Тоже не бог весть что.

Ну дык а откуда эти просто многоугольники взять? Карта-то в растре. Для этого надо перегнать из растра в этот нужный формат. То же относится и к .shp, как я понимаю.

Проблема вобщем-то заключается в растровости карты (пока что, о крайней мере).

Растровую карту ты можешь отрисовать только в том виде, в котором она изщначально нарисована, это ведь просто картинка.

Если хочешь серьезно заниматься растровой картографией, то используй Ozf2 формат. Практически все растровый карты идут в нем.

Насколько я знаю, в реальных ГИС идет наложение растровых и векторных слоев.