An Algorithm for Finding Convex Hulls of Planar Point Sets
| Autor: | Mei, Gang, Tipper, John C., Xu, Nengxiong |
|---|---|
| Rok vydání: | 2012 |
| Předmět: | |
| Zdroj: | 2012 2nd International Conference on , vol., no., pp.888,891, 29-31 Dec. 2012 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1109/ICCSNT.2012.6526070 |
| Popis: | This paper presents an alternate choice of computing the convex hulls (CHs) for planar point sets. We firstly discard the interior points and then sort the remaining vertices by x- / y- coordinates separately, and later create a group ofquadrilaterals (e-Quads) recursively according to the sequences ofthe sorted lists of points. Finally, the desired CH is built based on a simple polygon derived from all e-Quads. Besides the preprocessing for original planar point sets, this algorithm has another mechanism of discarding interior point when form e-Quads and assemble the simple polygon. Compared with three popular CH algorithms, the proposed algorithm can generate CHs faster thanthe three but has a penalty in space cost. Comment: Proceedings of IEEE Conference, ICCSNT 2012, in Press |
| Databáze: | arXiv |
| Externí odkaz: |
|