보로노이 다이어그램

보로노이 다이어그램 (Voronoi Diagrams)

점들의 집합을 영역으로 나누는 보로노이 다이어그램을 Octave로 그리고, 각 영역의 면적과 점 포함 여부를 어떻게 계산하는지 소개할게요.

출처: 문서

본문

N차원 공간의 점들 집합 s에 대한 보로노이 다이어그램(Voronoi tessellation)은, v(p)(p가 s의 원소인 테셀레이션의 한 분할) 안의 모든 점들이 s의 다른 어떤 점보다 p에 더 가깝도록 N차원 공간을 테셀레이션하는 것이에요. 보로노이 다이어그램은 점 집합의 Delaunay 삼각분할과 관련이 있는데, 보로노이 테셀레이션의 꼭짓점이 Delaunay 테셀레이션의 단체(simplex) 외접원의 중심이기 때문이에요.

voronoi

voronoi (x, y)
voronoi (x, y, options)
voronoi (…, "linespec")
voronoi (hax, …)
h = voronoi (…)
[vx, vy] = voronoi (…)

점 (x, y)의 보로노이 다이어그램을 플로팅해요. 무한대에 점이 있는 보로노이 면(facet)은 그리지 않아요.

options 인자는 문자열 또는 문자열 셀 배열이어야 하며, 밑바탕의 qhull 명령에 전달되는 옵션을 담아요. 자세한 내용은 Qhull 라이브러리 문서 http://www.qhull.org/html/qh-quick.htm#options를 참고하세요.

"linespec"이 주어지면 플롯의 색과 선 스타일을 설정하는 데 사용돼요.

축 그래픽 핸들 hax가 주어지면 새 그림이 아니라 지정된 축에 보로노이 다이어그램을 그려요.

출력 인자를 하나 요청하면 보로노이 다이어그램을 플로팅하고 플롯의 그래픽 핸들 h를 반환해요.

[vx, vy] = voronoi (…)는 다이어그램을 플로팅하는 대신 보로노이 꼭짓점을 반환해요.

x = rand (10, 1);
y = rand (size (x));
h = convhull (x, y);
[vx, vy] = voronoi (x, y);
plot (vx, vy, "-b", x, y, "o", x(h), y(h), "-g");
legend ("", "points", "hull");

See also: voronoin, delaunay, convhull.

voronoin

[C, F] = voronoin (pts)
[C, F] = voronoin (pts, options)

N차원 보로노이 면을 계산해요. 크기 [n, dim]의 입력 행렬 pts는 차원 dim인 공간의 n개 점을 담아요.

C는 보로노이 면의 점을 담아요. F 목록은 각 면에 대해 보로노이 점의 인덱스를 담아요.

두 번째 선택 인자는 문자열 또는 문자열 셀 배열이어야 하며 밑바탕의 qhull 명령에 전달되는 옵션을 담아요. 자세한 내용은 Qhull 라이브러리 문서를 참고하세요.

기본 옵션은 입력의 차원에 따라 달라져요.

2-D와 3-D: options = {"Qbb"}
4-D 이상: options = {"Qbb", "Qx"}

options가 없거나 []이면 기본 인자를 사용해요. 그 외에는 options가 기본 인자 목록을 대체해요. 사용자 옵션을 기본값에 추가하려면 options에 기본 인자를 반복해야 해요. 인자를 전달하지 않으려면 널 문자열을 사용해요.

See also: voronoi, convhulln, delaunayn.

voronoi 사용 예시는 다음과 같아요.

rand ("state",9);
x = rand (10,1);
y = rand (10,1);
tri = delaunay (x, y);
[vx, vy] = voronoi (x, y, tri);
triplot (tri, x, y, "b");
hold on;
plot (vx, vy, "r");

그 결과는 Figure 30.3에서 볼 수 있어요. 그림에서 삼각형 하나의 외접원이 추가되어 Delaunay 테셀레이션과 보로노이 다이어그램의 관계를 더 명확히 보여줘요.

보로노이 다이어그램 면의 크기에 대한 추가 정보와, 점 집합의 어떤 점이 다각형 안에 있는지는 각각 polyarea와 inpolygon 함수로 얻을 수 있어요.

polyarea

a = polyarea (x, y)
a = polyarea (x, y, dim)

삼각형 방법으로 다각형의 면적을 구해요.

변수 x와 y는 꼭짓점 쌍을 정의하므로 같은 형태여야 해요. 벡터 또는 배열일 수 있어요. 배열이면 x와 y의 열을 따로 처리하고 각각에 대해 면적을 반환해요.

선택 인자 dim이 주어지면 polyarea는 배열 x, y의 이 차원을 따라 동작해요.

polyarea 사용 예시는 다음과 같아요.

rand ("state", 2);
x = rand (10, 1);
y = rand (10, 1);
[c, f] = voronoin ([x, y]);
af = zeros (size (f));
for i = 1 : length (f)
  af(i) = polyarea (c (f {i, :}, 1), c (f {i, :}, 2));
endfor

꼭짓점이 무한대에 있는 보로노이 면은 무한 면적을 가져요. 사각형에 대한 단순화된 polyarea 버전은 rectint로 사용할 수 있어요.

rectint

area = rectint (a, b)

사각형 또는 N-D 상자들의 교차 영역·부피를 계산해요. a의 사각형과 b의 사각형 사이의 교차 면적을 계산해요. N차원 상자를 지원하며, 이 경우 차원 수에 따라 부피(초부피)를 계산해요.

2차원 사각형은 [xpos ypos width height]로 정의되는데, xpos와 ypos는 왼쪽 아래 모서리의 위치예요. 각 차원의 최솟값 좌표 다음에 해당 차원의 상자 길이가 오는 더 높은 차원도 지원돼요. 예: [xpos ypos zpos kpos … width height depth k_length …].

a와 b의 각 행은 사각형을 정의하고, 둘 다 여러 사각형을 정의하면 출력 area는 행렬이며 i번째 행은 a의 i번째 행에, j번째 열은 b의 j번째 행에 대응돼요.

See also: polyarea.

inpolygon

in = inpolygon (x, y, xv, yv)
[in, on] = inpolygon (x, y, xv, yv)

꼭짓점 (xv, yv)로 정의된 다각형에 대해 점 (x, y)가 안쪽(또는 경계)에 있으면 true를, 그렇지 않으면 false를 반환해요.

입력 변수 x와 y는 같은 차원이어야 해요.

선택 출력 on은 점이 정확히 다각형 가장자리 위에 있으면 true, 그렇지 않으면 false를 반환해요.

See also: delaunay.

inpolygon 사용 예시는 다음과 같아요.

randn ("state", 2);
x = randn (100, 1);
y = randn (100, 1);
vx = cos (pi * [-1 : 0.1: 1]);
vy = sin (pi * [-1 : 0.1 : 1]);
in = inpolygon (x, y, vx, vy);
plot (vx, vy, x(in), y(in), "r+", x(!in), y(!in), "bo");
axis ([-2, 2, -2, 2]);

그 결과는 Figure 30.4에서 볼 수 있어요.

더 알아보기

Delaunay 삼각분할은 Delaunay Triangulation 항목을 참고하세요.
볼록 껍질은 Convex Hull 항목을 함께 보면 좋아요.