Delaunay TriangulationsPresented by Glenn Eguchi6.838 Computational GeometryOctober 11, 2001Motivation: 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?Option: Discretize• Let ƒ(p) = height of nearest point for points not in A• Does not look naturalBetter 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 ATriangulation: 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 PTriangulation is made of triangles• Outer polygon must be convex hull• Internal faces must be triangles, otherwise they could be triangulated furtherTriangulation 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 PTerrain Problem, Revisited• Some triangulations are “better” than others• Avoid skinny triangles, i.e. maximize minimum angle of triangulationAngle 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 i such that αj = α’j for all j < i and αi > α’i• Best triangulation is triangulation that is angle optimal, i.e. has the largest angle vector. Maximizes minimum angle.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.• Edge e is illegal if:• Only difference between T containing e and T’ with e flipped are the six angles of the quadrilateral.Illegal EdgesIllegal 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.Thale’s Theorem• We can use Thale’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:Testing for Illegal Edges• The edge pipjis illegal iff pllies inside C.•If pi,pj,pk, plform a convex quadrilateral and do not lie on a common circle, exactly one of pipjand pkplis an illegal edge.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…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 PDelaunay GraphsTo obtain DG(P):• Calculate Vor(P)• Place one vertex in each site of the Vor(P)Constructing Delaunay GraphsIf two sites siand sjshare an edge (siand sjare adjacent), create an arc between viand vj, the vertices located in sites siand sjConstructing Delaunay GraphsFinally, straighten the arcs into line segments. The resultant graph is DG(P).Properties of Delaunay GraphsNo two edges cross; DG(P) is a planar graph.• Proved using Theorem 7.4(ii).• Largest empty circle propertyDelaunay 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.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.Properties of Delaunay TrianglesFrom the properties of Voronoi Diagrams…• Two points pi,pj∈ P form an edge of DG(P)iffthere is a closed disc C that contains piand pjon its boundary and does not contain any other point of P.Properties of Delaunay TrianglesFrom the previous two properties…•A triangulation T of P is a DT(P)iffthe circumcircle of any triangle of T does not contain a point of P in its interior.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.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 multiple DT exist for P?• Not all DT are angle optimal.• By Thale’s Theorem, the minimum angle of each of the DT is the same.• Thus, all the DT are equally “good” for the terrain problem. All DT maximize the minimum angle.Terrain Problem, revisitedTherefore, the problem of finding a triangulation that maximizes the minimum angle is reduced to the problem of finding a Delaunay Triangulation.So how do we find the Delaunay Triangulation?How do we compute DT(P)?• We could compute Vor(P) then dualize into DT(P).• Instead, we will compute DT(P) using a randomized incremental method.Algorithm Overview1. Initialize triangulation T with a “big enough” helper bounding triangle that contains all points P.2. Randomly choose a point prfrom P.3. Find the triangle ∆ that prlies in.4. Subdivide ∆ into smaller triangles that have pras a vertex.5. Flip edges until all edges are legal.6. Repeat steps 2-5 until all points have been added to T.Let’s skip steps 1, 2, and 3 for now…Triangle Subdivision: Case 1 of 2Assuming we have already found the triangle that prlives in, subdivide ∆into smaller triangles that have pras a vertex.Two possible cases:1) prlies in the interior of ∆∆∆∆Triangle Subdivision: Case 2 of 22) prfalls on an edge between two adjacent trianglesWhich edges are illegal?• Before we subdivided, all of our edges were legal.• After we add our new edges, some of the edges of T may now be illegal, but which ones?Outer Edges May Be