GEOMETRY TOOLBOX - A TOOLBOX OF GEOMETRIC ABSTRACT DATA TYPES

Abstract

The Geometry Toolbox (GT) defines a set of abstract data types and related functions for solving a class of geometric problems often encountered by systems and applications programmers in computer graphics. The data types defined are points, lines, planes, and polygons. Functions are provided for creating and manipulating GT data types and for determining certain relationships among them such as intersections, angles, and nearest points. The data types and algorithms used in GT are detailed. Close attention is paid to two issues: the finite precision of digital computers, and the mathematical instabilities of the algorithms. Our experience with using GT is discussed as well as other related work and possible future extensions. The GT Programmer's Manual is appended and includes a detailed specification of the toolbox.