면에 조각 상수 인 2 차원 데이터 보간

Question

두 개의 변수로 설명되는 불규칙한 메쉬 - 각면을 구성하는 정점의 인덱스를 저장하는면 배열과 각 정점의 좌표를 저장하는 verts 배열 . 또한 각면에 대해 조각 별 상수로 가정되는 함수가 있으며 각 면당 값 배열 형식으로 저장됩니다.

이 데이터에서 함수 f을 생성하는 방법을 찾고 있습니다. 다음과 같은 라인을 따라 뭔가 :

faces = [[0,1,2], [1,2,3], [2,3,4] ...] 
verts = [[0,0], [0,1], [1,0], [1,1],....] 
vals = [0.0, 1.0, 0.5, 3.0,....] 

f = interpolate(faces, verts, vals) 

f(0.2, 0.2) = 0.0 # point inside face [0,1,2] 
f(0.6, 0.6) = 1.0 # point inside face [1,2,3] 

점 x,y가에서 거짓말을 해당면을 발견하고 그 얼굴에 저장된 값을 반환하는 것입니다 f(x,y)을 평가하는 수동 방법. scipy (또는 matlab)에서 이미이 기능을 구현 한 함수가 있습니까?

Answer 1

당신이 원하는 것을 할 것입니다 MATLAB에는 내장 함수가 없습니다. INPOLYGON을 suggested by Jonas으로 사용하여 알고리즘을 직접 만들 수도 있지만, 포인트가 다각형 내에 있는지 확인하기위한 몇 가지 표준 알고리즘을 사용하여 더 빠른 구현을 직접 만들 수 있습니다.

3 차원에서 선분과 삼각형 표면 집합 사이의 교차점을 찾기위한 코드를 작성한 후 this softsurfer link이 알고리즘을 구현하는 데 가장 도움이되는 것으로 나타났습니다. 제 사건은 당신보다 복잡했습니다.2D로 작업하기 때문에 세그먼트의 삼각형 평면과 교차하는 지점을 찾기위한 링크의 첫 번째 섹션을 무시할 수 있습니다.

아래 MATLAB 코드의 간단한 버전이 포함되어 있습니다. interpolate 함수는 faces, vertices 및 values 행렬을 입력으로 사용하고 지정된 삼각형 내에서 구분 값을 얻기 위해 주어진 (x, y) 점에서 계산할 수있는 함수 핸들 f을 반환합니다.

• 는 f을 평가할 때 수행됩니다 처리가 nested functionevaluate_function에 포함되어 있습니다 : 다음은이 코드의 몇 가지 기능이 있습니다. 이 함수는 interpolate에있는 다른 변수에 액세스 할 수 있으므로 삼각형 테스트에 필요한 변수가 미리 계산되어 evaluate_function이 가능한 빨리 실행됩니다.
• 삼각형이 많은 경우 포인트가 모두 내부에 있는지 테스트하는 것이 비용이 많이들 수 있습니다. 따라서 코드는 먼저 주어진 반경 (즉, 삼각형 가장 긴 다리의 길이) 내에있는 삼각형을 찾습니다. 이 근처의 삼각형 만 테스트되어 포인트가 포인트 내에 있는지 확인합니다.
• 점이 삼각형 영역 내에 있지 않으면 NaN 값이 f에 의해 반환됩니다.
  이
  • 입력 확인 :이 코드는 현재 가정합니다

  당신이 당신이 그것을 사용하는 내용에 따라에 추가 할 수있는 코드에 포함되지 않은 몇 가지가 있습니다 faces은 N x 3 행렬이고, vertices은 M 행 2 행렬이고 values은 길이 N 벡터입니다. 입력이 이러한 요구 사항을 준수하는지 확인하기 위해 오류 검사를 추가하고 그 중 하나 이상이 잘못된 경우를 나타내는 오류를 던지기를 원할 것입니다.

