| 摘要 |
A method of producing and storing a Voronoi diagram includes: a) selecting a desired site Pk and a desired point p in the site; b) selecting a plurality of subfaces corresponding to a manifold around said point p; c) for each desired subface selecting a plurality of directions; d) for each direction providing a ray, selecting a point on the ray as an endpoint, and selecting hyperplanes corresponding to the endpoints; e) for each desired subface determining a type of intersection between the detected hyperplanes; f) determining whether there exist vertices of the cell in a cone generated by the endpoints, and finding said vertices, wherein if there remain further vertices that have not been found then there is carried out a step of further dividing the said subface into additional subfaces for separate determination; g) storing at least one of the following: said vertices, hyperplanes, neighbor sites, and possibly other information such as endpoints; h) repeating a)-g) for each desired site Pk and each desired point p in the selected site; i) defining at least one vertex or hyperplane from said endpoints, thereby decomposing said region X; and j) outputting said decomposed region X.
|
