Main Content

이 번역 페이지는 최신 내용을 담고 있지 않습니다. 최신 내용을 영문으로 보려면 여기를 클릭하십시오.

공간 탐색

소개

MATLAB®은 들로네 삼각분할(Delaunay Triangulation)이나 일반적인 삼각분할을 사용하여 공간을 탐색하는 함수를 제공합니다. MATLAB에서 지원하는 탐색 쿼리는 다음과 같습니다.

  • 최근접이웃 탐색 - 최근접 이웃 탐색(Closest-point Search) 또는 근접 탐색(Proximity Search)이라고도 합니다.

  • 점위치(Point-location) 탐색 - PIT(Point-In-Triangle) 탐색 또는 PIS(Point-In-Simplex) 탐색이라고도 합니다. 여기서 단체(Simplex)는 삼각형, 사면체, 또는 그 이상 차원의 다면체를 의미합니다.

유클리드 공간(Euclidean Space)에 있는 점 집합 X와 쿼리 점 q가 주어진 경우, 최근접이웃 탐색은 X 내에서 X의 어떤 점보다도 q에 더 가까운 점 p를 찾습니다. X의 삼각분할이 주어진 경우, 점위치 탐색은 쿼리 점 q를 포함하는 삼각형이나 사면체를 찾습니다. 이러한 메서드는 들로네 삼각분할과 일반적인 삼각분할 모두에 사용 가능하므로 점 데이터 수정 후 들로네 기준(Delaunay criterion)을 위반하는 경우에도 이들 메서드를 사용할 수 있습니다. 또한, 행렬 형식으로 표현된 일반적인 삼각분할을 탐색할 수도 있습니다.

MATLAB은 N차원에서 이러한 탐색 방식을 지원하지만, 일반적으로 차원 수가 3차원을 넘어 확장되면 정확한 공간 탐색을 기대할 수 없습니다. 따라서 최대 10차원까지의 대규모 문제를 풀어야 할 경우에는 근삿값을 찾는 대체 탐색 방법을 고려해야 합니다.

최근접이웃 탐색

MATLAB에는 문제의 차원 수에 따른 최근접이웃 계산 방식이 여러 개 있습니다.

  • 2차원 탐색과 3차원 탐색의 경우, triangulation 클래스에서 제공하고 delaunayTriangulation 클래스에서 상속하는 nearestNeighbor 메서드를 사용합니다.

  • 4차원 이상의 경우, 삼각분할을 생성하는 delaunayn 함수와 탐색을 수행하는 상호 보완적인 dsearchn 함수를 사용합니다. 이러한 N차원 함수는 2차원과 3차원을 지원하지만, 삼각분할 탐색 메서드만큼 보편적이거나 효율적이지는 않습니다.

이 예제에서는 delaunayTriangulation을 사용하여 2차원에서 최근접이웃 탐색을 수행하는 방법을 보여줍니다.

먼저 15개의 임의 점 집합을 만듭니다.

X = [3.5 8.2; 6.8 8.3; 1.3 6.5; 3.5 6.3; 5.8 6.2; 8.3 6.5;...
    1 4; 2.7 4.3; 5 4.5; 7 3.5; 8.7 4.2; 1.5 2.1; 4.1 1.1; ...
    7 1.5; 8.5 2.75];

점을 플로팅하고 주석을 추가하여 ID 레이블을 표시합니다.

