본문 바로가기

Function

섬 사이로 막가는 어선 경로 그리기

글 : 김승범 


이번에 한 작업은 어선 입출항 데이터로 16개 어항을 거쳐간 어선들이 지나다닌 경로를 그리는 일이었다. 그린 경로를 통해 16개 어항의 대략적인 영향권을 가늠할 수 있어야 했다. 분석은 아니고 시각화 작업만 했다. 사실 아직 안 끝났고 막바지 작업중인데, 기억이 생생할 때 기록해두기 위해 글을 써본다.


출발지에서 도착지까지 경로를 그리는 일이 약간 도전해볼만하다고 생각해서 시작했는데, 생각보다 훨씬 더 복잡한 작업이었다.


사실 발목을 잡는 복병은, 처음에 미처 생각못한 데이터에서부터 시작되었다. 일단 데이터 얘기부터 해보자.




우리나라에는 2000개가 넘는 어항이 있다. 그리고 어디에 있는지 아무도 모른다.


우리나라에는 소규모 어항을 포함하여 2000개가 넘는 어항이 있다. 유리 상자에 물과 물고기를 담는 어항 말고, 어선이 정박하는 항구말이다. 전라남도와 경상남도에는 정말 항구가 많은데 아래 사진에서 툭툭 튀어나온 것들이 모두 독립적인 어항이다. 이 어항들은 모두 다 이름이 있고, 어선의 입출항 여부와 탑승자 등을 모두 관계관청에 신고하게 되어 있다. 


여수시 화양면 일부 캡쳐. 출처 : google map


신고 제도의 취지는 간첩이나 밀입국 등 불법적인 입출항을 감시하기 위함이었는데 어쨌든 이렇게 쌓인 데이터를 통해 어업이 어디서 어떻게 얼마나 이루어지는지 파악할 수 있을뻔 했다. 

음? 갑자기 무슨 말이냐고? 놀랍게도 백 몇십개 국가 관리 어항을 제외하면 어항의 이름이 KEY값으로 관리되지 않고 있기 때문이다. 같은 어항을 비슷하거나 다른 이름으로 부르는 경우도 있고, 동명이인처럼 동명이항, 동명삼항... 도 있기 때문에 데이터를 쉽게 취합할 수 없다. 국가 관리 어항의 총 입출항 규모는 알 수 있지만 소규모 어항을 포함한 어항 간의 네트워크 관계는 알기 어렵다. 


입출항 신고는 어선 gps인 V-PASS 로 자동적으로 되거나, 사람이 수기로 기입한다. 그리고 또 한번 놀랍게도 V-PASS 데이터에서 뽑아낸 어항 이름조차 분명히 같은 어항인데 같은 이름으로 기입되지 않은 것들이 있다. 

그런데 비단 문제는 거기에 그치지 않는다. 어항의 위치조차 국가 관리 어항을 제외하면 좌표값으로 관리되지 않고 있다. 관리되고 있는 어항조차 실제 위치의 인근에 대충 찍혀 있는 경우가 많아서, 약간의 과장을 섞자면 사실상 어항 공간 정보는 모두 엉터리인셈이다.





859개 어항을 하나하나 찾았다


어선 경로를 그려보자 하고서 왜 이런 얘기를 그리 길게 하냐면, 실제 작업에서 절반 이상의 시간이 2000여개 어항 중 859개를 하나하나 직접 찾는데 소요되었기 때문이다. 

가장 찾기 어려웠던 것은 '송림'이었다. '송림항'이나 '송림포구'와 같은 검색어로는 물론 찾을 수 없다. 해당 어선의 선적지와 전후 입출항지를 파악하여 실질적으로 시간 내에 갈 수 있는 곳들 안에서 특정해야 했다. 결국 낙찰된 곳은 전남 고흥군 대서면 송림리의 한 어항. 행정구역 이름(리)으로 기입된 소규모 어항이 꽤 많았다. 

가려내기가 난해했던 것은 '송도'였다. 송도는 전국 곳곳에 뿌려져 있었는데, 입출항 기록에는 '송도2, 송도동편항, 송도서편항, 송도출장소, 송도항, 학림대행신고소(송도), 지도 송도' 가 있었고 거기서 무엇이 무엇인지 가려내야 했다.


데이터 정제는 어떤 작업이든 시간이 오래 걸리는 편이다. 잘 모를 때는 '사람이 만든 데이터는 오류가 많고, 신용카드처럼 기계가 만든 데이터는 정확하다'고 말하고 다녔는데 이 말은 맞을 수도 있고 틀릴 수도 있다. 처음부터 끝까지 사람의 손을 타지 않은 데이터는 거의 없기 때문이다. 특정 지역의 3-4년치 신용카드 데이터를 본 적이 있는데 해가 바뀌면서 업종 분류 기준이 바뀌어서 특정 분야의 신용카드 사용량이 갑자기 튀는 경우도 있었다. 분류는 사람이 하는 작업이니 원래 데이터가 정확하다 치더라도 결국 분류하는 과정에서 데이터가 혼란스럽게 바뀔 수도 있다.


어쨌든 데이터 정제 과정에서는 통상적으로 주요한 오류들을 바로잡는 코드를 짜서 일괄적으로 처리하고, 체에 걸러지지 않고 남아있는 몇몇 특수한 예들은 수작업으로 잡아주기 마련이다. 그렇다면 데이터 정제 과정에서 최악의 경우는 일괄 처리가 전혀 불가능하여 모든 하나하나를 직접 수작업해야 하는 경우. 이번 경우가 바로 그랬다.


