scipy.spatial.Voronoi : 광선이 주어진 선을 통과하는 위치를 알아내는 방법?

Question

좋은 하루 모두,

나는 다음과 같은 코드 세그먼트가 :

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

NUM_OF_POINTS = 20 

points = [] 
for i in range (0, NUM_OF_POINTS): 
    points.append([randint(0, 500), randint(0, 500)]) 

points = np.array(points) 
vor = Voronoi(points) 
voronoi_plot_2d(vor) 
plt.show() 

이와 같은 보로 노이 플롯을 생성합니다

내 목표는 발견하는 곳 '광선'(선 플롯에서 벗어난 점선 또는 점선)은 주어진 선과 교차합니다 (예 : x = 500). 어떻게해야할까요?

Voronoi 개체에 이미 ridge_vertices 목록을 사용해 보았습니다. 그러나이 '광선'은 목록의 단일 꼭지점과 연관되어 있기 때문에 선 수식을 파악할 수 없습니다.

편집 :

이 나의 궁극적 인 목표이며, 주어진 에지 셀이 경계와 교차하는 지점을 찾기 위해, 비행기의 경계 주어진. 예를 들어, 왼쪽 상단 가장자리 셀과 테두리 y = -50 및 x = 525가 주어지면 빨간색 X로 표시된 점을 찾을 수 있습니다. 이에 대한 통찰력이있는 경우

그래서, 그들은 감상 할 수있다.

감사합니다.

Answer 1

1. x 및 y 좌표를 알고 있기 때문에 모서리는 간단합니다.

2. 보로 노이 다이어그램의 가장자리는 그 가장자리로 구분되는 두 개의 셀의 중심에 등거리에 있으며 자연스럽게 "광선"의 끝점을 포함합니다 (용어에서). 두 센터 점 (x1, y_1) 및 (x_2, y_2) 및 테두리의 교점이 될 (x*, y*)하자, 그 다음은 원하는 분야

(1) (x*-x_1)^2 + (y*-y_1)^2 = d^2

(2) (x*-x_2)^2 + (y*-y_2)^2 = d^2

국경에 의해 정의 되었기 때문에 x* 또는 y*을 알고 있습니다. 그러면 두 개의 방정식과 두 개의 미지수 (x* 또는 y* 및 d)가 있습니다. 당신이 y* 알고 가정 할 때, 당신은 x*에 대한 다음과 같은 솔루션에 도착 :

x* = ((y*-y_1)^2 - (y*-y_2)^2 + x_1^2 - x_2^2)/(2 * (x_1 - x_2))

---

지금 어떻게 포인트 (x_1, y_1) 및 (x_2, y_2)의 쌍을 선택하는 알아낼 수 있습니까?

첫 번째 패스로

, 나는 그것을 무력 것 :

이

(1) (많은 n 개의 * (N-1) 국경 당/2, 그렇게되지 않음) 모든 지점의 조합을 통해 반복, x*을 찾거나 각각 y*입니다.그러면 잠재 솔루션 목록 (x_1, y_1), (x_2, y_2), (x*, y*)이 표시됩니다.

(2) 각 후보 (x*, y*) 쌍에 대해 원래의 데이터 세트 집합에서 가장 가까운 이웃을 찾을 수 있습니다 (scipy.spatial.KDTree 통해 효율적). 이 점수가 (x_1, y_1) 및 (x_2, y_2)이 아닌 경우 후보 솔루션 (x*, y*)을 삭제합니다.

KD 트리에서 가장 가까운 이웃을 찾는 것은 O (n log n) (IIRC)이므로 전체 절차에서 여전히 O (n^2)입니다.