안녕하세요 행복이님들~ 채니챈이에요🙂 오늘은 우리 서비스의 핵심 기능인 중간 지점 찾기 기능을 위한 알고리즘을 알아보았습니다!! 두 점 사이의 거리는 중점 정리를 사용하면 쉽게 구할 수 있겠지만 참여자가 3명 이상이 되면 다른 방법이 필요하게 되는데요. 이를 구현하기 위해 어떤 방법을 사용하면 좋을지 확인해보겠습니다! 물론 제가 알아보지 못한 더 많은 알고리즘이 있을 수 있으니 혹시 찾게 되시면 자유롭게 추가해주시면 감사하겠습니다🙇♀️
우선 제가 (독단적으로..) 생각해본 방법은 세 명 이상의 참여자들의 위치를 점으로 생각하고 이 모두를 꼭짓점으로 하는 다각형을 그립니다. 그리고 이 다각형의 무게중심을 찾으면 그것이 중점이 되겠죠! (가물가물한 무게중심..)
이 방법을 구현하기 위한 알고리즘이 있을까 조사하는 과정에서 그라함 스캔 알고리즘이라는 것을 알게 되었습니다. 그라함 스캔 알고리즘과 이어서 사용할 방법의 구체적인 내용에 대해서는 밑에서 자세하게 이야기 하기로 하고 가장 먼저, 전반적인 개요를 정리해보겠습니다. (아직 수빙수의 결재를 받진 못했습니다..😮)
가장 먼저 생각한 방법은 이렇습니다.
1. 모든 참여자를 꼭짓점으로 하는 가장 작은 다각형을 만든다
2. 1에서 만든 다각형의 무게중심을 찾는다
3. 이 무게중심과 가까운 지하철 역을 찾는다그런데 다른 참여자들에 비해 중점에서 가까운 사용자가 포함되게 되면 찌그러진 다각형, 즉 오목다각형이 만들어지겠죠. 아래의 concave 그림처럼 말입니다. 그럼 무게중심을 찾을 때 이 친구를 포함한 경우와 포함하지 않은 경우 큰 차이가 없을 것 같다는 생각이 들었습니다. 수학적 증명은 좀더 찾아봐야겠지만 이를 통해 계산을 조금이라도 줄일 수 있다면 좋을 것 같다는 생각이 들었어요. 그래서 찾게 된 것이 그라함 스캔 알고리즘입니다.
1. 그라함 스캔 알고리즘으로 외곽에 있는 참여자를 꼭짓점으로 하는 가장 작은 다각형을 만든다
2. 1에서 만든 다각형의 무게중심을 찾는다
3. 이 무게중심과 가까운 지하철 역을 찾는다그라함 스캔(Graham Scan) 알고리즘
그라함 스캔 알고리즘은 2차원 평면 상에 임의의 점들이 있을 때 그 점 중 일부를 포함하는 다각형을 만들고 나머지 점을 다각형 내부에 포함시키는 알고리즘입니다. 시간복잡도는 O(nlogn)이라고 하네요. 다시 말해, 점들의 외각선을 연결하는 꼭지점들을 찾아낼 때 사용하는 알고리즘이지요.
클러스터링
이렇게 만든 참여자 다각형으로부터 중간 지점은 찾는 방법으로 클러스터링의 centroid를 사용하거나 아예 무게중심을 찾는 방법을 고려해보았습니다.
클러스터링은 점들을 그룹으로 나누는 것입니다. 그 중 k-means 클러스터링은 점들을 k개의 클러스터로 묶는 알고리즘인데 점들의 centroid 중심을 할당하고 거리계산을 통해 클러스터를 재할당하는 방식으로 구현됩니다. 만약 우리가 k=1이라고 군집을 하나만으로 설정한다면 이를 통해 구한 centroid가 중점이 되지 않을까 하는 생각이 들었습니다. 물론 무게중심을 구하는 방법으로 구현해볼 수도 있을 것 같습니다. 그래서 무게중심 찾는 법도 알아보니 오! 무게중심을 쉽게 구할 수 있는 파이썬 메서드가 있네요! 이걸 사용해봐도 좋을 것 같습니다 후후👼
from shapely.geometry import Polygon
P = Polygon([[0, 0], [1, 0], [1, 1], [0, 1]])
print(P.centroid)
#POINT (0.5 0.5)참고로 K-Means 클러스터링 구현에는 Lloyd 알고리즘이 가장 많이 이용된다고 하네요.
유클리디안 거리
자 그럼 무게중심을 구한 후 무게 중심에서 가까운, 즉 중간지점인 지하철 역은 어떻게 찾을 것이며, 지하철 역에서 참여자들의 거리는 어떻게 구할까요? 그리고 중간지점 지하철 역에서 상권들 사이의 거리는 어떤 방식으로 구하게 될까요? 가장 일반적인 거리 계산 방법인 유클리디안 거리 계산 방법을 사용할 예정입니다.
유클리디안 거리는 두 점 사이의 거리를 구할 때 많이 사용하는 방식으로 고등학교 때 계산해본 경험이 다들 있을 것 같네요..!! 이것으로 거리를 구하고 거리에 비례하게 시간을 계산하여 제공해주는 식으로 구현해보면 어떨까 싶습니다.