안타까운 점은 그렇게 정리한 좌표파일도 일반적으로 사용하기 어렵다는 점이다. 왜냐하면 공식적인 어항 이름이 없는 경우가 대부분이라 같은 어항을 가리키는 이름들 중에 내가 임의로 정하여 기입했기 때문이다. 이런 작업은 국가에서 표준 key 값과 표준 어항이름을 정하는 수 밖에 없다.


그래서 결국 859개의 어항들을 찾아냈다. 내가 전달받은 2017년 어선 입출항 기록은 모두 1000만 line정도 되었고, 거기에 등장한 어선은 약 5만대였다. 

그 중에 시각화 대상인 16개 어항을 출입항한 어선은 모두 6,580대였고, 그 어선들이 출입항한 어항 중 859개 어항을 찾으면 16개 어항 관련 전체 입출항 기록의 98%가 커버되었다. 나머지 2%가 1000여개 어항과 관련된 기록이기 때문에 거기서 찾는 것을 그만 멈추었다.



여수와 남해 일부. 정말 많다





손으로 경로를 그리기에는 종류가 너무 많아서 코드를 작성하여 경로를 만들기로 했다



이제 데이터가 정리었고 출발지와 목적지들의 좌표값을 얻었으니 그리기만 하면 된다. 시작이 반이라고 하는데, 정말 시작하면서 절반의 시간을 쓰게 되었다.


내가 전달 받은 예시 파일은 아래와 같았다. 한참을 들여다보았는데, 아무래도 손으로(마우스로) 그린 것 같다. 곡률들이 다른 경우가 많고 곡률을 적용한 규칙을 좀처럼 찾기가 힘들었기 때문이다. 처음에는 나도 손으로 그릴까 살짝 고민했지만 데이터를 정리해보고 나니 그 경우의 수가 너무 많아서 손으로 그리면 859개 어항을 찾을 때보다 훨씬 더 오래 걸릴 것 같았다.


여튼 아래의 그림은 적절히 섬의 위치도 옮겨가면서 깔끔하게 잘 그렸다고 생각한다.



출처 : 새로운 어촌종합개발의 개발방향 및 로드맵에 관한 정책 연구



이제 코드를 작성해서 그리기로 결정했으므로 어떤 방식으로 경로를 만들어낼지 고민해야 했다. 


사실 처음에는 단순하게 생각했다. 위의 예시를 코드로 그리는 일은 (물론 손작업처럼 깔끔하기는 어렵겠지만) 상대적으로 쉽다. 좌측 울릉도의 경우에는, 출발지에서 도형 중심을 뒤로 하고 선을 뻗어나오게 한 후 섬보다 큰 원을 상정하고 거기에 근접하게 지나친 후 꺾어서 다시 목적지로 들어가면 된다. 우측의 그림, 즉 울릉도와 동해안의 경우도 몇 가지 예외를 제외하면 어렵지 않다. 울릉도에서 좀 더 동쪽 방향으로 뻗어나가다가 방향을 되돌려 각각의 동해안 목적지로 가면 된다. 

어떻게 보면 하나는 출발지와 목적지가 원의 테두리를 돌아가는 경우고, 다른 하나는 한 점에서 횡대로 나열해 있는 다수의 목적지까지 선을 잇는 이상적인 경우였다. 항구들도 바다를 향해 보란 듯이 열려 있었다.







Euclidean Shortest Path를 이용해서 경로를 만들어보자



그렇지만 실제 어항들의 좌표를 찍어보고 났더니 그런 방식은 가능하지 않다는 점을 깨달았다. 섬과 섬 사이를 지나쳐서 돌아돌아 숨어있는 항구로 들어가야 하는 경우가 대다수였기 때문이었다.





이를테면 위와 같은 경우에 북항에서 목포동명항까지 가는 경로는 어떻게 그려야 할까? 방파제에 부딪치지 않고 잘 피해 나와서 돌아돌아 움푹 들어간 곳을 찾아내어 무사히 도착해야 한다. 하늘로 포물선을 그리면서 직선 경로로 직접 날아가는 방법은 애초에 배제했다. 사실 중간중간에 계속 유혹은 들었지만, 그래도 배잖아. 배는 모름지기 바닷길로 가야 한다. 어쨌거나 나는 목적을 달성하고 이 글을 쓰고 있으니 '그런건 시각화에서 지켜야 할 기본 정신이지'라고 허세 넘치게 말해본다.


결국 목적지를 찾아내는게 중요했고, 이건 그럼 '길찾기'의 문제였다. 일반적으로 최단경로를 찾는 작업은 링크와 노드가 이미 주어진 경우가 많다. 즉 헤매면서 최단경로를 찾을지언정 주어진 길에서만 헤매면 된다. 그런데 이렇게 도형만 있는 경우는 헤매야 하는 길부터 찾아내야 한다. 이런 작업은 목적에 따라 Euclidean Shortest Path라고도 불리고 Visibility Graph라고도 불린다. 건축이나 도시 공간에서 시각적 접근이 가능한 시야각의 한계선들을 만들어내고 그 선들을 아슬아슬하게 타고 돌아가면 결국 A에서 B로 가는 최단경로를 구할 수 있다.


