Polygon Triangulation Algorithm as a Powerful Core Processor of PLAN-I

Abstract

A concise, complete and reliable algorithm for triangulating an arbitrary polygon is presented as a powerful core processor of PLAN-I (Production Layout Automation Nucleus) system1. A polygon with inner loops is converted into a non-self-intersecting polygon (NIP) through adding Bridge Edges . A triangular splitting algorithm for NIP is described in detail and successfully implemented. The program is about 300 lines in FORTRAN-77. Sweeping and local operations with respect to the triangular-faceted boundary representation are designed with the algorithm to improve functions of solid modeling in PLAN-I. The algorithm of triangulation can also be applied to Boolean operations and other issues.