스텐실 점프

Stencil jumping

스텐실 점프(Stencil walking)는 때때로 스텐실 워킹(Stencil walking)이라고 불리며, 구조화된 메쉬에 대해 주어진 점을 둘러싸는 격자 요소를 찾기 위한 알고리즘이다.간단히 말해서, 점 및 구조화된 망사, 이 알고리즘은 주어진 점을 둘러싸는 그리드 요소를 찾는 데 도움이 될 것이다.

이 알고리즘은 두 개의 메쉬가 서로 다른 내부에 하나씩 놓여 있을 때 구멍 절단 및 보간 측면에서 CFD(Computing Fluid Dynamics)에서 광범위하게 사용된다.이 문제의 다른 변형은 다음과 같은 것일 것이다: 한 장소를 주어진다면, 위도와 경도는 어느 곳에 있는가?짐승의 힘 알고리즘은 모든 망사 점으로부터 점의 거리를 찾아내고 어느 것이 가장 작은지 볼 수 있을 것이다.또 다른 접근법은 스텐실 점프 알고리즘과 비슷한 속도로 결과를 산출하는 바이너리 검색 알고리즘을 사용하는 것이다.바이너리 검색과 스텐실 점프 알고리즘의 조합은 가능한 최소 시간에서 최적의 결과를 산출할 것이다.

원칙

O 지점은 그리드 요소 ABCD 내부에 있다.

단순성을 위해 그림과 같이 2차원 메쉬의 격자 요소 하나를 고려하고 내부에 점 O를 고려하십시오.그리드 요소의 정점은 A, B, C 및 D로 표시되며 벡터 AB, BC, CD, DA, OA, OB, OC 및 OD가 표시된다.OA와 AB의 교차 제품은 화면에서 나오는 평면에 수직으로 벡터를 산출한다.우리는 교차 제품의 크기가 양이라고 말한다.OB와 BC, OC와 CD, 그리고 OD와 DA의 교차 제품이 모두 긍정적이라는 것이 관찰될 것이다.

O 지점은 그리드 요소 ABCD 외부에 있다.

요점이 외부에 있을 때는 그렇지 않다.여기서 우리는 모든 교차 제품이 긍정적이지 않다는 것을 알 수 있다.이것은 알고리즘의 주요 시험 기준이다.

앞으로 어떻게 나아가는가?

알고리즘은 시작하려면 추측 그리드 요소가 필요하다.격자 요소는 A라고 하는 한 점의 위치에 의해 찾을 수 있다.다른 포인트는 후속 포인트를 얻으면 자동으로 위치할 수 있다.필요한 교차 제품은 주문에서 찾을 수 있다.

  1. OA × AB
  2. OB × BC
  3. OC × CD
  4. OD × DA

이러한 교차 제품은 각각 하나씩 점검되며(표시된 순서대로) 음이 먼저 된다.OA × AB가 먼저 음수가 되면 다음 추측은 DA를 따라 한 단계 앞서야 한다.OB × BC가 먼저 음수인 경우 AB를 따라 한 단계 이동하여 다음 추측 등을 찾아낸다.

알고리즘은 모든 교차 제품이 양성인 정확한 그리드 요소에 수렴할 것이다.

참고 항목

참조

  • Rudy A. Johnson; Davy M. Belk (1993). "A MULTIGRID APPROACH TO EMBEDDED-GRID SOLVERS" (PDF (Fee required)). Technical Reports: USAF, Wright Lab., Eglin AFB. AIAA-1993-769. Retrieved 2007-05-31.
  • E.G. Paterson; R.V. Wilson; F. Stern (May 1998). CFDSHIP-IOWA and Steady Flow RANS Simulation of DTMB Model 5415 (PDF). 1st Symposium on Marine Applications of CFD. p. 5. Archived from the original (PDF) on October 27, 2004. Retrieved 2007-05-31.
  • Prewitt, Nathan C; Belk, Davy M; Shyy, Wei (2000). "Parallel computing of overset grids for aerodynamic problems with moving objects". Progress in Aerospace Sciences. 36 (2): 117. Bibcode:2000PrAeS..36..117P. doi:10.1016/S0376-0421(99)00013-5.

외부 링크