아래 링크에 일부 내용이 정리되어 있고 맨 밑의 링크에서는 인터랙티브하게 이해해볼 수 있다.

https://fribbels.github.io/shortestpath/writeup.html


출처 : https://fribbels.github.io/shortestpath/visgraph.html


위의 그림은 최단경로를 찾는 한가지 방법을 이해할 수 있는 인터랙티브 페이지에서 가져왔다. 우선 도형들과 교차 관통하지 않으면서 도형들의 꼭지점을 이어주는 선들을 모두 찾아서 링크와 노드를 만든다. 그렇다면 그 후에는 링크와 노드가 주어진 일반적인 연결망 그래프의 최단경로 찾는 방법들을 사용할 수 있다.


그런데 문제는 위처럼 점의 수가 별로 되지 않을 때는 별로 상관없지만, 점의 수가 3만개, 10만개로 많아질 때는 미리 링크와 노드를 준비하는 일은 메모리 문제 등으로 실현해내기 어렵다. 따라서 하나의 출발점에서 다른 모든 점들간의 최단경로를 구하는 방법을 반복적으로 수행하여 결과값을 구해보기로 한다.


또 한가지, 위 그림에서는 불필요한 부분이 있는데, 바로 도형의 오목한 꼭지점들이다. 이 점들은 최단경로 계산에 전혀 기여할 수 없는데, 위의 방식에서는 오목한점마저 계산해서 메모리와 연산시간을 낭비했다. 이러한 점들을 염두에 두고 계산식을 만들어보았다.





이 작업은 알고리즘의 시간복잡도가 꽤 된다


이 부분은 알고리즘에 관심있는 사람들이 아니라면 건너뛰면 된다.


위의 링크에 소개된 첫번째 방법은 시간복잡도가 O(N^3) 이다. 해안선의 shpae을 이루는 점의 수가 증가하면 그 세제곱만큼 시간이 증가한다는 건데, 사실 N^2만 되도 꽤 부담스러운 시간이다. 그래서 좀 더 밑의 설명을 보니 역시 O (NlogN)까지 알고리즘이 발전되어 있었다. 그런데 다시 자세히 보니 이 Hershberger and Suri's Wave Algorithm 은 작업의 해상도를 정해서 마치 픽셀 단위인 것처럼 계산하는 방식이다. 그러한 방식은, 찾아보았던 내용 중 GPU를 이용한 병렬처리 방식도 있었다. 사실 픽셀 단위로 계산해도 큰 문제는 없었지만 다음에 또 할지도 모르는 유사 작업을 위해 그냥 벡터 공간 자체로 계산하기로 했다. 


많은 시행착오를 거쳐 아래의 방식으로 알고리즘을 정리했다. 알고리즘이 정리되기 전에는 1개 어항에서 858개까지의 최단경로를 찾는데 54만개 노드의 지도에서 열두 시간이 더 걸렸는데, 알고리즘을 정리하여 같은 지도에서 15분이 걸렸고, 시각적으로 문제 없을 수준에서 지도를 단순화 하여 3만개 노드로 줄인 후, 계산시간을 8~10초 까지 단축시킬 수 있었다. 대부분의 시간이 도형충돌 검증에 소모되고 있던 것을 발견했기 때문에 그 부분의 시간을 줄이는데 집중했다. 병렬화 하지 않은 single processor 작업 방식이다.



1. 지도 shape의 line들을 500m 간격으로 재분할하여 quadtree에 넣는다. 장애물 검증용이고, 분할하는 이유는 장애물 검색을 효율적으로 하기 위함이다. 쿼드트리에는 point들이 들어가므로 point 위치 기준으로 구조체를 만들어서 해당 point를 한 끝의 꼭지점으로 지니는 line을 등록해둔다.


쿼드트리는 사각형 공간을 사분면별로 분할해가면서 점들의 위치를 저장해두는 자료구조다. 점들이 많은 공간에서 필요한 특정 위치의 점들을 찾아낼때 4를 밑수로 하는 로그 시간만큼만 걸리게 된다. 공간정보를 다룰 때 어마무시한 시간의 계산을 하기 싫다면 반드시 익혀두어야 하는 자료구조다. 사실 잘 만든 쿼드트리 클래스가 있으면 굳이 내용을 열어보지 않고 간편하게 사용하면 되는데, 이번 작업을 하면서 결국 쿼드트리를 클래스 파일을 재구축하는 작업을 하게 되었다. 대부분 반경 검색만 제공하는데, 거기에 두세가지 검색을 추가해야만 했기 때문이다.


2. 지도 shape에서 볼록한 꼭지점만 솎아낸 후 오목한 꼭지점은 버린다.


3. 항구 위치를 읽어들인다.


---------------------------------출발지 개수 기준으로 LOOP------4번에서 13번까지 반복한다.---------------------------

4. 앞서 선별한 볼록 꼭지점들과 어항을 quadtree에 넣는다. 지도 전체의 line을 넣은 quadtree와는 별개다.


5. 출발지에서 4번에서 입력한 전체 점들을 대상으로 직선 연결 가능한 대상 점들을 찾는다. 검색된 목적지들은 2차 계산에서 출발지가 된다.


