AN ALGORITHM FOR CONSTRUCTING THE CONVEX HULL AND THE TRIANGULATION OF A SET OF NODES IN A PLANE

Two kinds of common operation on the set of nodes in a plane are calculating its convex hull and triangulation, and usually the algorithms are studied independently. But in some cases, the two calculations are all needed. Therefore a comprehensive algorithm is presented in this paper. By adding a less time consumption model of distinguishing and managing the segments of the triangles during the triangulation of a set of nodes in a plane, the segments can be recorded, which would be the boundary of the convex hull of the node set. So the convex hull and the triangulation of the node set in a plane can be obtained in the same process. It means a higher efficiency. The algorithm can also work when it is used to implement one of the functions independently. It can also be used for calculating the convex hull of a simple polygon.