Main Content

공간 탐색

소개

MATLAB®은 들로네 삼각분할이나 일반적인 삼각분할을 사용하여 공간을 탐색하는 함수를 제공합니다. 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

이들 점으로 들로네 삼각분할(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 object. The axes object contains 37 objects of type line, text. One or more of the lines displays its values using only markers

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

이제 쿼리 점을 만들고 플롯에 추가합니다. 그런 다음 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 object. The axes object contains 30 objects of type line, text. One or more of the lines displays its values using only markers

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);

무게중심 좌표는 선형 보간을 수행하는 데 유용합니다. 이러한 좌표는 바깥쪽 단체의 각 꼭짓점에서 값을 스케일링하는 데 사용할 수 있는 가중치를 제공합니다. 자세한 내용은 산점 데이터 보간하기 항목을 참조하십시오.

참고 항목

| | | | | | | |

관련 항목