How to quickly group a set of points (2500x2500) by Voronoi cells?

Question

C++ / C#

There is a Voronoi diagram built in a 2500x2500 rectangle (with 500 cells)
How can now all 2500x2500 points be divided between 500 cells (so that each has an array with its points)?
Is there a more efficient way than simply checking if a polygon contains a point (and so on for each point)?

Answer 1

If you need faster than linear time, then there is a relatively difficult way. The Voronoi diagram is dual to the Delaunay triangulation. If we connect the centers of adjacent cells of the diagram, we get triangulation. Localize in Delaunay triangulation. you can not go through all the vertices, but go to neighboring triangles in the right direction (delaunay triangulation walk).
Knowing in which triangle we are, it is enough to check the distance to 3 of its vertices that coincide with the centers of the Voronoi cells.
Something like this is implemented here:
https://doc.cgal.org/latest/Voronoi_diagram_2/clas...
And here:
https://doc.cgal.org/latest/Triangulation_2/classC...
If you are trying to localize the nodes of a regular grid, then it is logical to take the result of the neighboring calculated localization as the initial triangle, since the points go in a row. In the function on the second link, there is such an opportunity.
An easier way might work . You can first break the centers of the Voronoi cells into cells of a regular (rectangular) grid and then look for the nearest point in neighboring regular cells.

Answer 2

According to the control points of the diagram: which of them is the closest to the next point - we enter into that array.
Can be optimized: all cells a.i. convex, so if two non-neighboring points both belong to the same cell, then all points between these two do too.