Main Content

볼록 껍질(Convex Hull) 구하기

MATLAB®은 다음과 같이 볼록 껍질을 계산할 수 있는 여러 가지 방법을 제공합니다.

convhull 함수를 사용하면 2차원과 3차원에서 볼록 껍질을 구할 수 있습니다. convhulln 함수를 사용하면 N차원(N ≥ 2)에서 볼록 껍질을 구할 수 있습니다. convhull 함수가 더 견고하고 대규모 데이터 세트에 뛰어난 성능을 제공하므로 2차원이나 3차원 계산에는 이 함수가 권장됩니다.

delaunayTriangulation 클래스를 사용하면 들로네 삼각분할에서 2차원이나 3차원 볼록 껍질을 구할 수 있습니다. 이 계산 방법은 전용 convhull 함수나 convhulln 함수를 사용한 것만큼 효율적이지 않습니다. 그러나 점 집합에 대해 delaunayTriangulation을 적용한 상태에서 볼록 껍질을 구하고자 한다면 convexHull 메서드를 사용해 기존 삼각분할에서 구하는 게 더 효율적일 수 있습니다.

alphaShape 함수를 사용하여서도 2차원이나 3차원 볼록 껍질 구할 수는 있습니다. 이때는 알파 반지름 입력 파라미터를 Inf로 설정하면 됩니다. 그러나 delaunayTriangulation과 마찬가지로, alphaShape를 사용하여 볼록 껍질을 구하는 것은 convhull이나 convhulln을 직접 사용하는 것보다 덜 효율적입니다. 이전에 만든 알파 셰이프 객체로 작업하는 경우는 예외입니다.

convhull과 convhulln을 사용하여 볼록 껍질(Convex Hull) 구하기

convhull 함수와 convhulln 함수는 점 집합을 인수로 받아 볼록 껍질 경계에 있는 점의 인덱스를 출력합니다. 점 인덱스에 기반하여 볼록 껍질을 나타내면 플로팅할 수 있을 뿐 아니라 데이터에 편리하게 액세스할 수 있습니다. 다음 예제에서는 볼록 껍질을 계산하고 나타내는 방법을 보여줍니다.

첫 번째 예제에서는 seamount 데이터셋의 2차원 점 집합을 convhull 함수에 대한 입력값으로 사용합니다.

데이터를 불러옵니다.

load seamount

점 집합의 볼록 껍질을 계산합니다.

K = convhull(x,y);

K는 볼록 껍질 주위에 반시계 방향으로 정렬된 점의 인덱스를 나타냅니다.

데이터와 데이터의 볼록 껍질을 플로팅합니다.

plot(x,y,'.','markersize',12)
xlabel('Longitude')
ylabel('Latitude')
hold on

plot(x(K),y(K),'r')

Figure contains an axes object. The axes object with xlabel Longitude, ylabel Latitude contains 2 objects of type line. One or more of the lines displays its values using only markers

볼록 껍질의 점에 점 레이블을 추가하여 K의 구조를 살펴봅니다.

[K,A] = convhull(x,y);

convhull은 2차원이나 3차원 점 집합의 볼록 껍질을 계산할 수 있습니다. 3차원 볼록 껍질을 계산하는 법을 보여주기 위해 seamount 데이터셋을 재사용할 수 있습니다.

seamount의 z 좌표 데이터인 고도(Elevation)를 포함시킵니다.

close(gcf)
K = convhull(x,y,z);

3차원에서 볼록 껍질의 경계 K는 삼각분할로 표현됩니다. 이는 삼각 패싯의 집단으로, 점 배열에 대한 인덱스로 구성된 행렬 형식을 갖습니다. 행렬 K의 각 행은 하나의 삼각형을 나타냅니다.

볼록 껍질의 경계가 삼각분할로 표현되므로 삼각분할 플로팅 함수 trisurf를 사용할 수 있습니다.

trisurf(K,x,y,z,'Facecolor','cyan')

Figure contains an axes object. The axes object contains an object of type patch.

convhull은 3차원 볼록 껍질에 의해 경계가 지정된 볼륨(체적)을 선택적으로 반환할 수 있으며, 구문은 다음과 같습니다.

[K,V] = convhull(x,y,z);

convhull 함수는 영역이나 볼륨을 계산하는 데 고려할 수 없는 꼭짓점을 제거하여 볼록 껍질의 표현을 단순화할 수 있는 옵션도 제공합니다. 예를 들어, 볼록 껍질의 경계 패싯이 동일직선상이나 동일평면상에 있는 경우 이들 패싯을 병합하여 볼록 껍질을 더 간결하게 표현할 수 있습니다. 다음 예제에서는 이 옵션을 사용하는 방법을 보여줍니다.

[x,y,z] = meshgrid(-2:1:2,-2:1:2,-2:1:2);
x = x(:);
y = y(:); 
z = z(:);

