A linear-time algorithm to compute the triangular hull of a digital object.(English)Zbl 1370.68303
Summary: A linear-time algorithm for determining the triangular hull of a digital object that is digitized with a uniform triangular-grid scan, is presented in this paper. A triangular hull consists of a sequence of edges on the underlying triangular grid \(\mathbb{T}\) consisting of three sets of parallel grid lines that are inclined at \(0^\circ\), \(60^\circ\), and \(120^\circ\) w.r.t. the \(x\)-axis. The proposed algorithm determines the triangular hull of a given object on the basis of certain geometrical properties of the edge-sequence observed along its boundary. The approach is purely combinatorial in nature as opposed to other conventional algorithms used for computing the convex hull such as those based on divide-and-conquer or line-sweep. The running time of the algorithm is linear on the number of pixels on the perimeter of the object. Also, by using a more sparse grid, i.e., by increasing the grid unit, the number of perimeter-pixels, and in turn, the running time of the algorithm can be reduced proportionately. The algorithm is tested extensively on several test cases and experimental results and analysis are presented.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68U10 | Computing methodologies for image processing |
Software:
QhullCite
Full Text:DOI
References:
| [2] | Barber, B. B.; Dobkin, D. P.; Huhdanpaa, H., The quickhull algorithm for convex hulls, ACM Trans. Math. Software, 22, 4, 469-483 (1996) ·Zbl 0884.65145 |
| [3] | Biswas, A.; Bhowmick, P.; Sarkar, M.; Bhattacharya, B. B., Finding the orthogonal hull of digital object: a combinatorial approach, (Intl. Workshop on Combinatorial Image Analysis, IWCIA, vol. 4958 (2008), Springer: Springer Berlin Heidelberg), 124-135 |
| [4] | Chazelle, B., An optimal convex hull algorithm in any fixed dimension, Discrete Comput. Geom, 10, 377-409 (1993) ·Zbl 0786.68091 |
| [5] | Das, B.; Dutt, M.; Biswas, A.; Bhowmick, P.; Bhattacharya, B. B., A combinatorial technique for construction of triangular covers of digital objects, (16th International Workshop on Combinatorial Image Analysis: IWCIA’14, Brno, Czech Republic, vol. 8466 (2014), Springer International Publishing), 76-90 ·Zbl 1486.68209 |
| [6] | Graham, R., An efficient algorithm for determining the convex hull of a finite point set, Info. Proc. Letters, 1, 132-133 (1972) ·Zbl 0236.68013 |
| [7] | Hashorva, E., Asymptotics of the convex hull of spherically symmetric samples, Discrete Appl. Math., 159, 4, 201-211 (2011) ·Zbl 1228.60021 |
| [8] | Jarvis, R. A., On the identification of the convex hull of a finite set of points in the plane, Info. Proc. Letters, 2, 18-21 (1973) ·Zbl 0256.68041 |
| [9] | Karavelas, M. I.; Seidel, R.; Tzanaki, E., Convex hulls of spheres and convex hulls of disjoint convex polytopes, Comput. Geom., Theory Appl., 46, 6, 615-630 (2013) ·Zbl 1267.52025 |
| [10] | Kirkpatrick, D. G.; Seidel, R., The ultimate planar convex hull algorithm, SIAM J. Comput., 15, 287-299 (1986) ·Zbl 0589.68035 |
| [11] | Klette, G., A recursive algorithm for calculating the relative convex hull, (Proc. of 25th International Conference on Image and Vision Computing New Zealand, IVCNZ (2010), IEEE), 1-7 |
| [12] | Klette, R.; Rosenfeld, A., Digital Geometry: Geometric Methods for Digital Picture Analysis, (Morgan Kaufmann Series in Computer Graphics and Geometric Modeling (2004), Morgan Kaufmann: Morgan Kaufmann San Francisco) ·Zbl 1064.68090 |
| [13] | Lopez-Chau, A.; Xiaoou, L.; Wen, Y., Convex-concave hull for classification with support vector machine, (Proc. of 12th International Conference on Data Mining Workshops, ICDMW (2012), IEEE), 431-438 |
| [14] | Schulz, H., Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets, Discrete Appl. Math., 157, 16, 3485-3493 (2009) ·Zbl 1186.68510 |
| [15] | Swart, G., Finding the convex hull facet by facet, J. Algorithms, 6, 1, 17-48 (1985) ·Zbl 0563.68041 |
| [16] | Woun, B. S.; Tan, G. Y.; Ang, M. H.; Wong, Y. P., A hybrid convex hull algorithm for fingertips detection, (Proc. of 11th International Conference on Computer Graphics, Imaging and Visualization, CGIV (2014), IEEE), 78-82 |
| [17] | Zhong, J.; Tan, K.; Qin, A. K., Finding convex hull vertices in metric space, (Proc. of International Joint Conference on Neural Networks, IJCNN (2014), IEEE), 1587-1592 |
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.
