March 3, 2005 Lecture 9: Delaunay triangulations Delaunay Triangulations(slides mostly by Glenn Eguchi)March 3, 2005 Lecture 9: Delaunay triangulations Motivation: Terrains• Set of data points A ⊂ R2• Height ƒ(p) defined at each point p in A• How can we most naturally approximate height of points not in A?March 3, 2005 Lecture 9: Delaunay triangulations Option: Discretize• Let ƒ(p) = height of nearest point for points not in A• Does not look naturalMarch 3, 2005 Lecture 9: Delaunay triangulations Better Option: Triangulation• Determine a triangulation of A in R2, then raise points to desired height• triangulation: planar subdivision whose bounded faces are triangles with vertices from AMarch 3, 2005 Lecture 9: Delaunay triangulations Triangulation: Formal Definition• maximal planar subdivision: a subdivision Ssuch that no edge connecting two vertices can be added to S without destroying its planarity• triangulation of set of points P: a maximal planar subdivision whose vertices are elements of PMarch 3, 2005 Lecture 9: Delaunay triangulations Triangulation is made of triangles• Outer polygon must be convex hull• Internal faces must be triangles, otherwise they could be triangulated furtherMarch 3, 2005 Lecture 9: Delaunay triangulations Triangulation DetailsFor P consisting of n points, all triangulations contain 2n-2-k triangles, 3n-3-k edges•n= number of points in P•k= number of points on convex hull of PMarch 3, 2005 Lecture 9: Delaunay triangulations Terrain Problem, Revisited• Some triangulations are “better” than others• Avoid skinny triangles, i.e. maximize minimum angle of triangulationMarch 3, 2005 Lecture 9: Delaunay triangulations Angle Optimal Triangulations•Create angle vector of the sorted angles of triangulation T, (α1, α2, α3, … α3m) = A(T)with α1 being the smallest angle•A(T) is larger than A(T’) iff there exists an isuch that αj = α’jfor all j < i and αi > α’i• Best triangulation is triangulation that is angle optimal, i.e. has the largest angle vector.March 3, 2005 Lecture 9: Delaunay triangulations Angle Optimal TriangulationsConsider two adjacent triangles of T:• If the two triangles form a convex quadrilateral, we could have an alternative triangulation by performing an edge flip on their shared edge.March 3, 2005 Lecture 9: Delaunay triangulations •Edge e is illegal if:• Only difference between T containing e and T’with e flipped are the six angles of the quadrilateral.Illegal EdgesMarch 3, 2005 Lecture 9: Delaunay triangulations Illegal Triangulations• If triangulation T contains an illegal edge e, we can make A(T) larger by flipping e.• In this case, T is an illegal triangulation.March 3, 2005 Lecture 9: Delaunay triangulations Thales’s Theorem• We can use Thales’ Theorem to test if an edge is legal without calculating anglesLet C be a circle, l a line intersecting C in points a and band p, q, r, and s points lying on the same side of l. Suppose that p and q lie on C, that r lies inside C, and that s lies outside C. Then:March 3, 2005 Lecture 9: Delaunay triangulations Testing for Illegal Edges• The edge pipjis illegal iff pllies inside C.– Proved using Thales’s Theorem. E.g., the angle pi-pj-pkis smaller than the angle pi-pl-pk• If pi, pj, pk, plform a convex quadrilateral and do not lie on a common circle, exactly one of pipjand pkplis an illegal edge.March 3, 2005 Lecture 9: Delaunay triangulations Computing Legal Triangulations1. Compute a triangulation of input points P.2. Flip illegal edges of this triangulation until all edges are legal.• Algorithm terminates because there is a finite number of triangulations.• Too slow to be interesting…March 3, 2005 Lecture 9: Delaunay triangulations Sidetrack: Delaunay Graphs• Before we can understand an interesting solution to the terrain problem, we need to understand Delaunay Graphs.• Delaunay Graph of a set of points P is the dual graph of the Voronoi diagram of PMarch 3, 2005 Lecture 9: Delaunay triangulations Delaunay GraphsTo obtain DG(P):• Calculate Vor(P)• Place one vertex in each site of the Vor(P)March 3, 2005 Lecture 9: Delaunay triangulations Constructing Delaunay GraphsIf two sites siand sjshare an edge (i.e., are adjacent), create an arc between viand vj, the vertices located in sites siand sjMarch 3, 2005 Lecture 9: Delaunay triangulations Constructing Delaunay GraphsFinally, straighten the arcs into line segments. The resultant graph is DG(P).March 3, 2005 Lecture 9: Delaunay triangulations Properties of Delaunay GraphsNo two edges cross; DG(P) is a plane graph.• Proved using the empty circle property of VoronoidiagramsMarch 3, 2005 Lecture 9: Delaunay triangulations Delaunay Triangulations• Some sets of more than 3 points of Delaunay graph may lie on the same circle. • These points form empty convex polygons, which can be triangulated. • Delaunay Triangulation is a triangulation obtained by adding 0 or more edges to the Delaunay Graph.March 3, 2005 Lecture 9: Delaunay triangulations Properties of Delaunay TrianglesFrom the properties of Voronoi Diagrams…• Three points pi, pj, pk∈ P are vertices of the same face of the DG(P) iff the circle through pi, pj, pkcontains no point of P on its interior.Proof:•Assume there are other points inside the circle. •Choose one point p inside the circle, and remove all other points but pi, pj, pk.Note that, after the removal of points,pi, pj, pkremains a triangle.•Assume lies opposite pj.•pis closer to the center than are pi, pj, pk. So, the center belongs to the interior of the Voronoi face of p.• Consider a segment o-pj. There is a point q on that segmentthat is equidistant to pjand p,but its distance to pi pkis larger.•Therefore, the Voronoi cells of pjand p share an edge, so thereis a Delaunay edge between pjand p.•But the Delaunay edges cannot intersect. QED.popipjpkMarch 3, 2005 Lecture 9: Delaunay triangulations Legal Triangulations, revisitedA triangulation T of P is legal iff T is a DT(P).•DT → Legal: Empty circle property • Legal → DT: assume legal and not empty circle propertyMarch 3, 2005 Lecture 9: Delaunay triangulations DT and Angle OptimalThe angle optimal triangulation is a DT.March 3, 2005 Lecture 9: Delaunay triangulations Terrain Problem, revisitedTherefore, the problem of finding a triangulation that maximizes the minimum angle is reduced to the problem of finding a
View Full Document