UM
A fast and complete convex-hull algorithm architecture based on ellipse and elastic ellipse methods
Wu X.G.1; Fang B.1; Tang Y.Y.1; Wang P.S.-P.3
2013
Source PublicationInternational Journal of Pattern Recognition and Artificial Intelligence
ISSN02180014
Volume27Issue:8
AbstractThe number of inner points excluded in an initial convex hull (ICH) is vital to the efficiency getting the convex hull (CH) in a planar point set. The maximum inscribed circle method proposed recently is effective to remove inner points in ICH. However, limited by density distribution of a planar point set, it does not always work well. Although the affine transformation method can be used, it is still hard to have a better performance. Furthermore, the algorithm mentioned above fails to deal with the exceptional distribution: the gravity centroid (GC) of a planar point set is outside or on the edge formed by the extreme points in ICH. This paper considers how to remove more inner points in ICH when GC is inside of ICH and completely process the case which mentioned above. Further, we presented a complete algorithm architecture: (1) using the ellipse and elasticity ellipse methods (EM and EEM) to remove more inner points in ICH and process the cases: GC is inside or outside of ICH. (2) Using the traditional methods to process the situation: the initial centroid is on the edge in ICH. It is adaptive to more data sets than other algorithms. The experiments under seven distributions show that the proposed method performs better than other traditional algorithms in saving time and space. © 2013 World Scientific Publishing Company.
Keywordcomputational geometry Convex hull eight directions ellipse method extreme points
DOI10.1142/S0218001413540086
URLView the original
Language英語
Fulltext Access
Citation statistics
Cited Times [WOS]:0   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionUniversity of Macau
Affiliation1.Chongqing University
2.Universidade de Macau
3.Northeastern University
4.Yangtze Normal University
Recommended Citation
GB/T 7714
Wu X.G.,Fang B.,Tang Y.Y.,et al. A fast and complete convex-hull algorithm architecture based on ellipse and elastic ellipse methods[J]. International Journal of Pattern Recognition and Artificial Intelligence,2013,27(8).
APA Wu X.G.,Fang B.,Tang Y.Y.,&Wang P.S.-P..(2013).A fast and complete convex-hull algorithm architecture based on ellipse and elastic ellipse methods.International Journal of Pattern Recognition and Artificial Intelligence,27(8).
MLA Wu X.G.,et al."A fast and complete convex-hull algorithm architecture based on ellipse and elastic ellipse methods".International Journal of Pattern Recognition and Artificial Intelligence 27.8(2013).
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Wu X.G.]'s Articles
[Fang B.]'s Articles
[Tang Y.Y.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Wu X.G.]'s Articles
[Fang B.]'s Articles
[Tang Y.Y.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Wu X.G.]'s Articles
[Fang B.]'s Articles
[Tang Y.Y.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.