4

I think my questions has something in common with this question or others, but anyway, mine is not specifically about them.

I would like, after having found the voronoi tessallination for certain points, be able to check where other given points sit within the tessellination. In particular:

Given say 50 extra-points, I want to be able to count how many of these extra points each voronoi cell contains.

My MWE

from scipy.spatial import ConvexHull, Voronoi, voronoi_plot_2d
import matplotlib.pyplot as plt

points = [[0,0], [1,4], [2,3], [4,1], [1,1], [2,2], [5,3]]
#voronoi
vor = Voronoi(points)
voronoi_plot_2d(vor)
plt.show()

voronoi

Now I am given extra points

extraPoints = [[0.5,0.2], [3, 0], [4,0],[5,0], [4,3]]
# In this case we have that the first point is in the bottom left, 
# the successive three are in the bottom right and the last one
# is in the top right cell.

I was thinking to use the fact that you can get vor.regions or vor.vertices, however I really couldn't come up with anything..

Is there parameter or a way to make this

cardamom
  • 6,873
  • 11
  • 48
  • 102
Euler_Salter
  • 3,271
  • 8
  • 33
  • 74

2 Answers2

5

This stuff is interesting, I have solved it for you using the answer from here The docs for this function are here

from scipy.spatial import cKDTree
points = [[0,0], [1,4], [2,3], [4,1], [1,1], [2,2], [5,3]]
voronoi_kdtree = cKDTree(points)
extraPoints = [[0.5,0.2], [3, 0], [4,0],[5,0], [4,3]]
test_point_dist, test_point_regions = voronoi_kdtree.query(extraPoints)
test_point_regions
>>> array([0, 3, 3, 3, 6])

Here is how you interpret that array - Will call your 'extraPoints' test points. Your first test point (0.5,0.2) sits in the region around your 0th point being (0,0). Second, third and fourth point sit in the region around point 3 (0-index) being (4,1). The last of your test points is around (5,3).

I think there might be an issue in imagining that these regions are polygons and trying to apply that kind of algorithm, as some of them on the edges are regions that go off to infinity.

cardamom
  • 6,873
  • 11
  • 48
  • 102
  • This is interesting! I did a few quick tests and it seems to match what the voronoi_plot_2d diagram suggests. Should they always agree? I'm confused why voronoi doesn't have its own query method. – uhoh Dec 01 '20 at 14:07
2

For very small number of points and cells it might be simpler to check every point against every cell with 'point in polygon' algorithm (perhaps there are numpy implementations of it)

In general case you can build trapezoidal map data structure over cells and quickly determine - what cell every points belongs to.

Arbitrary found example

MBo
  • 77,366
  • 5
  • 53
  • 86