The implementation of an algorithm to find the convex hull of a set of three-dimensional points

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

REFERENCES

• 1: Silvia Ansaldi , Leila De Floriani , Bianca Falcidieno, Geometric modeling of solid objects by using a face adjacency graph representation, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.131-139, Jul. 1985
• 2: APPLE COMPUTER, INC. Mazintosh Pascal Technical Appendix, Apple Computer, Inc., 1984, D 1-42.
• 3: BAUMGART, g.G. Geometric modelling for computer vision. Stanford Artif. intell. Lab. Rep. STAN-CS-74-463, Computer Science Dept., Stanford Univ., Stanford, Calif., 1974.
• 4: BRAID, I. Notes on a geometric modeller. C.A.D. Group Doc. 101, Univ. of Cambridge, U.K., June 1979.
• 5: DAY, A.M. The implementation of an algorithm to find the convex hull of a three dimensional set of points. Memo CGP 87/5, Dept. of Computing Science, Univ. of East Anglia, Norwich, U.K., 1987.
• 6: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 7: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 8: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• 9: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  E. Data

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Design, Experimentation, Theory