영역 경계의 유형

볼록 껍질(Convex Hull)과 비볼록 다각형(Nonconvex Polygon)

N차원 공간에 있는 점 집합의 모든 점을 감싸는 가장 작은 볼록 영역이 볼록 껍질입니다. 2차원 점 집합을 페그보드(나무못 꽂는 판)의 페그(못)로 간주할 경우, 고무 밴드를 사용하여 모든 페그를 감싸는 방식으로 이 점 집합의 볼록 껍질을 만들 수 있습니다.

rng('default')
x = rand(20,1);
y = rand(20,1);
plot(x,y,'r.','MarkerSize',10)
hold on
k = convhull(x,y);
plot(x(k),y(k))
title('The Convex Hull of a Set of Points')
hold off

볼록 다각형은 오목한 꼭짓점이 없는 다각형입니다. 예를 들면 다음과 같습니다.

x = rand(20,1);
y = rand(20,1);
k = convhull(x,y);
plot(x(k),y(k))
title('Convex Polygon')

점 집합의 비볼록 경계를 만들 수도 있습니다. 위의 볼록 껍질을 축소하고 줄이면 다음처럼 오목한 꼭짓점이 있는 비볼록 다각형으로 모든 점을 감쌀 수 있습니다.

k = boundary(x,y,0.9);
plot(x(k),y(k))
title('Nonconvex Polygon')

볼록 껍질은 다양하게 응용할 수 있습니다. 경계가 지정된 영역의 상한을 점 집합의 볼록 껍질 평면에 있는 이산 점 집합으로 구할 수 있습니다. 볼록 껍질은 더 복잡한 다각형이나 다면체의 표현을 단순화합니다. 예를 들어, 2개의 비볼록 바디가 교차하는지를 확인해야 하는 경우, 아래와 같은 일련의 빠른 기각 단계를 적용하여 바디 전체를 교차 확인하는 맹점을 피할 수 있습니다.

• 각 바디 둘레의 축 정렬 경계 상자가 교차하는지 확인합니다.

• 이러한 경계 상자가 교차하는 경우 각 바디의 볼록 껍질을 계산하고 이 볼록 껍질이 교차하는지 확인할 수 있습니다.

볼록 껍질이 교차하지 않으면 좀 더 종합적인 교차 테스트를 수행하지 않아도 되므로 수고가 줄어듭니다.

볼록 껍질과 비볼록 다각형은 비교적 단순한 경계를 나타내는 편리한 방법이지만, 이들은 사실상 알파 셰이프라고 불리는 일반 기하학 구조의 한 형태입니다.

알파 셰이프

점 집합의 알파 셰이프는 볼록 껍질(Convex Hull)의 일반화이며 들로네 삼각분할(Delaunay Triangulation)의 부분 그래프입니다. 즉, 볼록 껍질은 알파 셰이프의 한 유형일 뿐이며, 알파 셰이프 전체 집단은 지정된 점 집합에 대한 들로네 삼각분할에서 파생될 수 있습니다.

rng(4)
x = rand(20,1);
y = rand(20,1);
plot(x,y,'r.','MarkerSize',20)
hold on
shp = alphaShape(x,y,100);
plot(shp)
title('Convex Alpha Shape')
hold off

볼록 껍질과 달리, 알파 셰이프는 세부 표시 수준을 제어하거나 경계를 점 주위에 어느 정도로 맞출지 제어하는 파라미터를 갖습니다. 이 파라미터를 알파 또는 알파 반지름이라고 합니다. 알파 반지름을 0에서 Inf까지 다양하게 지정하면, 지정된 점 집합에 고유한 여러 알파 셰이프 세트가 생성됩니다.

plot(x,y,'r.','MarkerSize',20)
hold on
shp = alphaShape(x,y,.5);
plot(shp)
title('Nonconvex Alpha Shape')
hold off

알파 반지름을 다양하게 지정할 경우 구멍을 포함하거나 포함하지 않는 여러 영역으로 구성된 알파 셰이프가 생성될 수도 있습니다. 그러나 MATLAB®의 alphaShape 함수는 항상 정형화된 알파 셰이프를 반환하며, 점, 모서리, 면이 고립(Isolated)되거나 미완(Dangling) 상태가 되지 않도록 합니다.

plot(x,y,'r.','MarkerSize',20)
hold on
shp = alphaShape(x,y);
plot(shp)
title('Alpha Shape with Multiple Regions')
hold off

참고 항목

convhull | alphaShape

관련 항목

• delaunayTriangulation 클래스 사용하기
• 삼각분할 행렬 형식