A Quick Convex Hull Building Algorithm Based on Grid and Binary Tree
| Autor: | Yang Gao, Xuesong Wang, Yuhu Cheng |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Convex hull
Mathematical optimization Applied Mathematics Convex set TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Convex polytope Convex optimization Convex combination Output-sensitive algorithm Electrical and Electronic Engineering Gift wrapping algorithm Algorithm Orthogonal convex hull Mathematics |
| Zdroj: | Chinese Journal of Electronics. 24:317-320 |
| ISSN: | 2075-5597 1022-4653 |
| DOI: | 10.1049/cje.2015.04.015 |
| Popis: | A quick convex hull building algorithm using grid and binary tree is proposed for the minimum convex buidling of planar point set. Grids are used to assess and eliminate those interior points wihtout any contribution to convex hull building and points are sought in the boundary grid only so as to enhance the efficiency of algorithm. The minimum convex bull is built by taking such advantages of binary tree as quick, convenient and applicable for various point sets with different distributions, so as to resolve the description problem of concave point. The time complexity of the algorithm is low because of grid pretreatment. As the results of comparative expriment of random point and actual picture show, the proposed algorithm can obtain the best profile of 2D planar picture with minimum time, which is applicable for describing the shape of irregular convex-concave objects. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text