1

I need to calculate the distance between the furthest vertex of a Voronoi polygon and the point that generated it. I need to calculate this distance for all Voronoi polygons.

Is there a way to do it automatically in Python?

To generate the Polygon, I used Scipi. Do you have any tips or hints for me?

Brubarn B.
  • 13
  • 2

1 Answers1

1

Something like this could work:

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


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

dists = []

for i,point in enumerate(points):

    # get nearby vertices
    ridges = np.where(vor.ridge_points == i)[0]
    vertex_set = set(np.array(vor.ridge_vertices)[ridges, :].ravel())
    region = [x for x in vor.regions if set(x) == vertex_set][0]
    region = [x for x in region if x != -1] # remove outliers
    polygon = vor.vertices[region]
    if len(polygon) < 1:
        continue

    # calc distance of every vertex to the initial point
    distances = distance.cdist([point], polygon).T
    max_dist_idx = np.argmax(distances)
    max_dist = distances[max_dist_idx]
    dists.append(max_dist)

    # just for visuals
    xvals = [point[0], polygon[max_dist_idx][0]]
    yvals = [point[1], polygon[max_dist_idx][1]]
    plt.plot(xvals,yvals,'r-')
    # do stuff with that info

plt.show()

The method to match polygons with the enclosed point was posted here: https://stackoverflow.com/a/47316980/9173710

Raphael
  • 810
  • 6
  • 18
  • Thank you for answering! I am very new to programming, so excuse me for my next question: How do I get the coordinates of the vertices? – Brubarn B. Feb 03 '22 at 13:16
  • I edited my answer, also you can read in the docs what the attributes of the Voronoi class can do: https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Voronoi.html – Raphael Feb 03 '22 at 13:51
  • The line 'idx = vor.point_region(point)' gives me an exception error; numpy.ndarray object is not callable. Do you know what that means? – Brubarn B. Feb 03 '22 at 15:09
  • I redid the code again, this time it should work! I added a plot to visualize the result! – Raphael Feb 04 '22 at 13:25
  • 1
    Thank you, everything works now!! – Brubarn B. Feb 04 '22 at 20:04