Implementation of Graham’s Scan Method for Triangulation of Non Convex Polygons in Java Netbeans Environment

Implementation of Graham’s Scan Method for Triangulation of Non Convex Polygons in Java Netbeans Environment

Faruk Selimović

Muzafer Saračević

Vesad Doljak

Abstract - This paper presents an algorithm for triangulation of non-convex polygons on the principle of Graham’s scan. This method is based on finding the so-called "ear" of triangulation of the observed polygons. Second aspect is storing in a temporary stack all the previous points of the polygon from which would later be pulled the diagonals that will actually create the triangulations. Triangulation of the polygon has increasing application in the design of the Geographic Information Systems (GIS) and it is the basis for calculating the surface of irregular terrains. In particular, we have implemented mentioned method in Java Net Beans environment with a graphical user interface. Java, as one of the leading object-oriented programming languages allows efficient implementation of this algorithm, and it is one of the main reasons of implementation of this algorithm in this programming language.

Keywords - Polygon triangulation, Graham’s scan method, non-convex polygon, Java Net-Beans environment.

International Burch University

Journal of Natural Sciences and Engineering