An efficient algorithm for minimum zone flatness based on the computation of the largest inscribed ball in a symmetric polyhedron. (June 2017)

• Record Type: Journal Article
• Authors: Zheng, Yu
• Is Part Of: Computer aided design. Volume 87(2017)
• Page Start: 11
• Page End: 19
• Publication Date: 2017-06
• Subjects: Geometric form -- Flatness -- Largest inscribed ball -- Minimum zone -- Width -- Computational geometry; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2017.03.004
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: This paper presents an algorithm for the minimum zone flatness tolerance of a finite point set, which is defined to be the minimum Euclidean distance between two parallel planes that sandwich the point set. The algorithm is based on the observation that the flatness tolerance is equal to the radius of the largest inscribed ball in the convex hull of the Minkowski difference of the point set and itself, which is a symmetric polyhedron with respect to the origin. Then, an iterative procedure is developed to adaptively grow another symmetric polyhedron inside the convex hull of the Minkowski difference such that the radius of its inscribed ball monotonically increases and converges to the flatness tolerance. The algorithm is guaranteed to compute the globally minimum solution within finite iterations. Moreover, there is no need to compute the Minkowski difference or the convex hull of the point set, so the proposed algorithm is very fast and takes only several milliseconds for hundreds of thousands of points on a normal computer, such as a desktop computer with an Intel Xeon 3.70 GHz CPU and 16GB RAM used in this work. Highlights: An efficient algorithm for the minimum zone flatness tolerance of a finite point set is proposed. The flatness tolerance is reduced to the computing of the largest ball in a symmetric polyhedron. The largest inscribed ball is computed by iteratively growing an inscribed polyhedron. The algorithm needs several milliseconds for hundreds of thousands of points on a normal PC.