O (n^2)보다 복셀 목록에서 인접 그래프를 빠르게 생성 하시겠습니까?

Question

나는 현재 대략 이렇게하여 "이웃 그래프를"만드는거야 : 약 N에서 실행

for every voxel 
    look at every other unseen voxel 
    check if neighbours 

이 (마이너스 N)를 제곱. 특정 수의 복셀에 대해서는 허용되지만 더 큰 목록에서는 훨씬 더 많은 시간이 걸립니다.

또 다른 순진한 해결책은 단순히 모든 것을 큰 3D 배열이나 O (n)에서 실행되지만 훨씬 많은 메모리가 소모되는 해시 맵에 저장하는 것입니다.

더 빠른 방법이 있습니까? Google에 올바른 검색어를 입력 할 수없는 것 같습니다 ...

Answer 1

octree 또는 k-d tree 구조와 같은 공간 파티셔닝 트리를보고 싶을 수 있습니다. 이러한 구조는 대개 매우 효율적으로 (O (n) 또는 O (n log n), IIRC) 구축 될 수 있으며, 가장 가까운 이웃이나 주어진 경계 상자 내의 점을 찾는 데 매우 빠른 검색을 제공합니다. 이러한 구조 중 하나를 사용하면 거대한 3D 배열을 만드는 데 드는 엄청난 메모리 비용없이 큰 성능 향상을 얻을 수 있습니다.

희망이 도움이됩니다.