Transcription of Delaunay Triangulations - MIT
{{id}} {{{paragraph}}}
Example: confidence
Delaunay Triangulations - MIT
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 S such 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 P March 3, 2005 Lecture 9.
Finally, straighten the arcs into line segments. The resultant graph is DG(P). March 3, 2005 Lecture 9: Delaunay triangulations Properties of Delaunay Graphs No two edges cross; DG(P) is a plane graph. • Proved using the empty circle property of Voronoi diagrams.
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: