Tìm các vùng voronoi có chứa một danh sách các tọa độ tùy ý

Question

Tôi đang làm việc với một thuật toán, đối với mỗi lần lặp, cần tìm khu vực nào của sơ đồ Voronoi một tập hợp các điều phối arbirary thuộc về. có nghĩa là, mỗi vùng tọa độ được đặt bên trong. (Chúng ta có thể giả định rằng tất cả các tọa độ sẽ thuộc về một khu vực, nếu mà làm cho bất kỳ sự khác biệt.)

tôi không có bất kỳ mã mà làm việc trong Python, nhưng các mã giả trông giống như sau:

## 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 

Tôi biết rằng scipy.Delaunay có một hàm gọi là find_simplex, nó sẽ thực hiện khá nhiều những gì tôi muốn cho các đơn giản trong một tam giác Delaunay, nhưng tôi cần sơ đồ Voronoi, và xây dựng cả hai là thứ tôi muốn tránh.

Câu hỏi:

1. Có một thư viện của một số loại mà sẽ cho phép tôi làm điều này một cách dễ dàng?

2. Nếu không, có thuật toán hay nào mà tôi có thể xem sẽ cho phép tôi thực hiện điều này một cách hiệu quả không?

Cập nhật

giải pháp của Jamie là chính xác những gì tôi muốn. Tôi hơi xấu hổ vì tôi không tự nghĩ về điều đó ...

Answer 1

Bạn không cần tính toán các vùng Voronoi cho việc này. Theo định nghĩa, vùng Voronoi xung quanh một điểm trong tập hợp của bạn được tạo thành từ tất cả các điểm gần với điểm đó hơn bất kỳ điểm nào khác trong tập hợp. Vì vậy, bạn chỉ cần tính toán khoảng cách và tìm hàng xóm gần nhất. Sử dụng scipy của cKDTree bạn có thể làm:

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 Bây giờ nắm giữ một loạt các hình dạng (n_test, 1) với các chỉ số của các điểm trong voronoi_points gần gũi nhất với mỗi người trong số test_points của bạn.