Delaunay Triangulation
In this activity you will learn about Delaunay Triangulation. It is an algorithm used to cover a 2D set of points with triangles. Triangulation is used in animation and computer graphics to create a mesh of points that can model a person, background, object, etc. The triangles can be easily transformed to move the objects. Here is an example of the Delaunay triangulation:
Delaunay Triangulation works by using the circumcircle of each triangle. Follow the steps below to construct a Circumcircle of the following Triangle
1. Use the perpendicular bisector tool on each side of triangle ABC.
2. Notice how each line meets at one point. Mark this point. This is called the circumcenter of the triangle
3. Now draw a circle whose center is the circumcenter and whose radius is DA.
This circle is the circumcircle of Triangle ABC. Notice it contains point B and C also.
Based on the construction, what causes the circle to also contain points B and C? Hint: The circumcenter is on each perpendicular bisector. What does this guarantee about its distance from A, B, and C?
The algorithm uses the circumcircles to determine which points to connect with triangles. It is designed to maximize the smallest angle in the triangle. Drag the blue points below to see how the triangulation changes.
To minimize the angles, the triangles must be drawn so that each circumcircle does not contain any points in its interior. Move the slider below. Two possible triangulations of the 4 points are shown
Which is the correct triangulation of the 4 points? When the slider is on n = 1 or n =4? Hint: Check the green circumcircles for n = 1 and the red circles for n = 4. They are suppose to have no interior points.
Use the segment tool to draw a triangulation of the points below free hand. Then draw the circumcircles around your triangles. To draw a circumcircle for triangle AEC, use the circle through 3 points tool and click AEC. If all your circumcircles are empty, then it is correct.
To automatically draw a triangulation with GeoGebra:
1. Use the list tool to select points A through F. This makes list l1.
2. Then type DelaunayTriangulation(l1) in the input bar