Maps and Legends
This is exactly like the people who say "I can't imagine building the Pyramids without steam shovels" and therefore conclude they must have been built using alien anti-gravity rays, instead of with a million drafted peasants, a multi-decade contracting process, and very lax safety codes.
I suspect the portolans are in fact medieval "big data." The portolans (1290) postdate by a century or so the introduction of the compass to Europe (~1180). Lots of individual compass-bearings from a given city to its nearby neighbors, repeated for every city in which you have contacts, equals true compass bearings for the whole map, which is a kind of brute-force Mercator. The portolans probably came out of the Jewish intellectual centers in the Balearic Islands (Pisa, where the first portolan we know of surfaced, had a thriving Jewish community in the 12-13th c); it would not amaze me at all if they began as the proprietary charts assembled over decades of observations by Jewish merchants. That also explains why the portolans suddenly go to crap north of the Thames and east of the Weser.