ボロノイ図のどのサイトで新しい点が計算されますか？

Question

私はM点のボロノイ図を示すための小さなスクリプトを書いたthis tutorialから。私はscipy.spatialを使用します。

私は飛行機の新しいポイントを与え、このポイントはボロノイ図のどのサイトにあると言いたいですか？出来ますか？ボロノイ図の概念によって

import random 
import numpy as np 
import matplotlib.pyplot as plt 
from scipy.spatial import Voronoi, voronoi_plot_2d 

N = 70 
M = 10 

Matrix = [(random.random()*100,random.random()*100) for x in range(M)] 
points = np.array(Matrix) 


vor = Voronoi(points) 
print(vor.ridge_vertices) 

voronoi_plot_2d(vor) 
plt.show() 

Answer 1

、新しいポイントPは、元の点のうちPに最も近い点によって生成されるために属するセル：

は、これは私のコードです。この点を見つけることは、距離の単純な最小化である：

point_index = np.argmin(np.sum((points - new_point)**2, axis=1)) 

はしかし、あなたは地域を見つけたいです。 vor.regionsの地域は、残念ながらvor.pointsと同じ順番ではありません（なぜ、各地点に地域があるべきなのかはわかりません）。

だから私は、次のアプローチを使用：

1. は用セット
2. ルックとして、これらの尾根から尾根の頂点のすべてを取るvor.ridge_points
3. を使用して、私がしたい点の周りのすべての稜線を探します（一意の）領域と同じセットの頂点を持つ。

結果：

はここ

M = 15 
points = np.random.uniform(0, 100, size=(M, 2)) 
vor = Voronoi(points) 
voronoi_plot_2d(vor) 

new_point = [50, 50] 
plt.plot(new_point[0], new_point[1], 'ro') 

point_index = np.argmin(np.sum((points - new_point)**2, axis=1)) 
ridges = np.where(vor.ridge_points == point_index)[0] 
vertex_set = set(np.array(vor.ridge_vertices)[ridges, :].ravel()) 
region = [x for x in vor.regions if set(x) == vertex_set][0] 

polygon = vor.vertices[region] 
plt.fill(*zip(*polygon), color='yellow') 
plt.show() 

はデモである：それは無制限であれば地域の着色が不正確になること

注意。これは、領域発見アルゴリズムではなく、単純な色付けアプローチの欠陥です。無制限の領域を色付けする正しい方法については、Colorize Voronoi Diagramを参照してください。

脇に：乱数を生成するためにNumPyを使用しました。これはあなたが行ったより簡単です。