Mapper calculates positions on a Euclidean plane.
That is, coordinates are two dimensional, and the surface on which the points lie is not curved. Mapper is therefore unsuitable for large maps.
Mapper calculates the positions (coordinates) of places by regarding the measurements to be constraints on the coordinates, then satisfying all those constraints.
Mapper satisfies the constraints by defining an error function, which indicates the degree of dissatisfaction of the constraints, and finds the set of coordinates that minimize that function.
The definition of the error function takes into account the inaccuracy of the measurements.
For tracings from existing maps, Mapper creates a Delaunay triangulation of all the traced points. It creates an implied angle constraint for each vertex of each triangle in that triangulation. Each of those angle constraints constrains the angle at its vertex.
Mapper solves the multidimensional minimisation problem using the Fletcher, Reeves, Polak, Ribere algorithm, with Brent's method used for the line minimizations.
To compute the Delaunay triangulation, Mapper uses the robust incremental algorithm due to Watson, which is ultimately based on the algorithm due to Guibas. This uses the circumcircle test to determine which existing triangles need to be removed, and uses a temporary list of the edges of those triangles, to simplify creation of the new triangles.
The error function is designed so that the function minimized by the line minimizations will be approximately a parabola, so Brent's method will converge quickly.
This documentation is still being written,
and is therefore incomplete.
$Revision: 6.5 $
$Date: 2002/07/06 15:38:34 $