6. 연결 대상들을 찾는 방식은 다음과 같다. 등록한 다른 모든 꼭지점이 목적지로 연결될 수 있다는 가정 하에, 남은 꼭지점 수 만큼 루프를 돌면서 출발지와 그 꼭지점 사이에 다른 shape이 간섭하는지 충돌 검증을 한다. 충돌 검증을 할 대상은 앞서 1번에서 만든 quadtree를 기준으로 찾는다. 출발지와 목적지까지 직선으로 잇고, 그 직선을 따라 미리 분할해 둔 500m 반경으로 검색하면, 충돌가능한 물체는 반드시 그 쏘시지 모양의 영역에 들어오게 된다. 계산의 효율성을 위해 소세지 모양 대신 막대 모양으로 검색한 후 충돌을 검증하였다.


문제는 쿼드트리에서 기울어진 직사각형 영역을 기준으로 그 안에 포함된 점들을 추출해낼 수 있어야만 했다. 이 목적을 달성하기 위해 검색 함수를 직접 구현해야 했는데, 각 쿼드 사분면 직사각형이 기울어진 직사각형과 충돌하는지 계산해가면서 하위 트리로 내려가야한다.

통상적으로 이 충돌 검증을 AABB(Axis Aligned Bounding Box)와 OBB(Oriented Bounding Box)의 충돌 검증이라 부른다. 여러가지 방법이 있는데 분리축 이론을 사용하여 구현하였다. 나처럼 이런 분야가 전공이 아닌 사람들은 자타공인 최적 방법 같은 것이 있으면 편리한데, 그런 것은 잘 찾을 수 없었다.


분리축 이론을 이용한 AABB와 OBB의 충돌 검증 설명 그림

출처 : http://3dmpengines.tistory.com/1339. 원 출처는 다소 모호함






위 그림은 6번 설명의 예시 그림이다. 그림 안에 존재하는 해안선의 최대 길이를 500m로 한정해서 분할해 놓는 전처리 작업이 필요하다. 조발도항에서 굴구지항포구로 갈 수 있는지 판단하기 위해, 위의 영역안에 들어오는 선들에 대해 충돌 검증을 하고, 그 결과 해안선 2곳과 충돌이 검증된다. 당연한 말이지만 단 1곳이라도 해안선과 충돌한다는 말은 갈 수 없다(연결되지 않는다)는 말이다. 도달하려면 빙 둘러가야 한다. 그러므로 조발도항을 출발지로 하는 선을 찾을 때는 굴구지항 포구는 1차적 연결선에서 배제한다. 벌구(감도)와 가정항이 조발도항 기준으로 1차적으로 연결되는 항구가 된다.

그렇다면 더 잘게 쪼개면 검색되는 샘플 수가 줄어들게 되므로 더 유리한 것이 아닌가? 실제로 실험해본 결과, 쿼드트리의 하위 트리가 복잡해져서 메모리가 증가하고 찾는 시간도 더 오래걸렸다. 해안선의 복잡도에 따른 분할 최적치가 있는 듯 하다.

그리고 한 곳이라도 충돌하면 더 이상 다른 것들을 검색하고 충돌계산할 필요가 없기 때문에, 연산을 멈추고 판단을 내리도록 했다. 보통의 쿼드트리 함수는 검색 결과물만을 제공하는 방식으로 캡슐화 되어 있기 때문에,  그대로 이용하면 일단 모든 검색 결과를 받은 후, 2차적으로 충돌이 없는지 대조해봐야 한다. 결국 캡슐화를 깨고 private 변수들을 public으로 돌려서 검색과정과 판단 과정을 섞어야 했다. 클래스 관리 차원에서는 그다지 권장되지 않는 방법이지만, 이 방법을 통해 연산 시간을 절반 이하로 단축시킬 수 있었다.



7. 2차 계산부터는 앞 단계에서 찾아낸 도형의 꼭지점들이 출발지가 된다. 하나의 2차 출발지를 대상으로 설명하자면, 1차 출발지와 2차 출발지를 직선으로 잇고, 2차 출발지가 된 꼭지점과 같은 도형에 있는 인접 꼭지점 역시 직선으로 이으면, 그렇게 생기는 부채꼴 모양의 영역에, 그 2차 출발지가 최단경로상에서 직전 노드가 되는 3차 출발지들을 찾아낼 수 있게 된다. 역시 부채꼴 모양의 영역에 있는 점들은 쿼드트리에서 함수를 구현하여 검색한다. 이 것 역시 AABB(쿼드트리의 사분면들)와 삼각형의 충돌 검증과정이 필요한데, 역시 분리축 이론을 통해 계산했다. 계산의 효율성을 위해 부채꼴을 온전히 포함하는 이등변삼각형으로 찾는다.


예를 들어 점 p 다음의 최단경로 꼭지점으로 계산된 1번 점에서 다음 최단거리 꼭지점을 검색한다고 생각해보자. 앞에서 설명했듯이 위 그림에서 파란색으로 칠해진 영역 바깥 부분은 P와 1번을 거쳐간 선이 최단경로의 일부가 될 수 없다. 그러므로 파란 부분 안쪽에서 검색된 점들만 충돌 검증을 수행하면 되고, 이러한 한정 과정은 계산 시간을 드라마틱하게 줄여준다. 이렇게 목적지들을 한정하지 않으면 항상 모든 858개에 대해 충돌 검증을 해야 하기 때문이다.

