Computing the three-dimensional convex hull

Abstract
The program tetra computes the three-dimensional convex hull of a set of n points in (x, y, z) space. The input consists of the coordinates of the points and the output is the identification numbers of the points that are on the convex hull. Since the convex hull is constructed as a set of triangular faces, called facets, additional output information can be requested about these interlocking facets. This additional information may be used to reconstruct and verify the correctness of the comp...

Title of program: tetra
Catalogue Id: ADFS_v1_0

Nature of problem
The program determines the convex hull of a set of points in (x,y,z) space. The convex hull is the minimum volume convex polytope which encloses the set of points. This polytope can be considered to be composed of a set of triangular faces called facets. The program returns the points on the hull and, if requested, information from a balanced binary tree containing all the facets on the hull.

Versions of this program held in the CPC repository in Mendeley Data
ADFS_v1_0; tetra; 10.1016/S0010-4655(97)00027-1

This program has been imported from the CPC Program Library held at Queen's University Belfast (1969-2019)

摘要：程序tetra可计算(x,y,z)空间内n个点集的三维凸包（three-dimensional convex hull）。其输入为各点的坐标，输出为凸包上所有点的标识编号。由于凸包由若干被称为面片（facet）的三角面构建而成，用户可申请获取关于这些互锁面片的额外输出信息。此类附加信息可用于重构并验证其comp...的正确性。

程序名称：tetra

目录编号：ADFS_v1_0

问题本质：本程序用于求解(x,y,z)空间中点集的凸包。凸包是包围该点集的最小体积凸多面体（convex polytope），该多面体可被视为由若干被称为面片的三角面组合而成。程序将返回凸包上的点，若用户提出请求，还可返回包含凸包所有面片的平衡二叉树（balanced binary tree）中的相关信息。

Mendeley数据平台CPC库中收录的本程序版本：ADFS_v1_0; tetra; 10.1016/S0010-4655(97)00027-1

本程序源自贝尔法斯特女王大学馆藏的CPC程序库（1969-2019）