咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Efficient algorithm for findin... 收藏

Efficient algorithm for finding the CSG representation of a simple polygon

作     者:Dobkin, David Guibas, Leonidas Hershberger, John Snoeyink, Jack 

作者机构:Princeton Univ United States 

出 版 物:《Computer Graphics (ACM)》 (Comput Graphics (ACM))

年 卷 期:1988年第22卷第4期

页      面:31-40页

核心收录:

主  题:Mathematical Techniques 

摘      要: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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分