Hello, Geo-fence!
안녕하세요 라이더스개발팀 박민철 입니다.
BROS(Baemin Riders Operating System)에 Geo-fence를 도입한 경험을 적어보겠습니다.
(BROS는 라이더를 배차하고 음식을 픽업하여 고객에게 전달하는 서비스를 지원하는 배달 플랫폼 입니다.)
Geo-fence란?
‘geo-fencing’ 으로 불리기도 하는데, 지도위에 가상의 도형들의 영역을 말합니다.
[이런식으로 그리면 혼나요]
근데 왜 필요한거죠?
기존에는 지점(관제센터)의 행정동코드
기반으로 배달 가능 여부를 판단하였습니다.
고객의 행정동코드
와 지점의 배달 가능한 행정동코드
를 매핑하여, 배달 가능한 지점이 존재하면 주문을 생성할 수 있었습니다.
여기에서 1가지 같은 2개의 이슈가 발생합니다.
[경계선 주변 배달불가능]
첫 번째는 고객이 배달 가능 지역에 가까워도 특정 지점의 행정동코드
가 없으면, 배달할 수 없는 문제입니다. 경계선 근처에 거주하는 고객에게 서비스를 제공하지 못한 안타까움이 있습니다.
[움직일 기미가 안 보이는 라이더님]
두 번째는 배달 가능 지역내 일부 영역을 제외할 수 없는 문제입니다.
이 프로젝트가 진행되어야 하는 이유의 많은 지분을 차지하고 있습니다.
공원이나 오토바이가 진입하기 어려운 지역, 오랜 시간을 소요해야 하는 지역(타*팰리스는 보안 때문에 출입시간 소요가 많습니다.)을 피크타임에 유연하게 처리할 수 있도록 해야 합니다.
그래서 어떻게 했는데요?
먼저 Geo-fence를 사용하기 위해 네이버 지도 API 문서를 잘 읽었습니다.
그다음 BROS에서 지점별로 접수영역
과 차단영역
을 그리고 저장할 수 있도록 기능을 개발했습니다.
그리고 행정동코드
기반 로직에 접수영역
과 차단영역
을 추가로 판단하여 배달 가능 여부를 전달하도록 수정하였습니다.
[접수영역과 차단영역을 그려봅니다]
약간의 문제가 있습니다.
기존 시스템에서는 지점들의 배달 가능한 행정동코드
를 On/Off로 관리하고 있었습니다.
관리자가 접수영역
과 차단영역
을 적절하게 그릴 수 있도록 행정동의 정보를 Geo-fence로 같이 볼 수 있어야 했습니다.
그래서 통계청 통계지리정보서비스에서 제공하는 행정동 경계 파일을 기반으로 작성된 geojson 파일을 사용하여
행정동 영역을 저장하였습니다. ( github에 공유해주신 개발자님 감사합니다. )
하지만, 통계지리정보서비스에서 제공하는 코드는 7자리 행정구역분류코드
이고, 저희가 사용하는 코드는 10자리 행정표준코드관리시스템코드
이기 때문에 변환이 필요했습니다. ( 아 … 할많하않 )
통계분류 포털 홈페이지의 행정구역분류 엑셀 데이터를 다운받아 매핑을 할 수 있었습니다.
(이 삽질작업은 오픈 프로젝트인 우아한주소에 저장되어 있습니다.)
[행정동과 같이 접수영역과 차단영역을 그려봅니다]
마지막으로 로직을 수정합니다.
기존 로직에 행정동코드
포함 여부에 추가로 고객의 위치가 접수영역
안에 있는지 혹시 차단영역
안에 있는지 판단하는 기능을 추가하였습니다.
이렇게 간단하진 않지만, 대략 이런 느낌입니다.
...
boolean deliverable = ((행정동코드포함 || 접수영역안에위치함) && 차단영역안에없음);
...
끝.
더 들여다봅시다.
바쁘신 분들은 뒤로가기를 눌러주세요.
Geo-fence에서 생성한 도형 안에 점(Point)이 존재하는 여부를 JTS
(평면 기하학을 위한 기능을 제공하는 오픈소스 Java 라이브러리)를 사용했습니다.
Point.class와 Polygon.class은 Geometry.class를 상속받아 사용하고 있었으며, 적절해 보이는 within이라는 함수를 사용했습니다.
한번 테스트를 해봅니다.
[테스트통과는 언제나 기분이 좋아요]
궁금증이 하나 생깁니다. 영역의 경계선 위에 점(Point)이 있으면 어떨까요? 제대로 동작할까요?
점(Point)이 영역의 경계선에 있으면, 안에 있다고 판단하지 않습니다. 그렇군요.
문서를 읽어봅시다. (영어라서 문서를 먼저 안 읽…)
문서를 보면 contains, covers, coveredBy, equals … 그럴듯한 함수들이 있습니다.
앞서 사용한 within 함수를 살펴보면 DE-9IM
단어와, [T F F ] 표기가 있습니다.
잘 모르겠습니다. 그래서 검색을 해봤습니다.
DE-9IM?
*[DE-9IM
DE-9IM
은 두 도형의 내부, 경계, 외부의 총 9가지의 관계를 표현하며, 교집합에서 발생하는 도형의 Dimension(차원)을 행렬로 나타냅니다.
그림에서 보면 II(가장 왼쪽 위)는 교집합의 도형이 2차원이기 때문에 2가 나오고, IB는 교집합이 직선이므로 1이란 값이 도출됩니다.
A simplified version of dim(x) values are obtained mapping the values to T (true),
so using the boolean domain .
종류 | Dimension | boolean |
---|---|---|
점(Point) | 0 | T |
선 | 1 | T |
면 | 2 | T |
EMTPY | -1 | F |
[Dimension이 0이라고 false가 아닙니다!]
그리고 DE-9IM
을 boolean으로 변환할 때 점, 선, 면은 모두 true이며 존재하지 않는 도형은 false가 됩니다.
그럼 다시, 앞서 작성한 두 가지의 테스트코드를 다시 살펴봅시다.
테스트를 통과하지 못한 이유
앞에 두 가지의 경우에 대해 테스트코드를 작성했습니다.
- 점A가 영역B 안에 있는 경우
DE-9IM(A, B) = [0 F F F F F 2 1 2] - 점A가 영역B 경계선에 있는 경우
DE-9IM(A, B) = [F 0 F F F F 2 1 2]
문서에 보면 within을 포함한 covers, contains … 함수들의 DE-9IM
규칙을 설명한 내용이 있습니다.
within의 규칙은 [T F F ]입니다. 그래서 1번 조건은 만족하지만, 2번 조건을 만족하지 않습니다.
그래서 테스트코드에서 within의 값은 false로 반환됨을 알 수 있습니다.
2번 조건을 만족하기 위해선 wihtin 함수가 아니라 coveredBy 함수를 사용해야 합니다.
contains는 within의 도형의 순서가 바뀐 것이며, covers와 coveredBy도 유사한 관계를 알았습니다.
역시 아는 만큼 보입니다!
문서를 잘 읽고 개발을 합시다.
끝.
조금 더 들여다봅시다.
수포자들은 뒤로가기를 눌러주세요
DE-9IM
을 사용하여 두 도형의 관계를 표현하는 방식을 알았습니다.
그런데 말입니다.
두 도형의 교집합을 판단하는 건 어디까지나 저의 뇌피셜로 판단을 했는데요,
한 점(Point)이 다른 도형 안에 있다는 것을 어떻게 컴퓨터가 판단하는지 궁금해졌습니다. 그래서 한번 찾아봤습니다.
보통 가장 많이 사용하는 방법은 Ray Casting Algorithm
입니다.
[알고리즘이라서 그런지 0부터 시작(소오름)]
알고리즘은 대략 이렇습니다. 그림을 보면 알 수 있듯이, 점을 지나는 임의의 직선을 하나 쭉! 그립니다.
그러면, 그 직선과 도형이 만나는 교점
이 생깁니다. 이 교점
을 기준으로 7개의 선이 만들어집니다.
그 점이 홀수 번째 선 위에 있으면 도형 안에 포함, 짝수 번째 선 위에 있으면 도형 밖에 있다고 판단하면 됩니다.
( 이렇게 심플한 방법이! )
그럼 만만한 문제를 한번 풀어봅시다.
수학적 사고를 언어로 작성합니다.
[수학문제 같이 생긴 문제를 풀어봅시다]
임의의 점(4, 8)이 삼각형 안에 있는지 밖에 있는지 확인하시오. (3점)
문제를 해결하는 순서는 다음과 같습니다.
- 삼각형 직선 3개 방정식을 구한다.
- 점(4, 8)을 지나는 직선(y = 8)과 직선 3개의 교점을 구한다.
- 점(4, 8)이 교점들 사이 몇 번째 선위에 있는지 구한다.
- 작성 후 자신의 노력에 감동하여 오열한다.
먼저 좌표들을 순회하면서 직선의 방정식을 구합니다.
Coordinate[] coordinates = {
new Coordinate(2.0, 10.0),
new Coordinate(10.0, 11.0),
new Coordinate(5.0, 1.0),
new Coordinate(2.0, 10.0)};
for (int i = 0; i < coordinates.length - 1; i++) {
Coordinate curr = coordinates[i];
Coordinate next = coordinates[i + 1];
직선의 방정식
직선의 방정식은 y = ax + b ( a는 기울기
, b는 y절편
) 입니다.
두 점이 있는 경우 기울기
( y증가량 / x증가량 )를 구하고, y절편
은 두 점 중 한 점과 기울기
를 대입하여 값을 구합니다.
Double angle = (next.y - curr.y) / (next.x - curr.x);
Double yIntercept = curr.y - (angle * curr.x);
3개의 직선 방정식을 구했습니다. 이제 직선들과 점(4, 8)을 지나는 파란 직선(y = 8)과의 교점
을 구합니다.
y = angle * x + yIntercept 직선에 y = 8을 대입하여 교점(?, 8)들의 x좌표를 구합니다.
Double xIntersection = (8 - yIntercept) / angle;
교점
교점을 모두 구하면, 다음과 같이 3개의 교점(빨간색점)의 x값을 찾을 수 있습니다.
[예외인 녀석이 있는 것 같다]
그림에서 보면 가장 왼쪽에 있는 교점(빨간색점)은 삼각형의 변 위의 점이 아니기 때문에 예외를 해줘야 합니다.
두 점의 x 값을 범위로 지정하여 교점이 그 사이에 있는지 판단하고, 삼각형과 만나는 교점만을 리스트에 추가합니다.
// 두 점의 중간값과 차이를 구하고 교점이 사이에 있음을 판단합니다.
Double middle = (curr.x + next.x) / 2;
Double distance = Math.abs(next.x - middle);
boolean between = Math.abs(xIntersection - middle) <= distance;
if (between) {
xIntersections.add(xIntersection);
}
몇 번째 선 위에 있는가?
마지막으로, 점(4, 8)이 교점들 사이에 생긴 선 중 몇 번째 속하는지 판단합니다.
int x = 4;
// 간단한 계산을 위해 최대값과 최소값을 넣어줍니다.
xIntersections.add(Double.MAX_VALUE); // +무한
xIntersections.add(Double.MIN_VALUE); // -무한
xIntersections.sort(Double::compareTo);
...
for (int i = 0; i < xIntersections.size() - 1; i++) {
Double curr = intersections.get(i);
Double next = intersections.get(i + 1);
if (curr < x && x < next) {
// 짝수 번째는 OUT, 홀수 번째는 IN.
boolean within = (i % 2 == 1);
return within;
}
...
}
...
감동적인 마무리
수고하셨습니다. 드디어 끝났어요! ( 짝짝짝 )
이렇게 간단(?)하게 작성할 수 있었습니다. 하지만 현실은 그렇게 간단하지 않죠.
알고리즘이 매력적으로 간단하지만, 항상 잘 작동하는 것은 아닙니다.
Unfortunately, this method won’t work if the point is on the edge of the polygon.
이런 경우는 임의의 점이 도형 안에 포함되어 있지만, 알고리즘에 의하면 짝수 번째의 선 위에 있어 밖에 있다고 잘못된 값을 반환하게 됩니다.
물론 현실에서 사용하는 도형들은 유한한 점으로 표현하기 때문에 충분히 예외를 처리할 수 있습니다.
끝맺으며
포스팅을 간단하게 시작했지만, 내용이 산으로 가기도 하고, 기술과 멀어지고, 많이 길어지기도 했습니다.
이런 글도 있어야 다양한 곳에서 인사이트를 얻을 수 있다는 핑계로 작성을 했습니다.
개인적으로, 오래전부터 지도 API를 사용하면서 폴리곤 같은 도형 안에 포함 여부를 판단하는 로직에 궁금증이 있었습니다.
우연한 기회에 잊고 있던 작은 호기심을 깊게 찾아볼 수 있던 좋은 경험이었습니다.
긴 글 읽어주셔서 감사합니다.
문서를잘읽습니다 #영어공부필수 #일을이렇게열심히
진짜 끝.
참조문서