International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 9, No. 3, 8 Mar. 2017
Cover page and Table of Contents: PDF (size: 648KB)
A Concave Hull Based Algorithm for Object Shape Reconstruction
Full Text (PDF, 648KB), PP.1-9
Views: 0 Downloads: 0
Author(s)
Zahrah Yahya
1,*
Rahmita W Rahmat
2
Fatimah Khalid
2
Amir Rizaan
2
Ahmad Rizal
3
Index Terms
Convex hull, concave hull, vertices, shape reconstruction
Abstract
Hull algorithms are the most efficient and closest methods to be redesigned for connecting vertices for geometric shape reconstruction. The vertices are the input points representing the original object shape. Our objective is to reconstruct the shape and edges but with no information on any pattern, it is challenging to reconstruct the lines to resemble the original shape. By comparing our results to recent concave hull based algorithms, two performance measures were conducted to evaluate the accuracy and time complexity of the proposed method. Besides achieving the most acceptable accuracy which is 100%, the time complexity of the proposed algorithm is evaluated to be O(wn). All results have shown a competitive and more effective algorithm compared to the most efficient similar ones. The algorithm is shown to be able to solve the problems of vertices connection in an efficient way by devising a new approach.
Cite This Paper
Zahrah Yahya, Rahmita W Rahmat, Fatimah Khalid, Amir Rizaan, Ahmad Rizal, "A Concave Hull Based Algorithm for Object Shape Reconstruction", International Journal of Information Technology and Computer Science(IJITCS), Vol.9, No.3, pp.1-9, 2017. DOI:10.5815/ijitcs.2017.03.01
Reference
[1]A. Galton and M. Duckham, “What is the region occupied by a set of points?,” in Geographic Information Science, Springer, 2006, pp. 81–98.
[2]T. M. Chan, “Optimal output-sensitive convex hull algorithms in two and three dimensions,” Discrete Comput. Geom., vol. 16, no. 4, pp. 361–368, 1996.
[3]K. L. Clarkson and P. W. Shor, “Applications of random sampling in computational geometry, II,” Discrete Comput. Geom., vol. 4, no. 1, pp. 387–421, 1989.
[4]R. L. Graham, “An efficient algorith for determining the convex hull of a finite planar set,” Inf. Process. Lett., vol. 1, no. 4, pp. 132–133, 1972.
[5]R. A. Jarvis, “On the identification of the convex hull of a finite set of points in the plane,” Inf. Process. Lett., vol. 2, no. 1, pp. 18–21, 1973.
[6]E. Rosén, E. Jansson, and M. Brundin, “Implementation of a fast and efficient concave hull algorithm,” 2014.
[7]J.-S. Park and S.-J. Oh, “A new concave hull algorithm and concaveness measure for n-dimensional datasets,” J. Inf. Sci. Eng., vol. 29, no. 2, pp. 379–392, 2013.
[8]T. Ebert, J. Belz, and O. Nelles, “Interpolation and extrapolation: Comparison of definitions and survey of algorithms for convex and concave hulls,” in Computational Intelligence and Data Mining (CIDM), 2014 IEEE Symposium on, 2014, pp. 310–314.
[9]H. Edelsbrunner, D. G. Kirkpatrick, and R. Seidel, “On the shape of a set of points in the plane,” Inf. Theory IEEE Trans. On, vol. 29, no. 4, pp. 551–559, 1983.
[10]M. Melkemi and M. Djebali, “Computing the shape of a planar points set,” Pattern Recognit., vol. 33, no. 9, pp. 1423–1436, 2000.
[11]A. Moreira and M. Y. Santos, “Concave hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points,” 2007.
[12]M. Duckham, L. Kulik, M. Worboys, and A. Galton, “Efficient generation of simple polygons for characterizing the shape of a set of points in the plane,” Pattern Recognit., vol. 41, no. 10, pp. 3224–3236, 2008.
[13]S. Meintjes, “Multi-objective optimisation of a commercial vehicle complex network,” University of Pretoria, 2013.
[14]S. Methirumangalath, A. D. Parakkat, and R. Muthuganapathy, “A unified approach towards reconstruction of a planar point set,” Comput. Graph., 2015.
[15]I. Chivers, J. Sleightolme, "An Introduction to Algorithms and the Big O Notation", Introduction to Programming with Fortran, Springer, 2015, pp.359-364