python 효율적인 3d 보로 노이 다이어그램을 사용하여 복셀

Question

나는 좌표가 배열의 인덱스로 표시되는 복셀을 나타내는 3d 배열을 사용하여 보로 노이 다이어그램을 만들려고합니다. 예를 들어 는 :

points = np.random.random([10,3]) 
vox_len = 0.1 
lx = ly = lz = 11 
hull_space=np.zeros([lx,ly,lz],dtype=np.int16) 
hull_space.fill(-1) 
for i in range(lx): 
    for j in range(ly): 
     for k in range(lz): 
      coord = np.array([i,j,k]).astype(float)*vox_len 
      diff = points - coord 
      dist = np.sqrt(diff[:,0]**2 + diff[:,1]**2 + diff[:,2]**2) 
      closest = np.argmin(dist) 
      hull_space[i][j][k]=closest 

문제는 더 큰 배열과 코드가 매우 느린 것입니다. 나는 또한 시도했다 :

grid = np.indices((lx,ly,lz)).astype(float)*vox_len 
hull_space = np.ones([lx,ly,lz],dtype=np.int16) 
hull_space.fill(-1) 
closest_dist = np.ones(hull_space.shape) 
closest_dist.fill(999) 
for index,point in enumerate(points): 
    dist2 = (grid[0]-point[0])**2 + (grid[1]-point[1])**2 + (grid[2]-point[2])**2 
    hull_space[dist2 < closest_dist]=index 
    closest_dist[dist2 < closest_dist]=dist2[dist2 < closest_dist] 

그러나 결과는 더욱 악화되었다. scipy의 voronoi 다이어그램 방법을 알고 있지만 voronoi 영역의 가장자리를 거리 변환하는 데 voxel 이미지를 작성해야합니다. 제 목표는 모공 네트워크 모델에 사용하기 위해 얽힌 섬유 구조의 이미지를 만드는 것입니다. 보셀 방식은 모공을 만드는 데 유용합니다.

알고리즘 실행 속도를 높이려면 도움이 필요합니다. 500 포인트의 300x300x300 다이어그램의 경우 내 컴퓨터에서 약 50 분 걸립니다.

Answer 1

포인트 정렬을 시도 할 수 있습니다. 좌표를 2 진수로 처리하고 삽입하십시오. 그런 다음 두 가지 방법으로 정렬하십시오. 실제로 Cgal은 같은 알고리즘을 사용합니다.