Delaunay's Scissors
An interactive demo of the Delaunay triangulation algorithm and the Wallace–Bolyai–Gerwien theorem.

by Zivvy Epstein and Dima Smirnov

Definition (Delaunay triangulation)

A Delaunay triangulation for a set of points is the triangulation with the maximum minimal angle in its triangles. This is achieved by repeatedly "flipping" edges if they are inside a triangle's circumcircle.

Theorem (Wallace-Bolyai-Gerwien)

Any simple polygon can be cut into finite pieces and stuck back together to form any other simple polygon of equal area.

You:
  1. Click anywhere to start drawing the initial polygon. Click back in the orange circle when you are finished
  2. Similarly, draw the terminal polygon.
We:
  1. Rescale the polygons so that they are of equal area.
  2. Cut the initial polygon into random triangles.
  3. Find the Delaunay triangulation.
    1. Take a random edge whose triangles form a convex quadrilateral.
    2. Draw the circumcirlce of one of the edge's triangles.
    3. If a point in the other triangle is inside the circle, flip the edge.
    4. Repeat until there are no ledges left to flip.
  4. Cut and rearrange the triangles into a stack of rectangles.
  5. Cut new rectangles, turn them into triangles, and place them inside the terminal polygon.
Try again!