(计算机图形学)Voronoi_Diagram_Slides.ppt

Computational Geometry Lecture 8 Voronoi Diagrams Voronoi Diagram Input: A set of points locations (sites) in the plane. Output: A planar subdivision into cells. Each cell contains all the points for which a certain site is the closest. Application: Nearest-neighbor queries (by point location in the diagram). Voronoi Diagram Assume no four sites are co-circular. The Voronoi diagram is a planar graph, whose vertices are equidistant from three sites, and edges equidistant from two sites. The convex hull of the sites are those who have an unbounded cell. Prove ! Voronoi Diagram – Na?ve Construction Construct a bisector between one site and all others. A Voronoi cell is the intersection of all half-planes defined by the bisectors. Time complexity: O(nlogn) for each cell. Voronoi Diagram If all the sites are colinear, the Voronoi diagram will look like this: Otherwise, the diagram is a connected planar graph, in which all the edges are line segments or rays Voronoi Diagram Complexity A Voronoi diagram of n distinct sites contains n cells. One cell can have complexity n-1, but not all the cells can. The number of vertices V ? 2n-5 The number of edges E ? 3n-6 The number of faces F = n Voronoi Diagram Properties A vertex of a Voronoi diagram is the center of a circle passing through three sites. Each point on an edge is the center of a circle passing through two sites. Computing Voronoi Diagrams Plane sweep. The difficulty: If we maintain the VD of all points seen in the sweep so far – this can change as new points are swept. The Beach Line The bisector between a point and a line is a parabola. The beach line is the lower envelope of all the parabolas already seen. Sweep the plane from above, while maintaining the invariant: the Voronoi diagram is correct up to the beach line. The beach line is an x-monotone curve consisting of parabolic arcs. The breakpoints of the beach line lie on the Voronoi edges of the final diagram. The Algorithm Possible events: Sit