October 2, 2003 Lecture 9: Delaunay triangulations Delaunay Triangulations(slides mostly by Glenn Eguchi)October 2, 2003 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?October 2, 2003 Lecture 9: Delaunay triangulations Option: Discretize• Let ƒ(p) = height of nearest point for points not in A• Does not look naturalOctober 2, 2003 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 AOctober 2, 2003 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 POctober 2, 2003 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 furtherOctober 2, 2003 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 POctober 2, 2003 Lecture 9: Delaunay triangulations Terrain Problem, Revisited• Some triangulations are “better” than others• Avoid skinny triangles, i.e. maximize minimum angle of triangulationOctober 2, 2003 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.October 2, 2003 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.October 2, 2003 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 EdgesOctober 2, 2003 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.October 2, 2003 Lecture 9: Delaunay triangulations Thales’s Theorem• We can use Thales’s 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:October 2, 2003 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.October 2, 2003 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…October 2, 2003 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 POctober 2, 2003 Lecture 9: Delaunay triangulations Delaunay GraphsTo obtain DG(P):• Calculate Vor(P)• Place one vertex in each site of the Vor(P)October 2, 2003 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 sjOctober 2, 2003 Lecture 9: Delaunay triangulations Constructing Delaunay GraphsFinally, straighten the arcs into line segments. The resultant graph is DG(P).October 2, 2003 Lecture 9: Delaunay triangulations Properties of Delaunay GraphsNo two edges cross; DG(P) is a plane graph.• Proved using the empty circle propertyOctober 2, 2003 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.October 2, 2003 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.• p is 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.popipjpkOctober 2, 2003 Lecture 9: Delaunay triangulations Legal Triangulations, revisitedA triangulation T of P is legal iff T is a DT(P).• DT → Legal: Empty circle property and Thale’s Theorem implies that all DT are legal• Legal → DT: Proved on p. 190 from the definitions and via contradiction.October 2, 2003 Lecture 9: Delaunay triangulations DT and Angle OptimalThe angle optimal triangulation is a DT. Why?• If P is in general position, DT(P) is unique and thus, is angle optimal.What if
View Full Document