물론 파란색 안쪽 영역이라고 해서 항상 1번을 거치는 경로가 최단경로가 되란 법은 없다. 단지 라인과 노드로 등록해놓고 다익스트라 등의 알고리즘을 활용하여 최단경로인지 판별할 대상에 올려놓을 수 있다는 말이다. 예를 들자면, 또 다른 경로가 섬의 반대편으로 돌아왔는데 더 짧을 수도 있기 때문이다. 



8. 계속적으로 반복하여 다음 차수의 점들을 찾아낸다.


Priority Queue를 이용하여 출발점으로부터 누적된 거리가 가장 짧은 선들부터 계산을 돌리면 중간중간에 최종 결정할 수 있는 기회가 좀 더 많아진다.


9. 그런데 모든 연결점들을 일단 다 찾아서 기록하면 연결선들이 (최악의 경우) 점들의 제곱수만큼 많아지게 된다. 꼭지점들을 찾으면서 최단경로 여부를 바로바로 판단하고 아닌 것들은 폐기하여 모든 루프가 끝났을 때 최단경로만 남기도록 한다. 위에서 https://fribbels.github.io/ 의 그림을 예시로 들면서 설명한 내용이다.


10. 최단경로 여부의 판정은, 반경을 일정한 단위로 넓혀가면서 다익스트라 알고리즘과 유사한 방식으로 해당 반경 안에서의 최단 경로를 계산하는 방식을 취한다. 예를 들어 전국의 어항 간 최단경로를 계산하는데 출발지로부터 최장 1300km까지 계산해야 했는데, 출발지 기준으로 100km단위로 한번 끊어서 그 한계 안에서 최단경로를 완벽하게 찾고, 다시 200km까지 넓혀서 그 안에서 최단 경로를 찾아가는 방식으로 계산하면, 순수 (유사)다익스트라 방식보다 헤매는 수가 줄어들어 전체 계산 시간도 줄어들게 된다. 


11. 한번 계산해서 최단경로 여부가 확실히 계산된 점들은 quadtree에서 삭제한다. 반경을 넓혀서 계산할 때, 이미 결정된 내용의 중복계산을 방지하기 위함이다.


12. 간단한 연산을 통하여 막다른 골목 여부가 판별 가능한 점들은 다음 차수에서 더 이상 출발지로 상정하지 않고 계산을 마무리 한다.


이 그림에 보이는 점은 인근 점들을 검색하고 검증만 해도 쉽게 막다른 골목 여부가 판단 가능하다. 이렇게 dead end로 끝나는 것을 쉽게 판별할 수 있을 경우에는 다음 출발지에 넣지 않고 작업을 멈춘다.


13. LOOP가 하나씩 끝날때마다 해당 출발점의 경로들을 저장한다.

----------------------------------------------------------------------------------------------------------------


일단 여기까지다. 위 알고리즘은 검색 반경을 몇 km 단위로 끊는지, 혹은 최소 분할 선분 크기와 충돌검색 영역이 몇m인지에 따라 성능이 달라진다. 항상 최적값은 없고, 전체 노드 수에 따라 달라지는 것 같다.



설명이 다소 복잡해보이는데, 사실은 좀 더 많이 복잡하다.

그래서 그런지 링크와 노드가 주어진 50만개 정도 line 그래프에서 1:N의 OD경로를 찾는데 2초 정도 걸리는 것과 비교해보면, 고작 3만여개 꼭지점의 도형임에도 불구하고 꽤 오래걸린다는 생각이 드는데, 인터넷을 아무리 헤집어봐도 시간복잡도만 나올 뿐, 유사한 규모에서 running time을 비교한 내용을 찾기 어려워 내가 어느 정도로 해결한 것인지 잘 모르겠다. 일단 작업이 가능한 수준으로 계산시간이 줄어들었기 때문에 그대로 진행하기로 했다.


859개 어항간의 경로(859 x 858 = 737,022가지)를 일단 모두 계산해 두어야 했으므로 루프를 돌렸고, 120분 정도에 모두 계산되었다.







드디어 섬 사이로 막가는 최단경로를 그렸다!



결과 예시. 섬 사이를 잘 비껴가면서 구석구석 잘 찾아가고 있다.


그래서 얻은 결과 중 하나는 위의 그림과 같다. 출발지는 화면 바깥에 있는데, 도착지들은 어항(원으로 표시된 것)과 화면안에 보이는 모든 공간의 최단경로를 만들어내기 위해 필요한 볼록 꼭지점들까지다. 지금은 찾고자 하는 점들이 858개 어항이란 것이 확실히 정해졌으므로, 나머지 최종 도착지 경로들은 지우고 어항까지의 858개 루트만 저장해두면 된다.


어딘가 선들이 빠진 듯한 느낌이 들 수도 있는데, 그렇지 않다. 위 그림에서 보이는 어떤 부분도 저기 보이는 선들의 끝점 중 하나와 한번만 이어주면 최단경로가 된다.



그리고 이게 바로 하나의 어항을 출발지로 둔 전국의 그림이다. 이 그림을 처음 제대로 그려냈을 때가 이번 작업 전 과정을 통틀어 성취감이 가장 컸다.






그런데 그대로 쓸 수 없었다. 배가 해안선을 스쳐지나가지는 않기 때문에



처음 하는 일을 하다보면, 이제 거의 다 끝난 것 같지만 다시 새로운 고비가 오곤 한다. 이번에도 최단 경로를 찾는 순간 시각화 작업의 전반부가 거의 끝났다고 생각했지만 계속 마음에 걸리는 부분이 있었다. 배가 해안선을 스치듯이 지나가는 부분이 아무리 생각해도 자연스럽지 못했다. 



