Until the first high-altitude photographs were taken, the principal methods of cartography have been the same throughout the entire history.
If you are able to measure distances and angles, you have everything you need to map the world – this is the main focus of geodesy. Cartography then is just a trivial visual representation of geodetic data.
If you watch how the sun moves across the sky throughout the year, you will be able to see that the length of the sun’s path across the sky and the exact place where it rises and sets shifts as the months go by.
On the northern hemisphere, sun rises and sets at its northernmost point on the summer solstice (midsummer), and at its southernmost on the winter solstice. The equal point between these two extremes occurs at equinoxes, and if you connect the two opposite points on the horizon where the sun sets during the equinoxes, you can accurately determine the east-west axis.
The same thing applies to the celestial sphere. After observing it for a while it is very easy to come to a logical conclusion that it forms a sort of “sphere” that revolves around the earth, with its rotational axis fixed at Polaris, and the sun and the planets very slowly moving on trajectories close to the equator.
This has been of course widely known throughout the history.
One of the main problems of very early cartography was that using the Sun or the Moon to measure the fixed four cardinal directions (north south, west east) was unreliable, as their positions in the sky significantly changed throughout the year and varied as the latitude changed.
The margin of error could be massive if one did not know the precise time of the year and did not have a precise enough way to measure angles, he could stray up to 25 km to the side from the intended target 100 km away.
However, the point at the horizon that is intersected by the celestial equator (stars that move the fastest during the night) is the same at any latitude, and if we know some of the constellations and stars that are very close to the equator, we can measure east and west with utmost accuracy. The most important of such stars is Mintaka, the uppermost star of the Orion’s belt. If one flew around the earth at the equator, basing his direction only by the position of Mintaka, he would never stray more than 31 km away from the equator. To determine where the north is, just find the point of horizon closest to the Polaris.
To measure more precise angles, you can either use lines that have been drawn in equal distances on a circular hoop or a semi-circular curved stick, or even a more precise instrument, such as this octant:
Of course, you also have to measure the distances between different landmarks and points on the coastline to make a maps. On the coasts of seas, lakes and rivers, you could simply aim to one direction and count your steps, trying not to deviate as much from the straight line, writing down the angular directions of every 100, 500, 1000 or more steps. Drawing an accurate coastline on mid-size maps of a tropical region and small maps of temperate regions is then trivial – draw a grid of small squares, mark your starting point, draw a continuous segmented line throughout the grid, with one segment being the fixed amount of steps you walked in one fixed direction.
Though most people did not really need maps when traveling on foot or horseback, as they usually followed already well-known paths and roads, cartography was extremely useful in the field of sea travel, as there were often no orientation points for thousands of miles and one could get lost very easily if he did not know how to determine his position with enough accuracy. Same process as when mapping land areas applies when measuring the length and relative angle of a distance traveled marine vessel, however, it is much more difficult to do it accurately, therefore distortions happen easily.
Mapping land regions from within was exceptionally accurate even in ancient times mainly because one could determine walking distances with a very high degree of accuracy. It was also often possible to create a very detailed and accurate map of more than a hundred square miles of land in a very short time just by climbing on a mountain of a decent height and looking around. This map of Europe was drawn in 200 AD by Ptolemy, and similar accuracies were not achieved in medieval Europe until about 14th century.
However, on the open sea, there are no discernible landforms one could peg his location to, and therefore determining the location of a ship on a latitude and longitude grid was always the only way to accurely estimate the distances between different continents and archipelagos. And this is difficult. So difficult, in fact, that it wasn’t until 1762 when the longitude relative to the Prime Meridian could finally be measured for the first time within a margin of error of 1 arc minute (±1 nautical mile), using a state-of-art chronometer H4, manufactured by John Harrison, who received an 18th century equivalent of a Nobel Prize because of it. However, these clocks remained quite expensive for a long time, and decreased below the sum of the annual wages of a skilled worker few years after Napoleon was exiled to St.Helena.
Until then, majority of sailors used the much less accurate method based on measuring the angles of the moon and various stars, and comparing them to values in a large astronomical almanac, determining the time at the Prime Meridian and longitudinal distance relative to it.
World maps only started to be very similar in their accuracy to those we hang on our walls in mid 19th century, however, it took well into the 20th century until the polar regions were finally thoroughly explored, with the last major blank spot being only filled in 1932, when the coastlines of the North Land Archipelago were finally charted.