# Delaunay Triangulations - MIT

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 natural

March 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 A

March 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: Delaunay triangulations

Triangulation is made of triangles

? Outer polygon must be convex hull ? Internal faces must be triangles, otherwise

they could be triangulated further

March 3, 2005

Lecture 9: Delaunay triangulations

Triangulation Details

For 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 P

March 3, 2005

Lecture 9: Delaunay triangulations

Terrain Problem, Revisited

? Some triangulations are "better" than others ? Avoid skinny triangles, i.e. maximize

minimum angle of triangulation

March 3, 2005

Lecture 9: Delaunay triangulations

................

................

#### To fulfill the demand for quickly locating and searching documents.

It is intelligent file search solution for home and business.

##### Related download

- naming angles hanlonmath
- angle pair relationships st joseph high school
- revision 7 angle and circle properties
- delaunay triangulations mit
- straight lines
- the segment addition postulate date period
- section 1 introduction to geometry points l ines and planes
- segment and angle bisectors miami senior high
- coordinate geometr y
- correctionkey nl b ca b name class date 1 2 angle

##### Related searches

- find difference in percent between 2 values
- how to find percent between 2 numbers
- distance between two points map
- distance between two points calculator 3d
- distance between 2 points calculator
- find the distance between the points calculator
- how to find distance between 2 points
- how to find percentage between 2 numbers
- find a percentage between 2 number
- distance between 2 points matlab
- find percentage difference between 2 numbers
- how to find percentages between 2 numbers