장난감 연구소
[SQL] 위도와 경도를 사용하여 가까운 지점 찾기 본문
익힌 내용을 나중에 사용하기 위해 정리한 글로 부정확한 내용이 있을 수 있습니다.
쿼리
프로젝트를 진행하면서 자신과 가까이 있는 지점들을 검색하는 기능이 필요했다. 데이터베이스에 아래와 같이 모든 지점들의 위도와 경도를 실수 형태로 가지고 있다. 이때 한 지점과의 직선 거리가 일정 값 이하인 지점들을 어떻게 찾을 수 있을까?
한 지점과 모든 지점의 거리를 계산해서 SELECT 하려면, 아래와 같은 쿼리를 사용하면 된다. (MySQL로 테스트됨.)
SELECT
id, description,
(
6371 *
acos(
cos(radians(36.628486474734 /* 중앙도서관의 위도 */)) *
cos(radians(latitude)) *
cos(radians(longitude) -
radians(127.4574415007155 /* 중앙도서관의 경도 */)) +
sin(radians(36.628486474734 /* 중앙도서관의 위도 */)) *
sin(radians(latitude)))
) AS distance
FROM TABLE_NAME
HAVING distance < 1 /* 최대 검색 거리, 1km */
ORDER BY distance;
위 쿼리는 중앙도서관을 중심으로 모든 지점들의 직선 거리를 계산하여, 거리가 1km 이하인 모든 지점을 반환해준다. 6371은 지구 반지름의 상수 값이고, 중심점의 위도와 경도, 최대 검색 거리를 수정하여 사용할 수 있다.
원리
하버사인 공식 (Haversine formula)
지구는 구 형태이기 때문에 지도 위에서 두 점 사이 직선을 그려서는 정확한 두 점 사이의 거리를 구할 수 없다. 하버사인 공식은 구면 위의 두 점의 위도와 경도가 주어졌을 때, 구면 거리를 구할 때 사용된다.
$\theta$를 두 점을 잇는 호의 중심각(라디안), $r$을 지구 반지름, $d$를 두 점의 구면 거리(호의 길이)라고 할 때, 부채꼴이므로 각각은 아래와 같은 관계를 가진다.
$$ \theta = \dfrac{d}{r} $$
하버사인 공식는 위도($\varphi$로 표현)와 경도($\lambda$로 표현)를 사용하여 $\theta$를 하버사인 함수에 넣은 값 $hav(\theta)$를 계산할 수 있게 해준다.
$$ hav(\theta) = hav(\varphi_2-\varphi_1) + cos(\varphi_1)cos(\varphi_2)hav(\lambda_2-\lambda_1) $$
한 점의 위도와 경도를 $\varphi_1$, $\lambda_1$ 그리고 나머지 점의 위도와 경도를 $\varphi_2$, $\lambda_2$라고 할때 $hav(\theta)$는 위와 같다.
그리고 하버사인 함수는 아래와 같은 식을 가진다.
$$ hav(\theta)=\sin ^{2}\left({\frac {\theta }{2}}\right)={\frac {1-\cos(\theta )}{2}} $$
$d$를 구하기 위해 맨 위의 관계에서 $r$을 넘기고, $\theta$를 $archav(hav(\theta))$로 바꾼 후, $hav(\theta)$를 $h$라 하면 아래 식과 같다. 또, 하버사인 함수의 식을 변형하면 $ archav(\theta)=2\ arcsin(\sqrt{\theta}) $이므로 $ archav(h) $를 $ 2\ arcsin(\sqrt{h}) $로 바꿀 수 있다.
$$ hav(\theta) = r\ archav(h) = 2r\ arcsin(\sqrt{h}) $$
더 상세하게 아래와 같이 풀어 삼각함수에 위도와 경도를 대입하면 거리 $d$를 구할 수 있다.
$$ {\displaystyle {\begin{aligned}d&=2r\arcsin \left({\sqrt {\operatorname {hav} (\varphi _{2}-\varphi _{1})+\cos\varphi_1\cos\varphi_2\cdot \operatorname {hav} (\lambda _{2}-\lambda _{1})}}\right)\\&=2r\arcsin \left({\sqrt {\sin ^{2}\left({\frac {\varphi _{2}-\varphi _{1}}{2}}\right)+\cos \varphi _{1}\cdot \cos \varphi _{2}\cdot \sin ^{2}\left({\frac {\lambda _{2}-\lambda _{1}}{2}}\right)}}\right)\end{aligned}}} $$
구면 코사인 법칙 (Spherical Law of Cosines)
위의 하버사인 공식을 사용해서 두 지점 간의 거리를 계산할 수 있지만, 구면 코사인 법칙을 사용하여 거리 $d$를 구하는 것이 정확도가 좋다고 한다. 1
그림과 같이 구면 위 세 점 $u$와 $v$, $w$가 주어지고, uv의 길이가 $a$, uw의 길이가 $b$, vw의 길이가 $c$, vuw가 이루는 각을 $C$라 하자. 구의 반지름의 길이가 1이라면 $a$, $b$, $c$는 두 점이 구의 중심점과 만드는 부채꼴의 중심각과 같다.
이때 구면 코사인 법칙을 통해 아래 식이 성립한다.
$$ \cos c=\cos a\cos b+\sin a\sin b\cos C $$
다시 위도와 경도 문제로 돌아가자. 위 그림과 같이 반지름이 1인 구에서, 점 A와 점 B 사이의 구면 거리(이자 구의 중심과 이루는 부채꼴의 중심각) $\theta$를 구하자. 구의 북극점을 N으로 놓고, 세 점 A, B, N에 대해 구면 코사인 법칙을 사용할 것이다.
다시 말하지만 구의 반지름을 1 이라고 가정하면, 부채꼴의 중심각과 호의 길이가 같다. 그러므로 점 A의 위도 $\varphi_A$에 대해 $a=\frac{\pi}{2}-\varphi_A$이고 점 B의 위도 $\varphi_B$에 대해 $b=\frac{\pi}{2}-\varphi_B$이다. 또, 두 점의 경도 $\lambda_A$, $\lambda_B$애 대해 $C=\lambda_B-\lambda_A$와 같다. 이를 구면 코사인 법칙에 대입하면 아래와 같다.
$$ {\begin{aligned} \cos(\theta)&=\cos a \cos b + \sin a \sin b cos C \\ &=\cos(\frac{\pi}{2} - \varphi_A)\cos(\frac{\pi}{2} - \varphi_B) + \sin(\frac{\pi}{2} - \varphi_A)\sin(\frac{\pi}{2} - \varphi_B) \cos(\lambda_B - \lambda_A) \\ &=\sin(\varphi_A)\sin(\varphi_B) + \cos(\varphi_A)\cos(\varphi_B) \cos(\lambda_B - \lambda_A) \end{aligned}} $$
코사인을 역함수로 바꿔 처음 나온 수식인 부채꼴의 관계에 $\theta$를 대입하면 아래와 같다.
$$ {\begin{aligned} d &= r \cdot \theta \\ &= r \cdot \arccos(\sin(\varphi_A)\sin(\varphi_B) + \cos(\varphi_A)\cos(\varphi_B) \cos(\lambda_B - \lambda_A)) \end{aligned}} $$
처음 제시된 SQL 쿼리는 위 식으로 두 지점 간의 거리를 계산한다.
참고
MySQL에서는 POINT 자료형과 ST_DISTANCE_SPHERE 함수를 사용하면 쉽게 거리를 구할 수 있다.
SELECT
id, name, ST_DISTANCE_SPHERE(location, POINT(127.4574415007155, 36.628486474734)) AS distance
FROM TABLE_NAME /* POINT(경도, 위도) */
HAVING DISTANCE < 50 * 1000
ORDER BY distance;
'개발' 카테고리의 다른 글
[Git] Semantic Commit Messages (0) | 2024.01.12 |
---|---|
Git 레포지토리에 파일은 남기고 변경 추적만 중지하기 (0) | 2021.01.01 |