Efficient algorithm for finding the CSG representation of a simple polygon

David Paul Dobkin, Leonidas Guibas, John Hershberger, Jack Snoeyink

Research output: Contribution to specialist publicationArticle

29 Scopus citations

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 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 formulae do not always exist for general polyhedra in three dimensions.

Original languageEnglish (US)
Pages31-40
Number of pages10
Volume22
No4
Specialist publicationComputer Graphics (ACM)
DOIs
StatePublished - Jan 1 1988

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Efficient algorithm for finding the CSG representation of a simple polygon'. Together they form a unique fingerprint.

Cite this