摘要：Convex hull is widely used in computer graphic, image processing, CAD/CAM and pattern recognition. In this work, we derive some new convex hull properties and then propose a fast algorithm based on these new properties to extract convex hull of the object in binary image. It is achieved by computing the extreme points, dividing the binary image into several regions, scanning the regions existing vertices dynamically, calculating the monotone segments, and merging these calculated segments. Theoretical analyses show that the proposed algorithm has low complexities of time and space.
关键词：convex hull; extreme point; point set; monotone segment; computational geometry