예를 들면 위와 같은 부분이다. 실전항이나 물안항으로 가는 배들의 경로는 아무래도 자연스럽지 못하다. 저런 곳에서는 해안선과 해안선 사이의 한 가운데 즈음을 따라 가는 것이 더 자연스러워보인다. 지금 하는 일이 최단경로를 찾는 것이 목표가 아니라 배의 경로를 시각화하는 일이기 때문이다.


참고로 그림에 점들이 추가된 것은 이미 후 가공 작업이 약간 들어간 뒤의 결과 화면이기 때문이다. 최종 목적지에 진입하기 직전에 어느 정도 해안선에서 떨어진 곳에서 꺾어 들어가도록 했다. 최단경로는 그 dummy point 까지 구했다.





가장 간단한 방법은 원래 해안선에 500m 정도의 버퍼를 주어 새로운 도형으로 해안선을 만들고 그 해안선을 기준으로 최단경로를 구한 후 원래 해안선과 경로를 합쳐 최종 그림을 만드는 것이었다.





생각은 그럴듯 했지만 버퍼를 만들어보고는 문제가 있다는 점을 깨달았다. 위의 그림처럼 해안선이 엉겨붙어서 배가 지나다니지 못하는 경우가 생기기 때문이었다. 물론 버퍼 크기를 줄여보면 해안선이 엉겨붙는 문제는 없었지만, 사실 그건 있으나마나 마찬가지로 스쳐지나가는 것처럼 보였다.

애초에 문제가 되었던 부분이 바로 저렇게 해안선끼리 가까이 있는 경우였고, 가장 풀기 힘든 부분도 바로 그 부분이었다. 


저렇게 엉겨붙은 사이만 딱 갈라낼 수는 없을까?





보로노이 다이어그램에서 도움을 얻다


많은 시행착오를 거친 후에 Voronoi diagram을 떠올렸다. 이 알고리즘은 점들과 점들 사이에 같은 거리에 있도록 선들을 만들어준다. QGIS에서도 쉽게 해볼 수 있었기 때문에 별도의 코드를 작성하지 않아도 되는 장점이 있었다.

유클리디안 최단거리를 구할 때 '실제로 최단'은 아니지만 보로노이 다이어그램을 이용해서 적당히 중간들을 지나가도록 하는 방법도 있다. 내가 한 일은 그 방법의 일부를 약간 차용하여 섞은 정도다.



작업 순서는 아래와 같다. 모든 과정은 Qgis에서 진행했다.


1. 원래 해안선에서 여러 도형이 하나로 붙어 있는 MultiPolygon 이 있다면, 모두 독립시켜 Polygon으로 만든다. 만든 도형에 각각의 고유 ID를 부여한다.


2. 이 Polygon에서 꼭지점 Point를 추출한다. 각 point에 도형 고유 ID가 유지되었는지 확인한다.


3. 위에서 만든 point 들로 보로노이 다이어그램을 만든다.


4. 만들어졌다면 보로노이 폴리곤에도 point에 있던 고유 id들이 옮겨왔을 것이다. 이 고유 id값들로 dissolve한다. 아래의 그림은 dissolve 하기 직전에 도형 id별로 랜덤하게 색상을 부여한 그림이다. 병합하고 나면 아래 그림에서 색상별로 도형 하나씩 만들어진다. 내부의 선들은 지워진채로.



자, 이제 무엇을 하려는지 대략 짐작이 갈 것이다. 섬과 섬 사이의 중간 지점에 경계선들이 생겼다.




5. 보로노이 도형들을 병합하여 새로운 도형이 만들어졌다면 이제 안쪽으로 버퍼를 잡아 새로운 도형을 만든다. 여기서는 100m 씩 주어 200m의 바닷길이 생기도록 했다.

위에서 보여주었던 그림과 같은 지역으로 표현하자면 아래와 같다.








6. 이 보로노이 버퍼 도형과 앞에서 한번 시도해보았던 500m 해안선 버퍼를 겹쳐놓고 중첩되는 부분만 빼낸다.








7. 결과 그림은 아래와 같다.








8. 그런데 실전항 근처를 보면 점 기준 보로노이 연산의 특성상 한쪽 해안선으로 붙어서 꺾인 부분들이 보인다. 이런 부분을 제대로 해결하려면 C++ 라이브러리인 Boost library 같은 것들에서 제공하는 선이나 도형기준 보로노이 연산을 사용하면 된다.(사실 안 써봐서 정말 제대로 나오는지는 모르겠다. 적어도 예시 그림에서는 제대로 나온다) 그렇지만 이미 너무 많은 시간을 소요해서 이번에는 임기응변으로 해결하기로 했다. 새로운 라이브러리를 쓰는건 결국 내가 산출한 결과물의 형식과 라이브러리에서 필요로 하는 형식이 달라 꽤 많은 작업 시간을 필요로 하기 때문이다.



일단 도형을 단순화(simplify)해서 불필요한 요철들을 제거했다.

그리고 딱 한시간이라는 시간 제한을 걸고 배들이 지나다니는 주요 경로들을 기준으로 꺾인 해안선을 피는 수작업을 했다.








