QHULL 함수를 이용하여 최대 볼록 다각형 찾기 (3차원)

2차원 이상의 공간 내에서 다수의 점들이 분포하는 상태에서 Quick Hull 알고리즘에 의하여 이 점들을 모두 포함하는 최대 크기의 볼록 다각형(Largest Convex Polygon)을 찾아내는 작업을 IDL에서 QHULL 함수를 사용하여 수행하는 방법 및 예제를 지난 회차 게시물에서 소개한 바 있습니다. 지난 예제의 경우는 2차원 공간상에 분포한 데이터 포인트들을 대상으로 하였는데요. 기본적으로 QHULL 함수는 2차원 이상인 경우에 대하여 적용이 가능합니다. 그래서 오늘은 3차원 공간상에 분포한 데이터 포인트들을 대상으로 QHULL 함수를 적용해보는 예제를 소개해보고자 합니다.

 

먼저 다음과 같이 3차원 공간상에 분포하는 10개의 포인트들에 대한 X, Y, Z 좌표 데이터를 생성하는 방식으로 가상의 데이터를 정의해봅시다.

 

n = 10
x1 = RANDOMU(-1, n)*10
y1 = RANDOMU(-4, n)*10+50
z1 = RANDOMU(-7, n)*10+30

 

먼저 이 데이터를 3차원 공간상에 표출하고 그 모습을 살펴봅시다. 이러한 작업은 다음과 같이 SCATTERPLOT3D 함수를 사용하여 진행할 수 있습니다. 참고로 SCATTERPLOT3D 함수의 기본적인 사용법은 예전에 올렸던 관련 게시물의 내용을 참조하시면 됩니다.

 

win = WINDOW(DIMENSIONS=[600, 600], /NO_TOOLBAR)
p = SCATTERPLOT3D(x1, y1, z1, SYM_OBJECT=ORB(), $
  SYM_SIZE=1.5, SYM_COLOR='green', $
  XRANGE=[0, 10], YRANGE=[50, 60], ZRANGE=[30, 40], $
  AXIS_STYLE=2, ASPECT_Z=1, MARGIN=0.2, CLIP=0, $

  FONT_SIZE=11, /CURRENT)

 

이러한 과정에 의하여 표출된 그림은 다음과 같습니다.

 

 

그런데 이 상태에서 각 포인트의 일련번호도 함께 표시하는 것이 어떨까 합니다. 이후에 QHULL 함수를 적용한 결과를 해석하는데 있어서 도움이 되기 때문입니다. 이 과정은 다음과 같이 반복형 구문 및 TEXT 함수를 사용하는 방식으로 처리해봅시다.

 

FOR j = 0, N_ELEMENTS(x1)-1 DO $
  tx = TEXT(x1[j]+0.1, y1[j]+0.1, z1[j]+0.1, STRTRIM(STRING(j), 2), /DATA)

 

그러면 다음과 같이 각 포인트마다 일련번호까지 표시된 그림을 얻을 수 있습니다.

 

 

이제 이와 같이 3차원 공간상에 분포하는 점들을 모두 포함하는 최대 크기의 볼록 다각형을 얻기 위하여 QHULL 함수를 적용하고 결과를 산출해봅시다. 기본적인 사용법은 지난 게시물에서 소개된 2차원 데이터의 케이스와 거의 유사하며 단지 Z축 좌표 데이터가 추가된다는 차이만 있을 뿐입니다. 그 과정은 다음과 같습니다.

 

QHULL, x1, y1, z1, t
HELP, t
PRINT, 'Output list of vertices (t variable) from QHULL: '
PRINT, t

 

일단 이와 같은 과정에 의하여 출력된 내용을 보면 다음과 같습니다.

 

T               LONG      = Array[3, 14]
Output list of vertices (t variable) from QHULL: 
           0           6           8
           6           0           2
           6           5           8
           1           0           8
           1           3           0
           5           1           8
           1           5           3
           5           7           3
           0           7           2
           3           7           0
           7           4           2
           4           7           5
           4           6           2
           6           4           5

 

