An efficient convex hull algorithm using affine transformation in planar point set. (English) Zbl 1327.65040
Summary: When trying to find the convex hull (CH) of a point set, humans can neglect most non-vertex points by an initial estimation of the boundary of the point set easily. The proposed CH algorithm imitates this characteristic of visual attention, starts by constructing an initial convex polygon (ICP), and measures the width and length of ICP through a shape estimation step. It then maps the point set into the new one by an affine transformation and makes most of the new points exist in a new initial convex polygon (NICP) which approximated to a regular convex polygon. Next, it discards the interior points in NICP by an inscribed circle and processes the remaining points outside NICP by Quickhull. Finally, the algorithm outputs the vertex set of CH. Two theorems are also proposed to solve an unconstrained optimization problem instead of the iteration method. Compared with four popular CH algorithms, the proposed algorithm can generate CH much faster than them and achieve a better performance.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
Software:
QhullReferences:
| [1] | Casale P., Pujol O., Radeva P.: Approximate polytope ensemble for one-class classification. Pattern Recogn. 47(2), 854-864 (2014) · Zbl 1326.68218 · doi:10.1016/j.patcog.2013.08.007 |
| [2] | Stein A., Geva E., El-Sana J.: Cudahull: fast parallel 3d convex hull on the gpu. Comput. Graph. 36(4), 265-271 (2012) · doi:10.1016/j.cag.2012.02.012 |
| [3] | Tang S., Motlagh O., Ramli A., Ismail N., Nia D.N.: A novel ga-fcm strategy for motion learning and prediction: application in wireless tracking of intelligent subjects. Arab. J. Sci. Eng. 37(7), 1929-1958 (2012) · doi:10.1007/s13369-012-0274-6 |
| [4] | Yang Z., Cohen F.S.: Image registration and object recognition using affine invariants and convex hulls. IEEE Trans. Image Process. 8(7), 934-946 (1999) · Zbl 0948.68204 · doi:10.1109/83.772236 |
| [5] | Kim, B.; Kim, K.J.: Computing the convex hull for a set of spheres on a gpu. In: Proceedings of the 11th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and its Applications in Industry. ACM, pp. 345-345 (2012) |
| [6] | Nayyar Z.A., Zaigham N.A.: Assessment of wind potential in southeastern part of Pakistan along coastal belt of Arabian sea. Arab. J. Sci. Eng. 38(7), 1917-1927 (2013) · doi:10.1007/s13369-013-0546-9 |
| [7] | Krvr C.E., Ivan S. et al.: Sequential and parallel approximate convex hull algorithms. Comput. Artif. Intell. 14(6), 597-610 (1995) |
| [8] | Graham R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett. 1(4), 132-133 (1972) · Zbl 0236.68013 · doi:10.1016/0020-0190(72)90045-2 |
| [9] | Jarvis R.A.: On the identification of the convex hull of a finite set of points in the plane. Inf. Process. Lett. 2(1), 18-21 (1973) · Zbl 0256.68041 · doi:10.1016/0020-0190(73)90020-3 |
| [10] | Andrew A.: Another efficient algorithm for convex hulls in two dimensions. Inf. Process. Lett. 9(5), 216-219 (1979) · Zbl 0423.68032 · doi:10.1016/0020-0190(79)90072-3 |
| [11] | Chan T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discret. Comput. Geom. 16(4), 361-368 (1996) · Zbl 0857.68111 · doi:10.1007/BF02712873 |
| [12] | Liu G., Chen C.: A new algorithm for computing the convex hull of a planar point set. J. Zhejiang Univ. Sci. A 8(8), 1210-1217 (2007) · Zbl 1142.65024 · doi:10.1631/jzus.2007.A1210 |
| [13] | Zhang X., Tang Z., Yu J., Guo M., Jiang L.: Convex hull properties and algorithms. Appl. Math. Comput. 216(11), 3209-3218 (2010) · Zbl 1195.65023 · doi:10.1016/j.amc.2010.04.044 |
| [14] | Kim Y.J., Lee J., Kim M.S., Elber G.: Efficient convex hull computation for planar freeform curves. Comput. Graph. 35(3), 698-705 (2011) · doi:10.1016/j.cag.2011.03.028 |
| [15] | Sharif M.: A new approach to compute convex hull. Innov. Syst. Design Eng. 2(3), 186-192 (2011) |
| [16] | Liu R., Fang B., Tang Y.Y., Wen J., Qian J.: A fast convex hull algorithm with maximum inscribed circle affine transformation. Neurocomputing 77(1), 212-221 (2012) · doi:10.1016/j.neucom.2011.09.011 |
| [17] | Clarkson, K.L.; Mulzer, W.; Seshadhri, C.: Self-improving algorithms for coordinate-wise maxima and convex hulls. In: Proceedings of the 2012 Symposium on Computational Geometry. ACM, pp. 277-286 (2012) · Zbl 1293.68285 |
| [18] | Barber C.B., Dobkin D.P., Huhdanpaa H.: The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. (TOMS) 22(4), 469-483 (1996) · Zbl 0884.65145 · doi:10.1145/235815.235821 |
| [19] | Chadnov R.V.; Skvortsov A.V.: Convex hull algorithms review. In: Proceedings of 8th Russian-Korean International Symposium on Science and Technology. ACM, pp. 112-115 (2004) |
| [20] | Robert, F.; Simon, P.; Ashley, W.; Erik, W.: Affine transformation. http://homepages.inf.ed.ac.uk/rbf/HIPR2/affine.htm (2003). Accessed 1 Jul 2013 |
| [21] | Tzimiropoulos G., Mitianoudis N., Stathaki T.: Robust recognition of planar shapes under affine transforms using principal component analysis. IEEE Signal Process. Lett. 14(10), 723-726 (2007) · doi:10.1109/LSP.2007.896434 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
