The implementation of an algorithm to find the convex hull of a set of three-dimensional points
- 3 January 1990
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 9 (1) , 105-132
- https://doi.org/10.1145/77635.77640
Abstract
A detailed description of the implementation of a three-dimensional convex hull algorithm is given. The problems experienced in the production and testing of a correct and robust implementation of a geometric algorithm are discussed. Attention is paid to those issues that are often brushed over in the theoretical descriptions but cause errors in a real computation. These include degeneracies such as coplanar points, floating-point errors, and other special, but not necessarily degenerate, casesKeywords
This publication has 3 references indexed in Scilit:
- Geometric modeling of solid objects by using a face adjacency graph representationACM SIGGRAPH Computer Graphics, 1985
- Primitives for the manipulation of general subdivisions and the computation of VoronoiACM Transactions on Graphics, 1985
- Convex hulls of finite sets of points in two and three dimensionsCommunications of the ACM, 1977