그런데 지난번 2차원 데이터에 대한 예제와 비교하면 내용이 좀 더 복잡해보이는 감은 있습니다. 이 값들은 대체 뭘까요? 원래 3차원 다각형(Polygon)은 개별 단위 요소에 해당되는 삼각형의 면(face)들 여러 개로 구성됩니다. 그래서 위에서 산출된 t가 3x14의 구조를 갖는 배열이라는 것은 QHULL에 의하여 산출된 최대 크기 다각형이 14개의 삼각형 면들로 구성된다는 의미입니다. 이 때 각각의 삼각형 면은 3개의 꼭지점들(vertices)로 구성됩니다. 따라서 위에서 숫자들로 출력된 내용 한 줄은 삼각형인 각 면을 구성하는 3개의 포인트들에 대한 인덱스 번호들입니다. 예를 들어 첫번째 라인의 0, 6, 8은 앞서 정의된 10개의 포인트들 중 첫번째, 일곱번째, 아홉번째 포인트를 뜻하며 이 포인트들로 구성되는 삼각형의 면이 최대 크기 다각형을 구성하는 14개의 면들 중 하나임을 뜻합니다. 그러면 이러한 삼각형의 면(face)이 실제로 어떻게 위치하는가를 살펴보기 위하여 이 면의 좌표값들을 얻고 표출도 해봅시다. 그 과정은 다음과 같습니다.

 

  j = 0
  inds = t[*, j]
  x2 = x1[inds]
  y2 = y1[inds]
  z2 = z1[inds]
  plg = POLYGON(x2, y2, z2, FILL_COLOR='tomato', TRANSPARENCY=0, /DATA)

 

이와 같이 14개의 면들 중 첫번째 면을 구성하는 세 개의 점들에 대한 X 좌표값들로 구성된 x2 배열, Y 좌표값들로 구성된 y2 배열, Z 좌표값들로 구성된 z2 배열을 각각 얻고 이들을 POLYGON 함수에 투입하였습니다. 즉 기존의 그림상에 이러한 폴리곤이 추가로 표시되도록 한 것입니다. 표출된 그림을 보면 다음과 같습니다.

 

 

여기서는 j의 값이 0이므로 14개의 삼각형 면들 중 첫번째 면의 모습 및 위치를 확인할 수 있습니다. 그리고 위의 내용에서 j의 값을 바꾸면 다른 면들의 모습도 확인할 수 있습니다. 만약 j의 값이 6인 경우에는 구성 포인트들의 인덱스 번호가 1, 5, 3이 되며 이 경우의 표출 결과는 다음과 같습니다.

 

 

이와 같이 j의 값을 0~13의 범위 내에서 선택하여 바꿔보면 각 면의 모습 및 위치를 확인할 수 있는 그림을 표출할 수 있습니다. 그런데 우리의 목표는 위와 같이 삼각형 면을 하나씩 표시하는 것이 아니고 이러한 삼각형 면들로 구성된 전체 다각형을 표시하는 것입니다. 따라서 이러한 결과를 얻기 위해서는 추가적인 처리가 필요합니다. 이러한 처리는 기본적으로는 맨 처음에 정의했던 x1, y1, z1 배열들을 POLYGON 함수에 투입하여 다각형을 구현하는 작업이긴 합니다. 즉 다음과 같은 방식을 생각해볼 수 있습니다.

 

plg = POLYGON(x1, y1, z1, FILL_COLOR='tomato', /DATA)

 

다만 이와 같이 처리할 경우에는 우리의 기대와는 전혀 다른 엉뚱한 형태의 다각형이 표시될 것입니다. 그 이유는 주어진 10개의 포인트들의 꼭지점 좌표들만 주어졌을 뿐 이들을 연결하는 순서 및 방식에 대한 세부 정보는 전혀 주어지지 않았기 때문에 다각형을 구현하는 과정을 IDL이 그냥 알아서 처리하기 때문입니다. 따라서 그냥 이러한 방식으로 처리하면 안됩니다. 그 대신 최대 크기 다각형을 구성하는 포인트들끼리만 정확히 연결되도록 하기 위한 연결성(Connectivity) 정보까지 함께 제공하는 것이 필요합니다. 그리고 이러한 연결성 정보는 앞서 QHULL 명령을 사용하여 t라는 이름으로 이미 얻었습니다. 따라서 POLYGON 함수의 CONNECITIVITY 속성에 이러한 연결성 정보를 부여하면 되는데, 안타깝게도 t를 이 속성에 그대로 투입할 수는 없고 중간 처리가 필요합니다. 일단 그 과정은 다음과 같습니다.

 

ni = (SIZE(t, /DIM))[1]
conn = !null
FOR j = 0, ni-1 DO conn = [conn, 3, t[*, j]]
HELP, conn

 

이것은 최대 크기 다각형을 구성하는 14개의 삼각형 면들의 꼭지점 좌표 값들을 1차원적으로 나열하면서 각 면마다 3개의 점들로 구성됨을 명시하는 3이란 값을 중간중간에 끼워주는 과정이라고 보면 됩니다. 원래 POLYGON 함수에 투입되는 연결성 정보는 이와 같은 방식으로 구성되어야 하기 때문에 굳이 위와 같은 중간 과정이 반드시 필요합니다. 따라서 이와 같이 정리된 연결성 정보를 담은 1차원 배열인 conn을 POLYGON 함수에 투입하면 됩니다.

 