plot(X(:,1),X(:,2),'ob')
hold on
vxlabels = arrayfun(@(n) {sprintf('X%d', n)}, (1:15)');
Hpl = text(X(:,1)+0.2, X(:,2)+0.2, vxlabels, 'FontWeight', ...
  'bold', 'HorizontalAlignment','center', 'BackgroundColor', ...
  'none');
hold off

Figure contains an axes. The axes contains 16 objects of type line, text.

이들 점으로 들로네 삼각분할(Delaunay Triangulation)을 만듭니다.

dt = delaunayTriangulation(X);

쿼리 점을 만들고, nearestNeighbor 메서드를 사용하여 각 쿼리 점에 대응하는 X에서의 최근접이웃 인덱스를 구합니다.

numq = 10;
rng(0,'twister');
q = 2+rand(numq,2)*6;
xi = nearestNeighbor(dt, q);

플롯에 쿼리 점을 추가하고, 각 쿼리 점과 이에 대한 최근접이웃을 잇는 선분을 추가합니다.

xnn = X(xi,:);

hold on
plot(q(:,1),q(:,2),'or');
plot([xnn(:,1) q(:,1)]',[xnn(:,2) q(:,2)]','-r');

vxlabels = arrayfun(@(n) {sprintf('q%d', n)}, (1:numq)');
Hpl = text(q(:,1)+0.2, q(:,2)+0.2, vxlabels, 'FontWeight', ...
     'bold', 'HorizontalAlignment','center', ...
     'BackgroundColor','none');

hold off

Figure contains an axes. The axes contains 37 objects of type line, text.

3차원에서 최근접이웃 탐색을 수행하는 것은 delaunayTriangulation을 기반으로 한 2차원 예제의 직접적인 연장선상에 있습니다.

4차원 이상의 경우, 다음 예제에 표시된 대로 delaunayn 함수와 dsearchn 함수를 사용합니다.

4차원에서 임의의 샘플 점을 만들고 delaunayn을 사용하여 점을 삼각분할합니다.

X = 20*rand(50,4) -10;
tri = delaunayn(X);
쿼리 점을 만들고, 각 쿼리 점에 대해 dsearchn 함수를 사용하여 X에서의 최근접이웃 인덱스를 구합니다.
q = rand(5,4);
xi = dsearchn(X,tri, q)
nearestNeighbor 메서드와 dsearchn 함수를 사용하면 각 쿼리 점과 해당 최근접이웃 점 사이의 유클리드 거리를 선택적 인수로 반환할 수 있습니다. 4차원 예제에서는 다음과 같이 거리 dnn을 계산할 수 있습니다.
[xi,dnn] = dsearchn(X,tri, q)

점위치(Point-Location) 탐색

점위치 탐색은 쿼리 점이 들어 있는 삼각형, 사면체 등의 단체(Simplex)를 찾는 삼각분할 탐색 알고리즘입니다. 최근접이웃 탐색과 마찬가지로 점위치 탐색을 위해서도 MATLAB에는 문제의 차원 수에 따른 몇 가지 접근 방식이 있습니다.

  • 2차원과 3차원의 경우, triangulation 클래스에서 제공하고 delaunayTriangulation 클래스에서 상속하는 pointLocation 메서드를 사용한 클래스 기반 접근 방식을 사용합니다.

  • 4차원 이상의 경우, 삼각분할을 생성하는 delaunayn 함수와 점위치 탐색을 수행하는 상호 보완적인 tsearchn 함수를 사용합니다. 이러한 N차원 함수는 2차원과 3차원을 지원하지만, 삼각분할 탐색 메서드만큼 보편적이거나 효율적이지는 않습니다.

이 예제에서는 delaunayTriangulation 클래스를 사용하여 2차원에서 점 위치 탐색을 수행하는 방법을 보여줍니다.

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

X = [3.5 8.2; 6.8 8.3; 1.3 6.5; 3.5 6.3; 5.8 6.2; ...
     8.3 6.5; 1 4; 2.7 4.3; 5 4.5; 7 3.5; 8.7 4.2; ...
     1.5 2.1; 4.1 1.1; 7 1.5; 8.5 2.75];

삼각분할을 만들고, 삼각형 ID 레이블이 삼각형의 내심에 표시되도록 삼각분할을 플로팅합니다.

 dt = delaunayTriangulation(X);
triplot(dt);

hold on
ic = incenter(dt);
numtri = size(dt,1);
trilabels = arrayfun(@(x) {sprintf('T%d', x)}, (1:numtri)');
Htl = text(ic(:,1), ic(:,2), trilabels, 'FontWeight', ...
      'bold', 'HorizontalAlignment', 'center', 'Color', ...
      'blue');
hold off

Figure contains an axes. The axes contains 19 objects of type line, text.

이제 쿼리 점을 만들고 플롯에 추가합니다. 그런 다음 pointLocation 메서드를 사용하여 각 쿼리 점을 둘러싸는 삼각형의 인덱스를 구합니다.

q = [5.9344    6.2363;
    2.2143    2.1910;
    7.0948    3.6615;
    7.6040    2.2770;
    6.0724    2.5828;
    6.5464    6.9407;
    6.4588    6.1690;
    4.3534    3.9026;
    5.9329    7.7013;
    3.0271    2.2067];

hold on; 
plot(q(:,1),q(:,2),'*r'); 
vxlabels = arrayfun(@(n) {sprintf('q%d', n)}, (1:10)');
Hpl = text(q(:,1)+0.2, q(:,2)+0.2, vxlabels, 'FontWeight', ...
      'bold', 'HorizontalAlignment','center', ... 
      'BackgroundColor', 'none');
hold off

Figure contains an axes. The axes contains 30 objects of type line, text.

ti = pointLocation(dt,q);

3차원에서 점 위치 탐색을 수행하는 것은 delaunayTriangulation을 사용하여 2차원에서 점 위치 탐색을 수행하는 것의 직접적인 연장선상에 있습니다.

4차원 이상의 경우, 다음 예제에 표시된 대로 delaunayn 함수와 tsearchn 함수를 사용합니다.

4차원에서 임의의 샘플 점을 만들고 delaunayn을 사용하여 이를 삼각분할합니다.

X = 20*rand(50,4) -10;
tri = delaunayn(X);
쿼리 점을 여러 개 만들고 tsearchn 함수를 사용하여 바깥쪽 단체에 대한 인덱스를 구합니다.
q = rand(5,4);
ti = tsearchn(X,tri,q)
pointLocation 메서드와 tsearchn 함수를 사용하면 무게중심 좌표를 선택적 인수로 반환할 수 있습니다. 4차원 예에서는 다음과 같이 무게중심 좌표를 계산할 수 있습니다.
[ti,bc] = tsearchn(X,tri,q)
무게중심 좌표는 선형 보간을 수행하는 데 유용합니다. 이러한 좌표는 바깥쪽 단체의 각 꼭짓점에서 값을 스케일링하는 데 사용할 수 있는 가중치를 제공합니다. 자세한 내용은 산점 데이터 보간하기 항목을 참조하십시오.

참고 항목

| | | | | | | |

관련 항목