2011-08-15 4 views
0

N-Body 및 SPH와 같은 입자 알고리즘에 관심이 있습니다. 이러한 응용 프로그램에서 중요한 단계 중 하나는 쿼리 포인트가 주어지면 반경 'h'의 지정된 구체 내에 속한 입자 을 찾는 것입니다.Octree에서 지정된 반경 내에서 범위 검색

이제 Octrees가 N 바디 또는 SPH와 같은 문제에 대한 좋은 공간 데이터 구조라고 들었습니다.

그러나 옥트리 구조 이후에 "반경 내 입자 찾기"단계가 어떻게 수행되는지 이해할 수 없습니다. 누군가가이 단계를 수행하기 위해 참고 문헌, 논문 또는 기사를 가르쳐 주시겠습니까?

답변

1

k-d trees 또한 이것에 사용할 좋은 데이터 구조이며 일반적으로 가장 가까운 이웃 검색에 사용됩니다. 옥트리가 3dPoint 개체 포함 추측

+0

예 kd 트리가 범위 검색을위한 매우 훌륭한 데이터 구조 인 것 같습니다. 고맙습니다! :디 – smilingbuddha

1

: "는 점 (P)의 반경 (3) 내의 입자의 위치가" 같이 표현 될 수있다 "모든 점 Octreecells 만지고 포함하거나 구 (중심 (P), 반경 (r))과 교차 창"에 셀이 구와 교차하는지 테스트 :

dx,dy,dz = 0; 
if (pX < minX of Cell) 
    dx = |px - minX| 
else if (px > maxX of Cell) 
    dx = |px-maxX| 
Same for other dimensions 

return (|dx,dy,dz|<=r) 
관련 문제