K1 = convhull(x,y,z);
subplot(1,2,1)
defaultFaceColor  = [0.6875 0.8750 0.8984];
trisurf(K1,x,y,z,'Facecolor',defaultFaceColor)
axis equal
title(sprintf('Convex hull with simplify\nset to false'))

K2 = convhull(x,y,z,'simplify',true);
subplot(1,2,2)
trisurf(K2,x,y,z,'Facecolor',defaultFaceColor)
axis equal
title(sprintf('Convex hull with simplify\nset to true'))

Figure contains 2 axes objects. Axes object 1 with title Convex hull with simplify set to false contains an object of type patch. Axes object 2 with title Convex hull with simplify set to true contains an object of type patch.

MATLAB은 더 높은 차원에서 볼록 껍질과 하이퍼볼륨을 계산할 수 있도록 convhulln 함수를 제공합니다. convhulln이 N차원을 지원할지라도, 10차원이 넘을 경우에는 필요한 메모리가 급격히 증가하기 때문에 문제를 푸는 것이 쉽지 않습니다.

convhull 함수가 convhulln보다 더 견고하고 뛰어난 성능을 제공하므로 2차원과 3차원에서는 이 함수를 사용하는 것이 좋습니다.

delaunayTriangulation 클래스를 사용하여 볼록 껍질 구하기

이 예제에서는 2차원 점 집합의 들로네 삼각분할(Delaunay Triangulation)과 이 점 집합의 볼록 껍질 간 관계를 보여줍니다.

delaunayTriangulation 클래스를 사용하면 2차원과 3차원 공간에서 들로네 삼각분할을 계산할 수 있습니다. 이 클래스는 또한 삼각분할에서 볼록 껍질을 파생시키는 convexHull 메서드도 제공합니다.

2차원에 있는 점 집합의 들로네 삼각분할을 만듭니다.

X = [-1.5 3.2; 1.8 3.3; -3.7 1.5; -1.5 1.3; 0.8 1.2; ...
      3.3 1.5; -4.0 -1.0; -2.3 -0.7; 0 -0.5; 2.0 -1.5; ...
      3.7 -0.8; -3.5 -2.9; -0.9 -3.9; 2.0 -3.5; 3.5 -2.25];

dt = delaunayTriangulation(X);

삼각분할을 플로팅하고 단일 삼각형에서만 공유되는 모서리를 강조 표시하여 볼록 껍질을 나타냅니다.

triplot(dt)

fe = freeBoundary(dt)';
hold on
plot(X(fe,1), X(fe,2), '-r', 'LineWidth',2)
hold off

Figure contains an axes object. The axes object contains 2 objects of type line.

3차원에서는, 하나의 사면체에서만 공유되는 삼각분할의 패싯이 볼록 껍질의 경계를 나타냅니다.

전용 convhull 함수를 사용하는 것이 convexHull 메서드를 기반으로 한 계산보다 일반적으로 더 효율적입니다. 그러나 다음과 같은 경우에는 삼각분할을 기반으로 하는 접근 방식이 적합합니다.

  • 점 집합에 대해 이미 delaunayTriangulation을 사용하고 있는데 볼록 껍질도 필요한 경우.

  • 점 집합에서 점을 점진적으로 추가하거나 제거해야 하고, 점을 편집한 후에 종종 볼록 껍질을 다시 계산해야 하는 경우.

alphaShape를 사용하여 볼록 껍질(Convex Hull) 구하기

이 예제에서는 alphaShape 함수를 사용하여 2차원 점 집합의 볼록 껍질을 구하는 방법을 보여줍니다.

alphaShape는 2차원이나 3차원 점 집합에서 정형화된 알파 셰이프를 구합니다. 알파 셰이프가 점 집합을 얼마나 꼭 맞게 또는 느슨하게 감싸는지 결정하는 알파 반지름을 지정할 수 있습니다. 알파 반지름을 Inf로 설정할 경우 결과로 생성되는 알파 셰이프는 점 집합의 볼록 껍질이 됩니다.

2차원 점 집합을 만듭니다.

X = [-1.5 3.2; 1.8 3.3; -3.7 1.5; -1.5 1.3; 0.8 1.2; ...
      3.3 1.5; -4.0 -1.0; -2.3 -0.7; 0 -0.5; 2.0 -1.5; ...
      3.7 -0.8; -3.5 -2.9; -0.9 -3.9; 2.0 -3.5; 3.5 -2.25];

알파 반지름이 Inf인 알파 셰이프를 사용하여 점 집합의 볼록 껍질을 계산하고 플로팅합니다.

shp = alphaShape(X,Inf);
plot(shp)

Figure contains an axes object. The axes object contains an object of type patch.

참고 항목

| | | |

관련 항목