Introduction

This applet presents an algorithm to triangulate a simple, closed polygon. One can describe the problem as follows: If a polygon is given that has n edges, then the n diagonals are searched, which divide the polygon into n-2 triangles.

• The Triangulation
• An Applet to triangulate a polygon
• Reference

The Triangulation

A polygon with n edges, respectively points, is given.

The points and edges of the polygons are inserted in coincidental order into a special data structure, the QueryStructure. Trapezoids are generated from inserting the points and edges, which represent the searched trapezoidation after inserting all edges and points. Further information to the organization of the QueryStructure is in [SEI91].

Subsequently, diagonals are inserted, which divide the polygon into y-monotonous polygons. Such a diagonal is inserted only within a trapezoid to have their terminator points on different sides of the polygons to-be.

The y-monotonous polygon, developed by the diagonals, can be divided into triangles in linear time with a Greedy algorithm.

An Applet to triangulate a polygon

The corner points of the polygons can be entered by clicking with the left mouse button. As soon as the polygon is closed, the triangulation is computed and can be displayed by clicking the checkmarks at the lower edge of the screen.

• Show Trapezoids:
  The trapezoidation of the polygon is displayed.
• Show Diagonals:
  The diagonals from the intermediate step to the triangulation are displayed.
• Show Triangulation:
  The triangulation of the polygons is displayed.

Reference