PolygonTriangulation

Class Project of Introduction to Computational Geometry - Fall 2014

In computational geometry, polygon triangulation is the decomposition of a polygonal area (simple polygon) P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P. The problem of triangulating a simple polygon is an old and important computational problem. It can be simply stated as finding all the diagonals from one vertex to another in a given polygon that will partition the polygon into a set of triangles. A simple polygon is a polygon that has no self-intersections, n edges and n vertices. Polygon triangulation is used in many areas, and the search for optimal algorithms to compute it has a long history. Many algorithms assume that the polygon is already triangulated, and several would not be possible without the triangulation. Given a triangulation, other partitions such as convex or star polygons can easily be found in linear time. Some algorithms that rely entirely upon partitioned polygons are character recognition, shading and shortest path.

This software tool has an interactive user interface where a user can draw a simple polygon. If the polygon is crossed by itself, the tool will warn the user by pointing out one of the crosses. The user then can erase the content of the current window by pressing the “Reset” button to draw a new polygon. Otherwise after pressing the “Execute” button, the tool will triangulate the polygon by using ear clipping method of Godfried T. Toussaint’s “Efficient triangulation of simple polygons”. In this procedure user will understand the steps of the algorithm in more detail and how the algorithm works visually in “Processing” environment. It will give the user in-depth knowledge of the algorithm and the “Processing” environment.