How to Compute Minkowski, Euclidean and CityBlock Distance in C++?

Given a number of coordinates (could be any dimensions, but for simplicity we use 2 dimension X/Y coordinates for demonstration), you can get the ‘central’ point by averaging all coordinates:

where n is the number of X/Y points. The C/C++ code is simple as the formula:

1
2
3
4
5
6
7
8

void GetXY(double *x, double *y, int n, double *ax, double *ay) {    
    ax = 0;
    ay = 0;
    for (int i = 0; i < n; i ++) {
        ax += (x[i] / n);
        ay += (y[i] / n);
    }
}

void GetXY(double *x, double *y, int n, double *ax, double *ay) {    
    ax = 0;
    ay = 0;
    for (int i = 0; i < n; i ++) {
        ax += (x[i] / n);
        ay += (y[i] / n);
    }
}

In the machine learning K-means algorithm where the 'distance' is required before the candidate cluttering point is moved to the 'central' point. To compute the distance, wen can use following three methods: Minkowski, Euclidean and CityBlock Distance.

Minkowski Distance

The Minkowski Distance can be computed by the following formula, the parameter can be arbitary.

So, translating into C/C++ code with help of this easiest power function:

1
2
3
4
5
6
7

double GetMinkowskiDistance(double *x, double *y, int n, double r) {
    double sum = 0;
    for (int i = 0; i < n; i ++) {
        sum += power(x[i] - y[i], r);
    }
    return power(sum, 1.0 / r);
}

double GetMinkowskiDistance(double *x, double *y, int n, double r) {
    double sum = 0;
    for (int i = 0; i < n; i ++) {
        sum += power(x[i] - y[i], r);
    }
    return power(sum, 1.0 / r);
}

Euclidean Distance

Euclidean Distance is the case when .

CityBlock Distance

CityBlock Distance is the case when .

Other Distances Formula

When approaches infinity, we obtain the Chebyshev distance. If you visualize all these methods with different value of , you could see that how the 'central' point is approached.

distance-of-minkowski-distance

--EOF (The Ultimate Computing & Technology Blog) --