@inproceedings{638fe7c99a944aa5ad2eae35fdeeab45,

title = "An efficient algorithm for finding the CSG representation of a simple polygon",

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.",

keywords = "Boundary-to-CSG conversion algorithms, Constructive solid geometry, Simple polygons, Solid modeling",

author = "David Dobkin and Leonidas Guibas and John Hershberger and Jack Snoeyink",

note = "Publisher Copyright: {\textcopyright} 1988 ACM.; 15th International Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988 ; Conference date: 01-08-1988 Through 05-08-1988",

year = "1988",

month = aug,

day = "1",

doi = "10.1145/54852.378472",

language = "English (US)",

series = "Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988",

publisher = "Association for Computing Machinery, Inc",

pages = "31--40",

editor = "Beach, {Richard J.}",

booktitle = "Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988",

}