DOC PREVIEW
MIT 6 838 - Delaunay Triangulations

This preview shows page 1-2-3-4-5-37-38-39-40-41-42-75-76-77-78-79 out of 79 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 79 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

MIT 6 838 - Delaunay Triangulations

Download Delaunay Triangulations
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Delaunay Triangulations and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Delaunay Triangulations 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?