An Efficient Algorithm for Finding the CSG Representation of a Simple Polygon
Report ID: TR-152-88Author: Dobkin, David P. / Guibas, Leonidas / Hershberger, John / Snoeyink, Jack
Date: 1988-05-00
Pages: 11
Download Formats: |PDF|
Abstract:
We consider the problem of converting boundary representations of polyhedral objects into constructive-solid-geometry (CSG) representations. The CSG representations for a polyhedron P are based on the half-spaces supporting the faces of P. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practical O(n log n) algorithm for doing this boundary-to-CSG conversion for a simple polygon of n sides. We also prove that such nice formulae do not always exist for general polyhedra in three dimensions.