Loading…

A new algorithm for computing the convex hull of a planar point set

TP391; When the edges of a convex polygon are traversed along one direction, the interior of the convex polygon is always on the same side of the edges. Based on this characteristic of convex polygons, a new algorithm for computing the convex hull of a simple polygon is proposed in this paper, which...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Zhejiang University. A. Science 2007-07, Vol.8 (8), p.1210-1217
Main Authors: Liu, Guang-hui, Chen, Chuan-bo
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:TP391; When the edges of a convex polygon are traversed along one direction, the interior of the convex polygon is always on the same side of the edges. Based on this characteristic of convex polygons, a new algorithm for computing the convex hull of a simple polygon is proposed in this paper, which is then extended to a new algorithm for computing the convex hull of a planar point set. First, the extreme points of the planar point set are found, and the subsets of point candidate for vertex of the convex hull between extreme points are obtained. Then, the ordered convex hull point sequences between extreme points are constructed separately and concatenated by removing redundant extreme points to get the convex hull. The time complexity of the new planar convex hull algorithm is O(nlogh), which is equal to the time complexity of the best output-sensitive planar convex hull algorithms.Compared with the algorithm having the same complexity, the new algorithm is much faster.
ISSN:1673-565X
1862-1775
DOI:10.1631/jzus.2007.A1210