10. 최종적으로 만든 갈색 해안선 기준으로, 기존 어항에서 최근접한 곳에 어항의 dummy point를 만든다. 위의 그림에서 노란색이다. 기존 어항은 거의 다 새로 만들어진 해안선 내부에 위치하게 되므로 곧바로 연산하면 아무 어항도 찾아갈 수 없기 때문이었다.

최단거리는 이 노란색 점까지 구하고, 기존의 어항과 직선으로 잇는 작업을 한다.





11. 그래서 갈색 해안선 도형과 노란색 어항 기준으로 최단거리를 다시 구하면 드디어 아래와 같은 그림이 나온다.



그럭저럭 해안선을 스치지 않고 지나가게 되었다!



좀 더 넓은 지역을 보면 아래와 같다. 조금 더 그럴듯해졌다.








Catmull-Rom Spline으로 부드러운 곡선 그리기


이제 다 되었나고? 사실 이제부터 시작이다. 투박한 꺾인 선들을 그대로 쓸 수 없었기 때문에 부드러운 곡선으로 만들기로 했다.


일단 주요한 포인트를 지나는 경로들을 만들었으니 이 정점들을 지나는 스플라인을 만들기로 한다. 베지에 곡선 같은것을 이용해서 애써 피해간 해안선을 다시 넘나들수는 없으므로.

정점을 지나는 스플라인은 일반적으로 Cardinal 스플라인 방식을 이용한다. 그런데 긴 변과 짧은 변이 만날 때 선의 각도가 급격하게 꺾이면, 그 부담이 온전히 짧은 변으로 전가되었고, 따라서 굉장히 먼 곳까지 갔다가 돌아오는 형상이나 꼬인 선들을 곳곳에 만들어냈다.


그래서 찾아본 것은 Catmull-Rom spline. 이미 똑같은 문제들을 많은 사람들이 겪고 있었고 세상의 천재들은 이 문제를 이미 해결해놓았다. 캣멀롬 스플라인은 알파 값을 이용해 곡선의 보간 구간을 조절할 수 있고 알파값이 0이면 Cardinal과 일치하게 된다. 1에 가까울수록 단변보다는 장변이 그 부담을 지고 미리 꺾여 들어간다.


출처 : http://www.cemyuksel.com/research/catmullrom_param/



위의 그림에서 녹색이 알파값 0, Cardinal 방식이다. 긴 직선 구간은 그대로 가고 짧은 곡선 구간에서 꺾이는 부분을 부담하여 조정한다. 붉은 색이 알파값 1. 대부분의 부담을 장변에서 소화한다.


한글 위키 페이지에 파이썬으로 구현해놓은 코드가 있었고, 파이썬은 잘 모르지만 그럭저럭 찾아가면서 cpp 코드로 변환할 수 있었다.

https://ko.wikipedia.org/wiki/%EC%BA%A3%EB%A9%80%EB%A1%AC_%EC%8A%A4%ED%94%8C%EB%9D%BC%EC%9D%B8


이번에 만든 어선 경로는 끝부분에서 대부분 급격하게 꺾여 들어갔기 때문에 캣멀롬 스플라인 방식이 좋은 대안이 되었다. 알파값 0.5 정도로 셋팅하여 그렸다.





그래서 얻은 그림은 위와 같다. 시작과 끝을 가늘게 하고 중간을 두텁게 그렸다. 시각화는 OpenGL을 이용해서 그렸는데, 이런 곡선을 만드는 명령어 같은건 당연히 없고, 모든 라인 하나당 가느다란 부분부터 두꺼운 부분까지 좌표점을 분할해서 계산해서 그려야 한다. OpenGL의 Shader는 그런 작업을 gpu에서 빠르게 잘 처리한다. 





근데 이 길이 아닌가벼


그런데 문제가 있었다. 어항 간의 경로를 어항 간의 교류량에 따라 다르게 보여주어야 했는데, 결국 그건 두께나 색상으로 표현하는 것이 가장 좋다.


그런데 여수 국동항을 예로 들자면, 거리가 매우 가까운 어항들이 많이 있었고, 교류량이 다른 것들보다 월등히 많은 어항들은 인접하여 있는 것들이었다. 따라서 교류량에 비례하도록 두께를 주면 국동항 근처가 떡이 되어 아무것도 보이지 않았다. 색상이나 투명도로 구분해도 크게 다르지 않았다. 








확대해서 봐도 사정은 비슷했다.

하나의 출발지에서 도달해야 하는 너무 많은 도착지들이 있었는데, 그 경로들을 하나하나 분리해내기에는 너무 좁은 바닷길들을 동시에 지나쳐야 해서 만약 수작업으로 그린다고 하더라도 이게 과연 가능한 작업일까라는 의문이 들었다.


사실 처음부터 언급하지 않았던 것이 하나 있는데, 이 그림은 커봤자 일반적 책자 크기의 보고서에 한페이지로 들어간다. 그림 한장에 전국이 들어가야 한다. 중간부터 직감은 했지만 그 정도 작은 크기에서 가장 큰 면적을 차지하는 육지를 내버려두고 바닷길로만 돌아가는 경로를 보여주기에는 아무리 발버둥쳐봐야 넘을 수 없는 한계가 있었다. 사실 이 부분에서 그냥 육지를 가로질러가는 직선으로 그릴까 하는 유혹이 강하게 한번 더 들었다.


