Rasgele koordinatların listesini içeren voronoi bölgelerini bulma

Question

Her yinelemede, bir Voronoi diyagramının hangi bölümünün bir dizi arbirary koordinatının ait olduğunu bulması gereken bir algoritma ile çalışıyorum. Yani, hangi koordinatın hangi bölgede olduğu bulunur.

henüz Python çalışan herhangi bir kod yok (. Biz herhangi bir değişiklik olup olmadığını tüm koordinatlar, bir bölgeye ait olacaktır varsayabiliriz), ancak sahte kod şöyle görünür:

## 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'ın bir Delaunay üçgenlemesinde simplices için istediğim şeyi yapacak olan find_simplex adlı bir işlevi olduğunu biliyorum, ancak Voronoi diyagramına ihtiyacım var ve her ikisini de yapmak istemiyorum.

Sorular:

1. bana kolayca yapmanızı sağlayacak bir tür kütüphane var?

2. Değilse, bakabileceğim iyi bir algoritma var mı, bunu verimli bir şekilde yapalım mı?

Güncelleme

Jamie'nin çözüm tam olarak istediğim şey. Bu konuda kendimi düşünmüyorsam biraz utandım ...

Answer 1

Aslında bunun için Voronoi bölgelerini hesaplamanıza gerek yok. Tanım olarak, Voronoi bölgesi, kümenizdeki bir noktanın etrafında, bu noktaya kümedeki herhangi bir noktadan daha yakın olan tüm noktalardan oluşur. Böylece sadece mesafeleri hesaplamanız ve en yakın komşuları bulmanız yeterlidir. Yapabileceğin scipy en cKDTree kullanma:

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 Şimdi test_points her birine en yakın voronoi_points noktaların indeksleri ile şekil (n_test, 1) bir dizi tutar.