An Algorithm of Constructing Hierarchical Tree Structures of Polyhedra (1st Report)
Susumu Furukawa · Journal of the Japan Society of Precision Engineering · 1985
Various Problems of constructing and processing polyhedra represented by the hierarchical tree structure of convex components have been approached by the authors for several years. An algorithm of generating the tree structures of polyhedra is discussed in this paper. To decompose a polyhedron into the smaller components may be necessary in the processes of constructing the structure. A new method for this type of problem, which is based on the idea of utilizing the boundary edge line loops between used and unused faces for making the convex hull of the original one, is presented for the case of a polyhedron without holes. The main feature of this method is (1) the polyhedron can always be decomposed uniquely, (2) no vertex is newly produced, and (3) the number of newly created components may not become so large.