plg = POLYGON(x1, y1, z1, CONNECTIVITY=conn, FILL_COLOR='tomato', /DATA)

 

따라서 최대 크기 다각형을 제대로 표출하기 위한 전체 과정을 맨 처음 그래픽창을 띄우는 작업부터 시작하도록 다시 정의해보면 다음과 같습니다.

 

win = WINDOW(DIMENSIONS=[600, 600], /NO_TOOLBAR)
p = SCATTERPLOT3D(x1, y1, z1, SYM_OBJECT=ORB(), $
  SYM_SIZE=1.5, SYM_COLOR='green', $
  XRANGE=[0, 10], YRANGE=[50, 60], ZRANGE=[30, 40], $
  AXIS_STYLE=2, ASPECT_Z=1, MARGIN=0.2, CLIP=0, $

  FONT_SIZE=11, /CURRENT)

QHULL, x1, y1, z1, t
HELP, t
PRINT, 'Output list of vertices (t variable) from QHULL: '
PRINT, t

ni = (SIZE(t, /DIM))[1]
conn = !null

HELP, conn
FOR j = 0, ni-1 DO conn = [conn, 3, t[*, j]]
plg = POLYGON(x1, y1, z1, CONNECTIVITY=conn, FILL_COLOR='tomato', /DATA)

 

여기서는 앞서 TEXT 함수로 각 포인트의 인덱스 번호를 표시했던 내용은 이제는 필요없을 것으로 판단되어 삭제하였습니다. 이러한 과정을 실행하여 얻어지게 되는 표출 결과는 다음 그림과 같습니다.

 

 

즉 처음에 주어진 10개의 포인트들을 모두 포함하는 최대 크기 다각형은 이와 같은 모습이 됩니다. 유의할 점은 이 최대 크기 다각형을 구성하는 꼭지점들(Vertices)의 갯수는 8개라는 것입니다. 즉 원래 주어진 10개의 점들 중 나머지 2개는 이 다각형의 내부에 위치합니다. 따라서 이 그림에서는 그 2개의 점들의 모습은 보이지 않습니다. 물론 볼 수 있는 방법은 있습니다. 바로 다각형 자체를 약간 투명하게 보이도록 처리하는 것입니다. 이를 위하여 앞서 POLYGON 함수가 사용되었던 부분에서 TRANSPARENCY 속성을 추가해봅시다.

 

plg = POLYGON(x1, y1, z1, CONNECTIVITY=conn, FILL_COLOR='tomato', TRANSPARENCY=50, /DATA)

 

이와 같은 수정사항을 반영하여 다시 실행해보면 결과는 다음과 같습니다.

 

 

실제로 이러한 표출 그림의 경우는 마우스 왼쪽 버튼을 누르고 드래그하면서 다각형을 돌려볼 수 있습니다. 그러면 다각형의 안쪽에 존재하는 2개의 점들이 좀 더 명확하게 보일 것입니다.

 

지금까지 살펴본 예제는 10개의 포인트들로 구성된 데이터였는데요. 갯수가 더 많은 데이터의 경우도 한번 살펴봅시다. 맨 처음에 정의했던 변수 n의 값을 100으로 바꿔서 100개의 포인트들로 구성된 데이터에 대하여 동일한 방식으로 최대 크기 다각형을 얻어보면 결과는 다음 그림과 같습니다.

 

 

이 결과의 경우는 원래 주어진 포인트들의 갯수는 100개이지만, 최대 크기 다각형을 구성하는 포인트들의 갯수는 56개가 되는 것으로 확인됩니다. 즉 나머지 44개의 포인트들은 다각형의 내부에 위치합니다. 앞서 언급했듯이 마우스 왼쪽 버튼을 누르고 드래그하면서 살펴보면 이러한 사실을 쉽게 확인할 수 있을 것입니다.

 

지금까지 살펴본 바와 같이 3차원 공간상에 분포하는 데이터 포인트들에 대하여 최대 크기 다각형을 얻는 과정은 대략 이와 같습니다. 따라서 2차원 또는 3차원 공간상에서 분포하는 다수의 포인트들로 구성된 집단 데이터가 있을 때, 이와 같은 처리를 통하여 데이터 전체를 아우르는 다각형을 얻는 것이 가능하다는 것을 참조해두시면 좋을 것 같습니다.

 

 

 

이 글이 도움이 되었다면 게시물에 대하여 공감 버튼(하트 모양) 클릭 및 블로그 구독도 해주시면 더 큰 힘이 됩니다. 감사합니다.