大圏距離（Great Circle Distance）公式を使って近くのタクシーを検索するC++プログラム

本記事では、大圏距離（Great Circle Distance）公式を使用して、ユーザーの位置から約50km以内に存在するタクシー（配車車両）を検索するC++プログラムについて解説します。

問題の概要

ここでは、配車を必要としているユーザーの氏名と座標情報、および利用可能なすべてのタクシーの座標情報が記録されたJSONファイルが与えられていると仮定します。

この問題を解くための手順は以下の通りです。

• まず、GPS座標（緯度・経度）を double 型の数値に変換します。
• 次に、その数値を「度」から「ラジアン」へ変換します。
• 最後に、大圏距離公式を適用し、ユーザーの現在地から50km以内にあるタクシーを特定します。

なお、入力データの量が非常に多いため、プログラムではJSONファイルを入力として受け取り、結果も別のJSONファイルに出力する設計になっています。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define pi 3.14159265358979323
#define earth_radius 6371.0
// ユーザーの座標を定義
#define latitude1d 12.9611159
#define longitude1d 77.6362214
ifstream users ("input.access_file");
ofstream out ("output.access_file");
// 度をラジアンに変換
double to_radian(double degree) {
    return ( degree * (pi/180));
}
// 距離を計算
double cal_distance(double latitude2d, double longitude2d) {
    double lat1, lon1, lat2, lon2, diff_lon, great_circle;
    lat1 = to_radian(latitude1d);
    lon1 = to_radian(longitude1d);
    lat2 = to_radian(latitude2d);
    lon2 = to_radian(longitude2d);
    diff_lon = lon2 - lon1;
    great_circle = acos( sin(lat1) * sin(lat2) + cos(lat1) *cos(lat2) * cos(diff_lon) );
    return (earth_radius * great_circle);
}
// JSONファイルへアクセスするための構造体
struct access_file {
    long long int user_length, i, j, x, y, m, n, f, friends,id[100000];
    char latitude_string[1000], longitude_string[1000], id_string[1000], name[1000];
    double latitude2d, longitude2d;
    string line;
    // 距離の値をチェック
    void check_distance() {
        if (cal_distance(latitude2d, longitude2d) <=50.0000) {
            id[i] = atoll(id_string);
            i++;
            out << "{\"User_id\": " << id[i - 1] << ", \"Name\": " << name << "}" << endl;
        }
    }
    void file_parser() {
        if (users.is_open()) {
            while (getline(users, line)) {
                f = 0; x = 0; y = 0; friends = 0; m = 0, n = 0;
                user_length = line.size();
                for (j = 0; j < user_length; j++) {
                    if (line[j] == '"')
                        f++;
                    else if (line[j] == ':')
                        friends++;
                    if (f == 3) {
                        j++;
                        while (line[j] != '"') {
                            latitude_string[x] = line[j];
                            x++; j++;
                        }
                        j--; latitude_string[x] = '\0';
                    }
                    else if (f == 13) {
                        j++;
                        while (line[j] != '"') {
                            longitude_string[y] = line[j];
                            y++; j++;
                        }
                        j--; longitude_string[y] = '\0';
                    }
                    if (friends == 2) {
                        j += 2;
                        while (line[j] != ',') {
                            id_string[m] = line[j];
                            m++; j++;
                        }
                        j--; id_string[m] = '\0';
                        friends++;
                    }
                    else if (friends == 4) {
                        j += 2;
                        while (line[j] != ',') {
                            name[n] = line[j];
                            n++; j++;
                        }
                        j--; name[n] = '\0';
                        friends++; f += 2;
                    }
                }
                // 文字列を浮動小数点数に変換
                latitude2d = atof(latitude_string);
                longitude2d = atof(longitude_string);
                check_distance();
            }
        }
        // 入力ファイルを閉じる
        users.close();
        // 出力ファイルを閉じる
        out.close();
    }
};
int main() {
    access_file object;
    object.file_parser();
    return 0;
}

実行結果

（ソースコードおよび input.json ファイルと同じ場所に output.json という名前のファイルが生成されます。）

解説

このプログラムのポイントは以下の通りです。

• 大圏距離公式： 地球を完全な球体とみなし、球面上の2点間の最短距離（大円に沿った距離）を求める公式です。緯度・経度から2点間の距離をキロメートル単位で算出できます。
• 地球半径： 定数 earth_radius には6371.0kmを採用しており、これが平均的な地球の半径です。
• JSONパーサー： 外部ライブラリに依存せず、行単位で文字を読み取り、引用符やコロンの出現回数をカウントすることで、ID・氏名・緯度・経度の各フィールドを抽出する独自の簡易パーサーを実装しています。
• 距離判定： 各タクシーの座標について計算した距離が50.0000km以下であれば、そのタクシーのIDと氏名を出力ファイルに書き込みます。

このように、大圏距離公式はタクシー配車アプリのような「現在地付近の車両を検索する」機能を実装する際に非常に有用なアルゴリズムです。