영역 경계의 유형
볼록 껍질(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