Voronoi 다이어그램의 어느 지점에서 새로운 점을 계산할 수 있습니까?

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. 내가 원하는 지점 주변의 모든 능선을 찾아 vor.ridge_points
2. 이 능선에서 능선 정점을 모두 받아 사용 :
   그래서 나는 다음과 같은 방법을 사용 (고유 한) 영역과 동일한 꼭지점 집합을 사용합니다.

결과는 : 여기

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를 사용하여 난수를 생성하는 것으로, 사용자가 수행 한 것보다 간단합니다.