Accurate, simple and efficient triangulation of a polygon by ear removal with lowest memory consumption

Abstract

Polygons can conveniently represent real world objects. In automatic character recognition, shapes of individual letters are represented by polygons. In robotics, obstacles are represented using polygons. In computer graphics programming, solid objects are represented using polygons on the two dimensional screen. The polygons can be easily manipulated using known mathematical operations. That is the reason for representing real world objects using polygons. However, polygons can be in complicated shapes. Therefore, it is better if there is a way to partition a polygon into smaller pieces. Triangulation is a particular way of doing this from which polygons are partitioned into triangles. The basic triangulation algorithm is widely used in applications where 100% accuracy is necessary. Algorithms with better asymptotic order than the basic triangulation algorithm exist. However they are not 100% accurate and use advanced data structures causing higher memory consumption. This paper proposes a simple, efficient and 100% accurate algorithm which uses lowest amount of memory. The proposed algorithm is more suitable for embedded systems which do not possess large amount of memory. The proposed algorithm was experimentally compared with the basic triangulation algorithm. The experimental results prove that the proposed algorithm is faster than the basic triangulation algorithm.

Keywords

• computational geometry, computer graphics programming, triangulation, computational statistics, linear programming