CODEWITHSUNDEEP
pythonnumpyscipygeometryvoronoi
Euler_Salter
Euler_Salter

Reputation: 3561

Python: check (and count how many) where points sit within voronoi cells

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

Upvotes: 4

Views: 2365

Answers (2)

cardamom
cardamom

Reputation: 7421

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.

Upvotes: 6

MBo
MBo

Reputation: 80187

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

Upvotes: 2

Related Questions