이 글에서는 대권 거리(Great Circle Distance) 공식을 활용해 사용자 위치에서 약 50km 이내에 있는 택시를 찾아내는 C++ 프로그램을 소개합니다.
문제 정의
택시 호출 앱을 개발할 때 핵심이 되는 기능은 바로 '현재 위치에서 가까운 차량 찾기'입니다. 여기서는 다음과 같은 상황을 가정합니다.
승객의 이름과 GPS 좌표(위도, 경도), 그리고 현재 배차 가능한 모든 택시의 좌표가 담긴 JSON 파일이 하나 주어집니다. 우리가 해야 할 일은 이 데이터를 분석하여 승객으로부터 50km 이내에 있는 택시만 골라내는 것입니다.
해결 절차
전체적인 처리 흐름은 다음과 같습니다.
1. JSON 파일에서 읽어온 GPS 좌표를 double 타입 숫자로 변환합니다.
2. 도(degree) 단위의 좌표값을 라디안(radian)으로 변환합니다.
3. 대권 거리 공식에 대입하여 사용자와 각 택시 사이의 실제 거리를 계산합니다.
4. 계산 결과가 50km 이하인 택시만 최종 목록에 포함합니다.
참고로 입력 데이터의 양이 매우 많기 때문에, 이 프로그램은 JSON 파일을 직접 입력으로 받고 결과 역시 별도의 JSON 파일로 출력하도록 설계되었습니다.
대권 거리 공식이란?
대권 거리(Great Circle Distance)는 지구를 완전한 구(sphere)로 가정했을 때 구면 위의 두 점 사이의 최단 거리를 의미합니다. 두 지점의 위도(lat1, lat2)와 경도(lon1, lon2), 그리고 지구 반지름 R(약 6,371km)을 이용해 다음과 같이 계산할 수 있습니다.
d = R × arccos( sin(lat1) × sin(lat2) + cos(lat1) × cos(lat2) × cos(lon2 − lon1) )
GPS 좌표는 도 단위로 표현되지만 삼각함수는 라디안 값을 요구하기 때문에, 계산 전에 반드시 도 → 라디안 변환을 거쳐야 한다는 점에 유의하세요. 또한 acos 기반 공식은 부동소수점 오차로 인해 거리가 매우 먼 두 지점에서 불안정해질 수 있으므로, 실제 서비스에서는 수치 안정성이 더 좋은 하버사인(Haversine) 공식을 함께 고려하는 것이 좋습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
#define pi 3.14159265358979323
#define earth_radius 6371.0
//defining the user's coordinates
#define latitude1d 12.9611159
#define longitude1d 77.6362214
ifstream users ("input.access_file");
ofstream out ("output.access_file");
//converting degree to radian
double to_radian(double degree) {
return ( degree * (pi/180));
}
//to calculate the distance
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);
}
//creating structure to access JSON file
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;
//to check the value of distance
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;
}
}
//converting string to float
latitude2d = atof(latitude_string);
longitude2d = atof(longitude_string);
check_distance();
}
}
//closing input file
users.close();
//closing output file
out.close();
}
};
int main() {
access_file object;
object.file_parser();
return 0;
}
실행 결과
(코드와 input.json 파일이 저장된 동일한 위치에 output.json 파일이 생성됩니다.)