순회, location(Coordination) 좌표 기반 거리 측정 루프시 최적화 방법

그림 소프트웨어를 만들고 있는데, 최적화의 길에 들어선 상황이다. 아무래도 그림 소프트웨어는 선을 그리고 지울 때 성능 최적화가 사용자 경험에 중요한 영향을 끼치기 때문에 적절한 알고리즘을 구현할 필요가 있었는데, 최근 부딪힌 문제가 '거리 측정' 문제이다.

내가 만든 그림 소프트웨어에서 필기한 글자이다. 이 글자들은 레스터화 된 비트맵 이미지가 아니라, 모두 벡터 형태로 구현되어 있어 선을 일일이 그리는 방식으로 구성되어 있다. 따라서 글을 지우기 위해 한 획만 지우더라도 이어져있는 모든 벡터를 한 번에 지우는 등의 작업이 손 쉽게 가능하다.

한편 지우개를 구현할 때, 마우스 좌표로부터 제일 가까운 선을 검색한 뒤, 거리를 측정하고, 이 거리가 일정 이하일 때 해당 객체를 지우게끔 구현해야 한다. 즉 지우개를 들고 마우스를 움직일 때 마다 적어도 O(n)의 처리를 수행해야 하는 것인데, 그려진 벡터가 매우 많은 경우 이 벡터를 모두 순회해야 한다는 문제가 존재한다.

따라서 선을 그릴 때 무수히 많은 벡터들을 단순히 1차원 벡터에 저장해서는 호출할 때 최적화를 할 수 없게 되기에, 같은 성분을 가진 선끼리는 묶어 저장하고, 같은 성분을 바로 가져올 수 있는 방법이 필요했다.

2D 좌표계 기반에서 공통 성분을 묶을 방법은 x, y 좌표를 그리드 형태로 관리할 수 있다.

즉 커다란 격자 공간만한 메모리를 하나 만들어두고, 각각 메모리가 저장되는 파트를 분할한다. 그리고 특정 점과 직접적인 연관 관계를 가지는 그리드 좌표에 점을 리스트로 삽입하는 것이다. 즉 위 그리드 공간 하나 하나가 Array 배열 공간이라고 볼 수 있다.

즉 그리드 공간에 이렇게 데이터가 들어가 있을 때, 마우스와 제일 가까운 영역을 찾기 위해서 저 멀리 있는 객체를 조회할 필요가 없다.

빨간 점이 마우스 좌표라고 가정했을 때, 마우스 좌표를 그리드 좌표계로 옮긴 뒤에, 그리드 좌표계에서 해당 그리드의 리스트 배열만 바로 즉시 가져온 뒤 해당 공간 안에서만 순회를 돌면 된다.

즉 위와 같은 상황에서는 칠해진 영역의 그리드의 배열을 가져온 뒤 해당 배열 안에서만 순회를 돌면된다. 반지름과 같이 조금 여유가 필요한 경우 해당 그리드를 기준으로 특정 반지름만큼 더 추가로 그리드 배열을 가져오거나, 좌우 격자로 +- 1 여유를 주어 배열을 더 조회하면 된다.

즉 그리드 좌표로 변환하는 방법은 굳이 복잡하게 변환 행렬등을 쓸 필요 없다. 단순히 x 좌표와 y 좌표를 어느 수준으로 나눈 뒤에 정수로 변환해주면 된다. 그러면 세세한 길이 정보는 사라지고 큰 위치 정보로만 담기 때문에 해당 수준까지는 같은 배열 공간에 담아 보관할 수 있다.

가져올 때는 마찬가지로 해당 그리드 좌표계에 존재하는 객체들을 모두 가져오면 된다. 이 방식으로 검색 대상 범위를 최소한으로 줄여 성능을 대폭 향상하였다. 특히 넓게 작성하는 필기 소프트웨어의 경우는 한 공간에 글을 빼곡히 작성하기 보다 무한한 캔버스에 넓게 작성하기 때문에 이러한 방법이 매우 효율적이다.