Where would you start in re-making this map?

[jtougas]

In Photoshop there is a command (Select -> Color Range) that lets you select areas of your image by color. I would use this to select each area of color in turn and then fill that area in a new, blank layer. Then I'd go back in and fill any holes, filling any areas covered by "higher" terrain - e.g. so that green took up the entire area of the landmass. The result would be a stack of layers with a solid fill for each color in the map. This would serve as my base layer as I built up the new map, the main piece of this being the green layer that contained the entirety of my coastline.

I'm not sure if Gimp has this feature but I imagine it does. If not you can certainly use the "magic wand" tool and make multiple selections of each non-connected area of each color and do the same thing...it'll just take a bit longer.

Hope it helps.
M

As a matter fact there is a similar tool in GIMP under the magic wand tool options