The idea of this algorithm is to utilize a uniform grid (the number of nets used in this article is the multiple of the number of 4 of the number of points), and all points are in the grid, and the points in these grids make up the Voronoi diagram, and the online increment algorithm . Then use the regional merge method in the granted algorithm to combine all the Voronoi diagrams composed of all small squares into a complete Voronoi diagram.
The pseudo code is as follows:
#ifnotdef voronoi.h
#def voronoi.h
// There are three classes here: Point, Voronoi, Grid. The Point class uses the coordinates to describe the position of the point, Voronoi is the Voronoi graphic constructed in the flat point, and the grid is the grid of the Point.
Class point {
Struct position {
INT X;
Int Y;
}
Int Gridnum;
INT seq;
Int Totalnum;
Int Gridnum;
}
Class voronoi {
Struct graph {
CDC Polygon ();
}
Struct onlineincremeth {
}
}
Class grid {
Void
int Num.Range;
Int serial;
Int Totalnum;
INT POINTNUM;
INT POINTTOTALNUM;
int Layer;
Int morton.availabledigit;
Int morton.lastdigit;
1 The algorithm of the voronoi diagram is divided using uniform grid.
The PREF is established closest to the number of devices, with a uniform grid of the number of plaids. Store in a quadrush.
Voronoi diagram constructed by the POST output point.
Return Null
1 Open file // Open the storage file of point coordinates
2 read point.position // read the coordinates
3 Find_nearestquadronum (Poin.TotalNum, Grid.Num); / / Find the power of 4 of the total number of points close to the total number of points, with this number as the total number of grids
4 crete_grid (grid.num) // creation grid
4 Loop (Point.Seq Not Exceed Poin.totalnum) // Enter the grid according to the coordinates
1FIND POINT.POSITION in Grid.num.Range
2 point.gridnum = grid.serial
4 endloop
5 loop (grid.serial not exceed grid.stotalnum) // merge points in the grid into Voronoi
1 loop (Grid.Pointnum Not Exceed Grid.PointTotalnum) / / Judging the number of points in the grid
1 if Grid.Pointnum <= 1 // If the number of points is not more than 1, the loop is jumped out
2 Break
3 else
4 voronoi_onlineincremeth (point.gridnum = grid.serial)
5 voronoi.gridnum = Grid.Serial
4 end loop
6 end loop
7 conjoin_voronoi_quartreemeth (voronoi.grid) // uses a quadruple grid merge algorithm
2conjoin_voronoi_quartreemeth:
PREF, we first need to use all the small grid storage (stored format using a four-in-one MORTON code)
POST finally constitutes a complete Voronoi map by constantly returning small grid.
Return Voronoi
1 Grid.layer = getLog (4, grid.num) // Sign in the length of the MORTON code of the grid 2 loop (Grid.Layer Not Less Than 1) // Use the Morton code length for Voronoi diagram combined
1 grid.morton.availabledigit = getLog (4, grid.num) -grid.layer 1. // Find the effective place of the grid's MORTON code
2 Loop (Grid.morton.availableDigit Not Less Than 1) // Set the threshold to make the raster available MORTON code effective bit number of no less than 1
1 Grid.morton.lastdigit = 0 // The last start search value of the grid MORTON code is 0
1 loop (Grid.morton.lastdigit NOT EXCEED 3) // Take a loop to find a small grid located in the same large quadrupo
1 Grid1.morton.lastdigit = GET (Grid1.morton.lastdigit )
2 Grid2.morton.lastdigit = Grid1.morton.lastdigit
1 if true = compare (Grid1.morton.lastdigit, Grid2.morton.lastdigit)
1 voronoi.graph = conjoin_voronoi (grid1, grid2) // uses Voronoi merge algorithms in the granted method
2 end if
2 end loop
3 end loop
3 end loop
Let's analyze the time complexity of the algorithm:
In the algorithm of the first part, identify the number of grids of the total number of points and create a standby time to take a constant time, and share all the grids requires O (n) time. The time complexity of the following sections is different. The worst case is O (N2).
In the second partial algorithm, the time consumption of the first step is O (log4n), and the complexity of the operation time of the Voronoi diagram is O [log4n × (log4n N2)], so the time complexity is O [ LOG4N (N2)].
In summary, the time complexity of this algorithm is O [N N2 LOG4N (N2)] = O [LOG4N (N2)].
It seems that this algorithm is more than a long time, in fact, it is not necessarily studied. This algorithm can be reduced to O (log43n) for uniformly distributed point algorithms. Take 16 points as an example, o (log4316) = 8, below 16 itself. So this algorithm is suitable for uniform distribution network points.
