임의의 좌표 목록을 포함하는 보로 노이 영역을 찾는 것

Question

나는 각각의 반복에 대해 보 로리 오코 다이어그램의 어떤 영역에 얼버리 코디네이트 세트가 속해야 하는지를 알아야하는 알고리즘으로 작업하고 있습니다. 즉, 각 좌표가있는 영역이 그 안에 있습니다.

가 아직 파이썬에서 작동 코드가없는 (. 우리는 어떤 차이가있는 경우 모든 좌표가 영역에 속하는 것으로 가정 할 수있다)하지만, 의사 코드는 다음과 같이 보입니다 :

을

## we are in two dimensions and we have 0<x<1, 0<y<1. 

for i in xrange(1000): 
    XY = get_random_points_in_domain() 
    XY_candidates = get_random_points_in_domain() 
    vor = Voronoi(XY) # for instance scipy.spatial.Voronoi 
    regions = get_regions_of_candidates(vor,XY_candidates) # this is the function i need 

    ## use regions for something 

scipy.Delaunay에는 find_simplex라는 함수가 있습니다.이 함수는 Delaunay 삼각 분할에서 simplices에 대해 원하는 작업을 수행하지만 Voronoi 다이어그램이 필요합니다. 두 가지 모두를 구축하는 것은 피하고 싶은 것입니다.

질문 :

1. 내가 쉽게 할 수 있도록 몇 가지 종류의 라이브러리가 있습니까?

2. 그렇지 않다면 효율적으로 처리 할 수있는 좋은 알고리즘이 있습니까?

업데이트

제이미의 솔루션은 내가 원하는 정확히입니다. 나는 다소 혼란 스럽다. 비록 내가 직접 생각하지 않았다. ...

Answer 1

실제로 이것을 위해 보로 노이 지역을 계산할 필요는 없다. 정의에 따르면, 세트의 한 지점 주위의 보로 노이 지역은 세트의 다른 지점보다 해당 지점에 가까운 모든 지점으로 구성됩니다. 따라서 거리를 계산하고 가장 가까운 이웃을 찾아야합니다. 당신이 할 수 scipy의 cKDTree 사용 :

import numpy as np 
from scipy.spatial import cKDTree 

n_voronoi, n_test = 100, 1000 

voronoi_points = np.random.rand(n_voronoi, 2) 
test_points = np.random.rand(n_test, 2) 

voronoi_kdtree = cKDTree(voronoi_points) 

test_point_dist, test_point_regions = voronoi_kdtree.query(test_points, k=1) 

test_point_regions는 이제 test_points의 각각에 가장 가까운 voronoi_points에있는 점의 인덱스와 모양 (n_test, 1)의 배열을 보유하고 있습니다.