Abstract
Given a set of dot pattern point set P with the size n in the plane, we propose a Delaunay triangulation-based shape reconstruction algorithm, entitled prudent carving, that can reconstruct the inner boundaries (holes) and outer boundaries of P with the same approach. Our prudent carving algorithm is a parameter-free algorithm that has the ability to detect multiple components, sharp corners, and nested holes independent from the number of them in the total \(O(n \log n)\) time. The qualitative and quantitative comparison of the results with the state-of-the-art algorithms shows that the prudent carving algorithm provides an enhancement over the previously best-known algorithms for reconstructing the boundaries of points.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahlvers U, Rajagopalan R, Zölzer U (2005) Model-free face detection and head tracking with morphological hole mapping. In: 2005 13th European signal processing conference., pp 1–4
Bae SW, Lee C, Ahn H-K, Choi S, Chwa K-Y (2009) Computing minimum-area rectilinear convex hull and L-shape. Comput Geom 42(9):903–912
de Berg M, van Kreveld M, Overmars M, Schwarzkopf O (2000) Computational geometry: algorithms and applications, 2nd edn. Springer, Berlin
Duckham M, Kulik L, Worboys M, Galton A (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recogn 41(10):3224–3236
Edelsbrunner H (1998) Shape reconstruction with Delaunay complex. In: Lucchesi CL, Moura AV (eds) LATIN’98: theoretical informatics. Springer, Berlin, pp 119–132
Edelsbrunner H, Kirkpatrick D, Seidel R (1983) On the shape of a set of points in the plane. IEEE Trans Inf Theory 29(4):551–559
Ghadai S, Balu A, Sarkar S, Krishnamurthy A (2018) Learning localized features in 3D CAD models for manufacturability analysis of drilled holes. Comput Aided Geom Des 62:263–275
Gheibi A, Davoodi M, Javad A, Panahi S, Aghdam M, Asgaripour M, Mohades A (2011) Polygonal shape reconstruction in the plane. IET Comput Vision 5:97–106
Jayanti S, Kalyanaraman Y, Iyer N, Ramani K (2006) Developing an engineering shape benchmark for CAD models. Comput Aided Des 38(9):939–953
Liu Y, Nediak M (2003) Planar case of the maximum box and related problems. In: Canadian conference on computational geometry (CCCG)
Megiddo N (1982) Linear-time algorithms for linear programming in \({R}^3\) and related problems. In: 23rd annual symposium on foundations of computer science (SFCS 1982), pp 329–338
Melkemi M, Djebali M (2000) Computing the shape of a planar points set. Pattern Recogn 33(9):1423–1436
Methirumangalath S, Kannan SS, Parakkat AD, Muthuganapathy R (2017) Hole detection in a planar point set: an empty disk approach. Comput Gr 66:124–134
Methirumangalath S, Parakkat AD, Muthuganapathy R (2015) A unified approach towards reconstruction of a planar point set. Comput Gr 51:90–97
Oliveira E, Furtado V, Andrade J, Makse H (2018) A worldwide model for boundaries of urban settlements. R Soc Open Sci 5(5):180468
Peethambaran J, Muthuganapathy R (2015) A non-parametric approach to shape reconstruction from planar point sets through Delaunay filtering. Comput Aided Des 62:164–175
Sheikhi F, de Berg M, Mohades A, Monfared MD (2010) Finding monochromatic L-shapes in bichromatic point sets. In: 22nd Canadian conference on computational geometry (CCCG), pp 269–272
Sheikhi F, Mohades A (2018) Planar maximum-box problem revisited. Theoret Comput Sci 729:57–67
Sheikhi F, Mohades A (2020) Maximum separability by L-shapes. In: 2020 25th international computer conference, computer society of Iran (CSICC), pp 1–7
Sheikhi F, Mohades A, de Berg M, Davoodi M (2015) Separating bichromatic point sets by L-shapes. Comput Geom 48(9):673–687
Sheikhi F, Zeraatkar B, Hanaie S (2023) Dot to dot, simple or sophisticated: a survey on shape reconstruction algorithms. Acta Informatica 60(4):335–359
Thayyil SB, Parakkat AD, Muthuganapathy R (2020) An input-independent single pass algorithm for reconstruction from dot patterns and boundary samples. Comput Aided Geom Des 80:101879
Toussaint G (1983) Solving geometric problems with the rotating calipers. In: Proceedings of IEEE MELECON ’83, pp A10.02/1–4
van Kreveld M, van Lankveld T, Veltkamp R (2009) Identifying well-covered minimal bounding rectangles in 2D point data. In: 25th European workshop on computational geometry, pp 277–280
Funding
No funding was received for conducting this study.
Author information
Authors and Affiliations
Contributions
Authors contributed equally to this work.
Corresponding author
Ethics declarations
Conflict of interest
The authors have no Conflict of interest to declare that are relevant to the content of this article.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Sheikhi, F., Zeraatkar, B., Amereh, F. et al. Prudent carving: a progressively refining algorithm for shape reconstruction from dot patterns. J Supercomput 80, 18652–18678 (2024). https://doi.org/10.1007/s11227-024-06175-w
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-024-06175-w