First, a spot of background science. The Longitude Problem is exactly identical to the problem of establishing simultaneity on widely separated locations on the Earth's surface, and both prerequisite the existence of a reliable estimate of the Earth's diameter. Certainly Eratosthenes calculated the Earth's diameter in the 3rd Century BC, and other civilizations may have done so by roughly the same time period. However the problem of establishing simultaneity is more difficult, and comes in two flavours.
Longitude is calculated by comparing the elevation of an astronomical object to the pre-calculated (or observed) elevation of the same object at a reference location at the precisely simultaneous moment in time. Everything in the sky rotates once around that vast celestial sphere every 24 hours, so the more precisely one can establish simultaneity the more precise one's measurement of longitude will be.
The problem is simpler when the goal is cartography - calculating the longitude, and thus precise location, of a given spot on the globe exactly once. In this case one can use the occurrence of a predicted astronomical event as the definition of simultaneity. Surveying teams are organized to travel to the specified locales well in advance of the event, and providing the skies are clear on the given day the necessary observations are made. Once the surveying teams return the results are tabulated and the maps drawn.
The more difficult problem, and the one that confounded the British Admiralty into establishing the Longitude Prize, is of establishing the location of a moving vessel out of sight of land at whatever time the skies happened to be clear, wherever and whenever that was. One could not halt a sailing vessel in the middle of the ocean and wait for a pre-calculated event that occurred once or twice a month at best. It was necessary to resort to Dead Reckoning, a well-established and remarkably accurate science by the 17th and 18th centuries, which provided locations within one or two dozen miles on voyages thousands of miles long. When the goal was simply to voyage out and return home, this was more than adequate. However when the need is to avoid reefs of only a few hundred yards extent, being off by a few miles all too often results in foundering instead of sailing safely by.
The accuracy of dead reckoning can be judged by the quality of 16th and 17th century maps, reproductions of which are readily available all over the web. Don't be misled by the contours of western North America - those are due to the wanderings of the North Geomagnetic Pole.