Paris Map 1734 - 2D interpolation on an irregular grid

From the Wikipedia article "Turgot Map of Paris":

In 1734 Michel-Étienne Turgot, chief of the municipality of Paris as provost of merchants, decided to promote the reputation of Paris for Parisian, provincial or foreign elites by implementing a new map of the city. He asked Louis Bretez, member of the Royal Academy of Painting and Sculpture and professor of perspective, to draw up the plan of Paris and its suburbs.

http://upload.wikimedia.org/wikipedi..._-_Kyoto_U.jpg

Detail from maps 11 & 15 with the Louvre

In the eighteenth century, the trend was to abandon portraits of cities (inherited from the Renaissance) for a geometric plan, more technical and mathematical. But the plan de Turgot goes against this trend, by choosing the system of *perspective cavaliere*: two buildings of the same size are represented by two drawings of the same size, whether the buildings are close or distant.

*** end Wikipedia quote ***

The resulting map is both fascinating and beautiful, but unfortunately not strictly to scale due to its unusual perspective and the artistic license of the mapper. It is nonlinear wrt the distance between two points, plus the coordinate system rotates somewhat from place to place.

So... the problem to be solved is how to find an accurate geolocation of any point on the map. As many of the landmarks on the map still exist in modern Paris it is possible to pin an accurate location to many points on the map. The result is an irrgular grid of location data from which to estimate the location of any point on the map. This must be accomplished in real time with the limited computational resources of an iPhone. If interpolation directly from the irregular grid is too computationally intensive, it would be acceptable to prebuild a regular grid of location data (via interpolation) and interpolate from that in real time.

- What is the best approach to this problem?
- Is there an approach that takes advantage of the relatively slow rate of change of the distortion field across the map?
- A public domain C implementation of the algorithm is a big plus.

I am far from knowledgable in the relevant math, so I won't be in the least insulted if it turns out I'm just ignorant of an obvious answer. I've looked at descriptions of various methods of 2D interpolation on an irregular grid but am not able to determine with any confidence which of the many approaches would best apply to this problem.

Thanks in advance.