DISTANCE_TO_POSITION
Estimate city positions from distance tables.

DISTANCE_TO_POSITION is a FORTRAN90 program which estimates the positions of cities given a city-to-city distance table.

In 2D, the problem is singular. In particular, the position of one city is completely arbitrary, and one component of a second city is completely arbitrary (and a third city's position can be "flipped" about the line connecting cities one and two). To remove some of this singularity, the program assigns city #1 the position (0,0) and city #2 is given a 0 Y coordinate.

In N-dimensional space, a similar set of constraints must be placed on the first N cities, or the least squares solver is likely to fail. (That is, we specify all N components of the first city to be 0, N-1 components of the second one, and so on, up to the N-th city which has a single 0 component).

The computations carried out by this program assume that the cities lie on a plane. If the distance data is for international cities, the effect of spherical geometry may make the planar approximation very bad.

Once the nonlinear least squares problem is set up, the routine UNCMIN from the NMS software package is called to compute a solution.

Usage:

distance_to_position distance.txt

• distance.txt is the distance information

Languages:

DISTANCE_TO_POSITION is available in a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

CITIES, a dataset directory which contains sets of information about cities and the distances between them;

CITIES, a FORTRAN90 library which handles various problems associated with a set of "cities" on a map.

DISTANCE_TO_POSITION_SPHERE, a MATLAB program which estimates the positions of cities on a sphere (such as the earth) based on a city-to-city distance table.

LAU_NP, a FORTRAN90 library which implements heuristic algorithms for various NP-hard combinatorial problems.

NMS, a FORTRAN90 library which includes a wide variety of numerical software.

PARTIAL_DIGEST, a FORTRAN90 library which solves the partial digest problem.

Source Code:

• distance_to_position.f90, the source code.

Examples and Tests:

• grid04_xy.txt, positions of 4 points on a grid.
• grid04_dist.txt, the distance table for the points.
• grid04_dist.coord.txt, the estimated positions of the points, based on the distance table.

List of Routines:

• DISTANCE_MODULE is a module for the distance matrix.
• MAIN is the main program for DISTANCE_TO_POSITION.
• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• COMPUTE_POSITION_FROM_DISTANCE computes positions from a distance matrix.
• FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
• FILE_NAME_EXT_GET determines the "extension" of a file name.
• FILE_NAME_EXT_SWAP replaces the current "extension" of a file name.
• FILE_ROW_COUNT counts the number of row records in a file.
• GET_UNIT returns a free FORTRAN unit number.
• MAP is the function to be minimized for city positions.
• POSITION_TO_DISTANCE creates a distance matrix from positions.
• R8MAT_DATA_READ reads data from an R8MAT file.
• R8MAT_HEADER_READ reads the header from an R8MAT file.
• R8MAT_PRINT_SOME prints some of an R8MAT.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• R8MAT_WRITE writes an R8MAT file.
• R8VEC_UNIFORM_01 returns a unit pseudorandom R8VEC.
• S_BLANK_DELETE removes blanks from a string, left justifying the remainder.
• S_INDEX_LAST_C finds the LAST occurrence of a given character.
• S_TO_R8 reads an R8 value from a string.
• S_TO_R8VEC reads an R8VEC from a string.
• S_WORD_COUNT counts the number of "words" in a string.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the FORTRAN90 source codes.