Library of Congress holds conference on origins of portolan charts

The Arabs at the time had preserved a good portion of the scientific researches of the Ptolemaic Greeks, who were able to determine latitude (and I think longitude somewhat with many astronomical observations over time), so the relative locations of some key ports may have filtered out to some European cartographers at the time. The ability to observe latitude was possibly seeing limited re-discovery in Europe through Arab sources. For sure by the early 15th century Portuguese navigators could easily observe latitude.

But I believe these maps were created through dead reckoning. http://en.wikipedia.org/wiki/Dead_reckoning William Clark created a meticulously detailed highly accurate map of the Missouri, Snake, and Columbia rivers through dead reckoning, with the aid only of compass and sextant for latitude. (Lewis & Clark made some detailed observations for longitude, but the calculations were not performed until after the expedition was over and had nothing to do with Clark's map.)

I'll bet these maps originally had nothing to do with normal navigation (i.e. for commerce) accurate maps were for a long time military intelligence assets.

Great Britain employed a network of spies employing dead reckoning techniques to map out areas of south central Asia the British did not have access to (for military/intelligence purposes). Rudyard Kipling's novel Kim deals with this historical episode.