scipy.spatial.Voronoi: Comment savoir où un rayon traverse une ligne donnée?

Question

Bonjour à tous,

je le segment de code suivant:

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() 

qui produit des parcelles Voronoï comme celui:

Mon but est de trouver où les « rayons » (les lignes qui sort de l'intrigue, en pointillés ou solide) se croisent avec une ligne donnée (par exemple x = 500). Comment puis-je faire cela?

J'ai déjà essayé d'utiliser la liste ridge_vertices dans l'objet Voronoi, mais ces 'rayons' ne sont associés qu'à un seul sommet dans la liste, donc je ne peux pas comprendre l'équation de ligne.

Edit:

Mon but ultime est avec ce, compte tenu des frontières du plan, pour trouver les points qui se croisent avec ces frontières pour une cellule de bord donné. Par exemple, étant donné la cellule de bord en haut à gauche, et les frontières y = -50 et x = 525, je trouverais les points marqués avec les X rouges.

Donc, si vous avez des idées à cela, ils seraient appréciés.

Merci.

Answer 1

1. Les coins sont triviaux car vous connaissez les coordonnées x et y. Les arêtes d'un diagramme de Voronoï sont équidistantes des centres des deux cellules qui sont séparées par ce bord, ce qui inclut naturellement l'extrémité d'un «rayon» (dans votre terminologie). Que les deux centres soient les points de (x1, y_1) et (x_2, y_2), et l'intersection du rayon avec la frontière être (x*, y*), alors ce qui suit est:

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

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

Vous connaissez soit x* soit y* car ils sont définis par la bordure. Ensuite, vous avez deux équations, et deux inconnues (x* ou y* et d). En supposant que vous savez y*, vous arrivez à la solution suivante pour x*:

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

---

Maintenant, comment voulez-vous savoir que des paires de points (x_1, y_1) et (x_2, y_2) choisir?

En tant que premier passage, je la force brutale il:

(1) itérer sur toutes les combinaisons de points (n * (n-1)/2 par frontière, donc pas beaucoup), trouver x* ou y*, respectivement.Cela vous donne une liste des solutions possibles.

(2) Pour chaque paire candidate (x*, y*), je trouverais les 2 plus proches voisins dans votre ensemble original de points de données (efficacement via scipy.spatial.KDTree). Si ces points ne sont pas (x_1, y_1) et (x_2, y_2), éliminez la solution candidate (x*, y*). La recherche des voisins les plus proches dans un arbre KD est O (n log n) (IIRC), donc vous êtes toujours O (n^2) pour toute la procédure.