Graph 펼치기

  Graph 형식의 데이타를 서로 겹치지 않게 도면에 펼치는 방법에 대한 내용입니다.

우선 생각이 드는 것은 우선 도면에 흩뿌려놓고 겹치는 부분이 있으면 겹치지 않게 서로 이동하는 것입니다.
모든 항목들이 서로 겹치지 않을때까지 이동하는 겁니다.
말은 쉽지만 그 결과가 어떨지 예측이 되지 않습니다.(시간은 얼마나 걸릴지, 모양은 어떻게 나올지…)
그래서 생각해본 것은 항목의 Bounding Box를 통하여 차지하는 영역을 예측하여 펼치는 방안입니다.
서로 직교하면서 지그재그 방식으로 펼쳐보도록 하겠습니다. 바로 이렇게요.

우선 하나의 라인을 선택합니다.

선택한 라인에 붙어 있는 브랜치 라인의 영역을 구합니다.

라인은 공간을 좌,우로 분할하고 홀수 브랜치는 좌, 짝수 브랜치는 오른쪽에 두게 되면 홀수 브랜치와 짝수 브랜치는 서로 겹쳐지지 않게 됩니다.

짝수 혹은 홀수 브랜치끼리 겹쳐지지 않도록 펼치면 됩니다.

위 그림에서 브랜치 3의 위치를

브랜치 3의 위치 = 브랜치 1의 위치 + 브랜치 1의 오른쪽 폭(A) + 브랜치 3의 왼쪽 폭(B)

이렇게 설정하면 브랜치 1과 3은 서로 겹쳐지지 않게 됩니다.

브랜치 3의 위치를 정한 후 브랜치 5가 있다면

브랜치 5의 위치 = 브랜치 3의 위치 + 브랜치 3의 오른쪽 폭 + 브랜치 5의 왼쪽 폭

로 정하면 브랜치 3과 브랜치 5는 서로 겹쳐지지 않게 됩니다.

이를 일반화시키면

브랜치(i+1)∗2=브랜치i∗2의위치+브랜치i∗2의오른쪽폭+브랜치(i+1)∗2의왼쪽폭

으로 브랜치의 위치를 구하면 됩니다.

여기서 브랜치 1의 영역을 구하기 위해서는

브랜치 1에 연결되어 있는 브랜치들의 영역을 구해야 합니다.

이것도 일반화시키면

Graph의 깊이 탐색을 하여 말단 노드의 영역을 구한 뒤 합하여 상위 노드의 영역을 구하면 됩니다.

브랜치 1의 영역은 다음과 같은 식으로 표현됩니다.

 $$\begin{Bmatrix}\begin{Bmatrix}브랜치_{1-1-1}\\브랜치_{1-1-2}\end{Bmatrix}=브랜치_{1-1}\\\begin{Bmatrix}브랜치_{1-2-1}\\브랜치_{1-2-2}\end{Bmatrix}=브랜치_{1-2}\end{Bmatrix}=브랜치_1$$