• 변형 삼각형 검사 :faces 및 vertices 입력에 의해 정의 된 삼각형 중 하나 이상이 축퇴 될 수 있습니다 (즉, 0 영역을 가질 수 있음). 이것은 두 개 이상의 삼각형 정점이 똑같은 점이거나 삼각형의 세 정점이 직선 상에있을 때 발생합니다. f을 평가할 때 이러한 삼각형을 무시하는 수표를 추가하고 싶을 것입니다.
• 가장자리 처리 경우 : 포인트가 둘 이상의 삼각형 영역의 가장자리로 끝날 수 있습니다. 따라서 어떤 포인트의 가치가 있는지 (예 : 가장 큰 액면가, 평균 액면가 등) 결정해야합니다. 이와 같은 가장자리의 경우 아래 코드는 faces 변수의 얼굴 목록 시작 부분에 더 가까운 얼굴 값을 자동으로 선택합니다.

  function f = interpolate(faces,vertices,values) 
  
      %# Precompute some data (helps increase speed): 
  
      triVertex = vertices(faces(:,2),:);    %# Triangles main vertices 
      triLegLeft = vertices(faces(:,1),:)-triVertex; %# Triangles left legs 
      triLegRight = vertices(faces(:,3),:)-triVertex; %# Triangles right legs 
      C1 = sum(triLegLeft.*triLegRight,2); %# Dot product of legs 
      C2 = sum(triLegLeft.^2,2);   %# Squared length of left leg 
      C3 = sum(triLegRight.^2,2);   %# Squared length of right leg 
      triBoundary = max(C2,C3);    %# Squared radius of triangle boundary 
      scale = C1.^2-C2.*C3; 
      C1 = C1./scale; 
      C2 = C2./scale; 
      C3 = C3./scale; 
  
      %# Return a function handle to the nested function: 
  
      f = @evaluate_function; 
  
      %# The nested evaluation function: 
  
      function val = evaluate_function(x,y) 
  
      w = [x-triVertex(:,1) y-triVertex(:,2)]; 
      nearIndex = find(sum(w.^2,2) <= triBoundary); %# Find nearby triangles 
      if isempty(nearIndex) 
       val = NaN;   %# Return NaN if no triangles are nearby 
       return 
      end 
      w = w(nearIndex,:); 
      wdotu = sum(w.*triLegLeft(nearIndex,:),2); 
      wdotv = sum(w.*triLegRight(nearIndex,:),2); 
      C = C1(nearIndex); 
      s = C.*wdotv-C3(nearIndex).*wdotu; 
      t = C.*wdotu-C2(nearIndex).*wdotv; 
      inIndex = find((s >= 0) & (t >= 0) & (s+t <= 1),1); 
      if isempty(inIndex) 
       val = NaN;   %# Return NaN if point is outside all triangles 
      else 
       val = values(nearIndex(inIndex)); 
      end 
  
      end 
  
  end 
  

  :
마지막으로

, 여기에 코드입니다

Answer 2

이것은 보간법이 포인트가 내부에있는 삼각형면을 찾는 것과 너무 많이 들리지 않습니다. 각 삼각형면을 테스트하는 방법은 this site을 확인하십시오. 함수는 내부에있는면을 결정하고 해당 값을 반환합니다. 물론 얼굴이 많거나이 작업을 많이하는 경우 최적화를위한 방법을 찾고 싶을 것입니다 (각 삼각형에 대해 x와 y 방향으로 가장 멀리있는 점을 저장하고 점포를 저장하십시오 예를 들어 얼굴이있는 점이 있습니다. 점이이 경계 상자 안에 있지 않으면 삼각형의 내부인지 확인하지 못할 수도 있습니다.

나는 Matlab에 내장되어있는 것을 찾거나 원하는 것을하기 위해 scipy를 발견 할 것이 틀림 없다.

Answer 3

CGAL-python 모듈을 사용하고 싶을 수 있습니다. 정확하게 기억한다면, CGAL은 삼각형 검색 기능을 제공합니다. 그러나 내장 된 표현을 사용하여 점진적으로 삼각 측량을 구성하면 가장 효율적으로 작동합니다. 빠르고 간단하게하려면 Voronoi 다이어그램 (Matlab에서이 기능은 훌륭하지 않음) 또는 단일 쿼리의 경우 모든 쿼리를 계산하여 쿼리 포인트에 가장 가까운 메쉬 정점을 찾을 수 있습니다. 거리를 구하고 최소값을 구한 다음 해당 정점을 가진 모든 삼각형을 검색합니다.

Answer 4

Matlab에는 내장형 함수 inpolygon이있어 삼각형 안에 있는지 테스트 할 수 있습니다. 나는 당신이 어떤 얼굴에 있는지를 확인할 수있는 기능을 모른다.

그런 함수를 작성하려는 경우 먼저 가장 가까운 점을 테스트 한 다음 해당 점을 찾을 때까지 정점을 공유하는 모든면에 대해 inpolygon을 계산합니다. 이것은 상당히 빨라야합니다.

Answer 5

C 코드의 잘 설명 된 래퍼 인 matplotlib.delaunay.interpolate을 살펴보십시오.
는 (그러나 class LinearInterpolator는 "순간은, 정규 직사각형의 격자 보간 지원됩니다."이 말한다)