3D 공간에서 점들을 효율적으로 관리하기 위한 해시 기반 그리드 자료구조이다.
공간 분할 ( Spatial Partitioning )
3D 공간을 균일한 크기의 셀로 나누고 각 셀은 해시값으로 인덱싱된다.
예시:
┌─────┬─────┬─────┐
│ 0,0 │ 1,0 │ 2,0 │
├─────┼─────┼─────┤
│ 0,1 │ 1,1 │ 2,1 │ (2D 예시, 실제는 3D)
├─────┼─────┼─────┤
│ 0,2 │ 1,2 │ 2,2 │
└─────┴─────┴─────┘
- 각 점은 자신이 속한 셀의 해시값으로 저장
- 동일 셀 내 여러 점들은 리스트로 관리
- 메모리 효율적 (빈 셀은 저장 안 함)
주요 동작
점 삽입
// 의사코드
Point3D p = { x, y, z };
GridCell cell =
{
int( x / cellSize ),
int( y / cellSize ),
int( z / cellSize )
};
int hash = HashFunction( cell );
grid[ hash ].Add( p );
근접 이웃 검색
// 특정 점 주변 이웃 찾기
SearchRadius = cellSize;
// 주변 27개 셀만 검색 (3x3x3)
for ( dx, dy, dz in [ -1, 0, 1 ] )
{
CheckCell( cell.x + dx, cell.y + dy, cell.z + dz );
}장점
| 장점 | 설명 |
|---|---|
| 빠른 검색 | O(1) 평균 시간 복잡도로 근접 점 검색 |
| 메모리 효율 | 점이 있는 셀만 저장 |
| 동적 추가/삭제 | 실시간으로 점 추가/제거 가능 |
| 확장성 | 대량의 점 처리에 적합 |
일반적인 사용 사례
- 충돌 감지 : 게임/시뮬레이션에서 객체 간 충돌 체크
- 파티클 시스템 : 파티클 간 상호작용 계산
- 포인트 클라우드 : 3D 스캔 데이터 처리
- 근접 이웃 검색 : 특정 반경 내 점 찾기
- 군집화 : 밀집된 점들 그룹화
성능 특성
- 검색 : O(1) ~ O(n) (셀 크기에 따라 다름)
- 삽입 : O(1)
- 삭제 : O(1)
- 메모리 : O(점의 개수)