결국 '시작과 끝을 가늘게 하고 중간을 두텁게 표현한 곡선'을 만드는데 쓴 시간은 버리고 새로운 방법을 고안해야만 했다. 





성냥개비 여섯개로 삼각형 네 개를 만드는 방법은?


온전한 팔각 성냥 한 통을 한번에 불 붙여보고 싶은게 로망일만큼 성냥이 주변에 흔하던 시절, 다음과 같은 퍼즐 문제가 있었더랬다.


'성냥개비 여섯개를 부러뜨리지 않고 정삼각형 네 개를 만드는 방법은?'


정답은 3차원으로 정사면체를 만드는 것이었는데, 이 문제를 내는 사람은 해답을 모르는 사람 앞에서 항상 의기양양했고, 가끔씩 어딘가에는 발상의 전환이라는 예로 사용된 적이 있었던 것 같다. 나도 끙끙대다 그 재수없는 의기양양함 앞에서 패배를 선언했던 적이 있는지라 그 발상의 전환인가 뭔가 하는 것은 똑똑히 기억한다. 뭐라 설명할 수가 없지만 정답을 듣고는 약간 짜증이 났던 기억. 쳇. 사실 그게 뭐가 그렇게 대수라고.


참고로 성냥개비 네개를 부러뜨리지 않고 정삼각형 두 개를 만드는 문제도 있었다. 나에게는 그 정답이 더 발상의 전환 같고 재미있었는데, 단순히 삼각형 여섯개처럼 2차원과 3차원을 넘나드는 것이 아니라 실재와 지각의 차원을 다시한번 생각하게 해 주었기 때문이었다. 게다가 정답을 듣고 짜증보다는 웃음이 났던 기억이다.

성냥개비 세개로 정삼각형을 만들고 다른 하나로 눈 위를 살짝 찌르면 삼각형이 두 개가 된다. 여기서 가장 중요한 부분은 찌르는 부분이 각진 나무가 아니라 둥근 성냥머리여야 한다는 점이다. 

각진 나무 부분으로 눈 위를 찌르면 아프기 때문이다.





어선 경로에 3차원 표현을 넣어보자


허나 잘 안보이는 그림을 던져주고 '마음의 눈으로 보라'고 할 수도 없는 노릇이니 성냥개비 여섯개로 정삼각형 네 개를 만드는 방식을 이용하기로 했다.


두께로 어항 사이의 교역량을 표현할 때 치명적인 점은 2차원 공간 안에서 확장되기 때문에 한 선의 두께가 주변의 선들을 잘 안보이게 만든다는 점이었다. 투명도를 주어 표현해도 이번 경우는 한계가 있었다. 위의 그림처럼 어느정도 비례를 감안해도 너무 적게 주면 구분이 안되거나 약간 많이 주면 떡지거나 둘 중의 하나였다.


그래서 교역량을 서로 간섭하지 않는 바다 속, 즉 z값의 음수 방향으로 표현했다. 그랬더니 자세한 하나하나는 역시 구분이 힘들었지만 대략적인 집중 지역이 눈에 들어왔다. 출발지에서 0의 값, 도착지에 갈수록 교역량만큼 깊어지도록 해서 상호 간섭하는 부분을 최소화 했다.


처음에는 그 교역량을 어항을 나타내는 원의 크기로 표현하려고 시도해보기도 했지만 역시 간섭의 문제가 있었고, 그래서 다시 z축 양의 방향으로 어항 위에 세워서 눈에 잘 보이도록 했다. 사실 이건 작문을 배울 때, 하지 말라고 배우는 '동어반복(redundancy)'인 것 같기도 하지만 바닷속 파란색은 대체적인 교역집중지역을 보여주고, 땅위의 같은 수치 막대 그래프는 어항별로 잘 보여주기 때문에 이렇게 정리하기로 했다.


그리고 처음에는 특정 어항을 한번이라도 거쳐간 모든 배들을 그리는 것이었는데, 의견이 오고가면서 특정 어항을 입항하거나 출항한 이동만 선택하여 보여주기로 했다. 그래서 선의 복잡도와 개수가 대폭 줄어들기도 했다.

(그래서 사실 이렇게 정리될 경우, 단순히 시간만 고려한다면 그냥 손으로 모두 그리는게 더 빠를 뻔 했다.)



주요한 어항들의 이름을 표현하고 마무리.

이렇게 기나긴 작업과 기나긴 글은 끝을 맺는다.



참고로 아래 그림에 보이는 연도포구는 의뢰받은 16개 어항 중 하나는 아니고, 이 글에 싣기 위해 별도로 작업했다. 

연도포구는 여수시 행정구역 안에 있는 여수시 남쪽의 섬 연도에 있다. 약간 멀직이 떨어진 곳 중 교류량이 많은 곳은 그림 왼쪽의 거문도항인데 이 곳 역시 여수시다. 고흥군 남쪽에 있는 듯하지만.

왜 그렇게 행정구역을 정해는지는 모르겠지만, 남쪽 바다 위의 섬들은 물리적 거리와 행정구역 범위가 나란히 가지 않는 경우도 종종 있다. 또 한가지 재미있는 점은, 제주특별자치도는 한라산이 있는 커다란 섬과 그 주변이라고 대부분 알고 있지만, 꼭 그렇지만은 않다. 궁금하신 분들은 '추자도'를 찾아보시길.

대표이미지대표이미지