그리드에서 입자 위치를 저장하는 알고리즘

Question

입자 분포가 있습니다. 즉, N 입자의 위치를 ​​나타내는 3D 배열 x, y 및 z이 있습니다. 내 도메인을 셀로 나눕니다. 셀에 얼마나 많은 입자가 있는지 알 수있는 알고리즘을 프로그램하고 싶습니다. 너무 많은 메모리를 사용하지 않는 것을 찾고 있습니다. 입자의 분포가 1 차원이면 똑똑한 아이디어는 x으로 입자를 정렬하는 것입니다. 이렇게하면 모든 셀에 대해 더 작은 숫자의 x을 가진 입자 만 셀 안에 저장하면됩니다. 예를 들어, 나는 7 번째 파티클이 i에 속하는 더 작은 숫자의 x 인 파티클임을 안다. 따라서 셀 i에 0에서 7까지의 입자를 찾아야합니다.

질문 : 어떻게 이것을 3D로 확장 할 수 있습니까? 또는 체인 메쉬를 어떻게 만들 수 있습니까?

Answer 1

이것은 사소한 문제는 아닙니다. 일반적으로 R-trees과 실제로 Spatial databases을 볼 수 있습니다.

Answer 2

나는 당신의 문제가 훨씬 쉽게 해결 될 수 있다고 생각합니다.

'세포'의 3D 배열을 만드십시오. 입자를 반복하고 셀의 현재 입자가 증가하는 값이 속합니다.

샘플 코드 :

cells = int[X][Y][Z] 
for p in particles: 
    cx = cast_to_int((p.x/maxX) * X) 
    cy = cast_to_int((p.y/maxY) * Y) 
    cz = cast_to_int((p.z/maxZ) * Z) 
    cells[cx][cy][cz]++ 

UPD은 모든 셀들이 동일한 크기의 대응이있는 경우에만 작동한다 (즉, X1 = X2 = XN, Y1 = Y2 = YN ...).