Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Acta Informatica
Published in: Acta Informatica 4/2023

01-08-2023 | Review

Dot to dot, simple or sophisticated: a survey on shape reconstruction algorithms

Authors: Farnaz Sheikhi, Behnam Zeraatkar, Sama Hanaie

Published in: Acta Informatica | Issue 4/2023

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Dot pattern points are the samples taken from all regions of a 2D object, either inside or the boundary. Given a set of dot pattern points in the plane, the shape reconstruction problem seeks to find the boundaries of the points. These boundaries are not mathematically well-defined. Hence, a superior algorithm is the one which produces the result closest to the human visual perception. There are different challenges in designing these algorithms, such as the independence from human supervision, and the ability to detect multiple components, holes and sharp corners. In this paper, we present a thorough review on the rich body of research in shape reconstruction, classify the ideas behind the algorithms, and highlight their pros and cons. Moreover, to overcome the barriers of implementing these algorithms, we provide an integrated application to visualize the outputs of the prominent algorithms for further comparison.
previous article Editorial 2023: changes and invariants
next article Testing membership for timed automata

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
2.
Acharyya, A., De, M., Nandy, S.C., Pandit, S.: Variations of largest rectangle recognition amidst a bichromatic point set. Discrete Appl. Math. 286, 35–50 (2020)MathSciNetMATHCrossRef
3.
Agarwal, P.K., de Berg, M., Matousek, J., Schwarzkopf, O.: Constructing levels in arrangements and higher order Voronoi diagrams. SIAM J. Comput. 27(3), 654–667 (1998)MathSciNetMATHCrossRef
4.
Ahlvers, U., Rajagopalan, R., Zlzer, U.: Model-free face detection and head tracking with morphological hole mapping. In: 2005 13th European Signal Processing Conference, pp. 1–4 (2005)
5.
Arampatzis, A., Kreveld, M.V., Reinbacher, I., Jones, C.B., Vaid, S., Clough, P., Joho, H., Sanderson, M.: Web-based delineation of imprecise regions. Comput. Environ. Urban Syst. 30(4), 436–459 (2006)CrossRef
6.
Asaeedi, S., Didehvar, F., Mohades, A.: \(\alpha \)-concave hull, a generalization of convex hull. Theor. Comput. Sci. 702, 48–59 (2017)MathSciNetMATHCrossRef
7.
8.
Bae, S.W., Lee, C., Ahn, H.-K., Choi, S., Chwa, K.-Y.: Maintaining extremal points and its applications to deciding optimal orientations. In: Tokuyama, T. (ed.) Algorithms and Computation, pp. 788–799. Springer, Berlin (2007)MATHCrossRef
9.
Bae, S.W., Lee, C., Ahn, H.-K., Choi, S., Chwa, K.-Y.: Computing minimum-area rectilinear convex hull and L-shape. Comput. Geom. 42(9), 903–912 (2009)MathSciNetMATHCrossRef
10.
Batsanov, S.S.: Van der Waals radii of elements. Inorg. Mater. 37, 871–885 (2001)CrossRef
11.
Boyce, J.E., Dobkin, D.P., Drysdale, R.L.S., III., Guibas, L.J.: Finding extremal polygons. SIAM J. Comput. 14(1), 134–147 (1985)MathSciNetMATHCrossRef
12.
Chaudhuri, A.R., Chaudhuri, B.B., Parui, S.K.: A novel approach to computation of the shape of a dot pattern and extraction of its perceptual border. Comput. Vis. Image Underst. 68, 257–275 (1997)CrossRef
13.
14.
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Cham (2000)MATHCrossRef
15.
de Figueiredo, L.H., Paiva, A.: Region reconstruction with the sphere-of-influence diagram. Comput. Graph. 107, 252–263 (2022)CrossRef
16.
Dey, T.K., Wang, Y.: Computational Topology for Data Analysis. Cambridge University Press, Cambridge (2022)MATHCrossRef
17.
Duckham, M., Kulik, L., Worboys, M., Galton, A.: Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recogn. 41(10), 3224–3236 (2008)MATHCrossRef
18.
Edelsbrunner, H.: Weighted alpha shapes. Technical report, USA (1992)
19.
Edelsbrunner, H.: Shape reconstruction with Delaunay complex. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN’98: Theoretical Informatics, pp. 119–132. Springer, Berlin (1998)CrossRef
20.
Edelsbrunner, H., Kirkpatrick, D., Seidel, R.: On the shape of a set of points in the plane. IEEE Trans. Inf. Theory 51, 551–559 (1983)MathSciNetMATHCrossRef
21.
Ertöz, L., Steinbach, M., Kumar, V.: Finding clusters of different sizes, shapes, and densities in noisy, high dimensional data. In: Proceedings of the 2003 SIAM International Conference on Data Mining (SDM), pp. 47–58 (2003)
22.
Fekete, S.P., Pulleyblank, W.R.: Area optimization of simple polygons. In: SCG ’93 (1993)
23.
Galton, A., Duckham, M.: What is the region occupied by a set of points? In: Raubal, M., Miller, H.J., Frank, A.U., Goodchild, M.F. (eds.) Geographic Information Science, pp. 81–98. Springer, Berlin (2006)CrossRef
24.
Ghadai, S., Balu, A., Sarkar, S., Krishnamurthy, A.: Learning localized features in 3D CAD models for manufacturability analysis of drilled holes. Comput. Aided Geom. Des. 62, 263–275 (2018)MathSciNetMATHCrossRef
25.
Gheibi, A., Davoodi, M., Javad, A., Panahi, S., Aghdam, M., Asgaripour, M., Mohades, A.: Polygonal shape reconstruction in the plane. IET Comput. Vis. 5, 97–106 (2011)CrossRef
26.
Ghosh, P., Gao, J., Gasparri, A., Krishnamachari, B.: Distributed hole detection algorithms for wireless sensor networks. In: 2014 IEEE 11th International Conference on Mobile Ad Hoc and Sensor Systems, pp. 257–261 (2014)
27.
Guler, T., Gross, G.: Detection of island formation and identification of causal factors under multiple line outages. IEEE Trans. Power Syst. 22(2), 505–513 (2007)CrossRef
28.
Jarvis, R.: On the identification of the convex hull of a finite set of points in the plane. Inf. Process. Lett. 2(1), 18–21 (1973)MATHCrossRef
29.
Jayanti, S., Kalyanaraman, Y., Iyer, N., Ramani, K.: Developing an engineering shape benchmark for CAD models. Comput. Aided Des. 38(9), 939–953 (2006)CrossRef
30.
Krasnoshchekov, D., Polishchuk, V.: Order-\(k\)\(\alpha \)-hulls and \(\alpha \)-shapes. Inf. Process. Lett. 114(1), 76–83 (2014)MathSciNetMATHCrossRef
31.
Lee, D.-T.: On \(k\)-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput. C–31(6), 478–487 (1982)MathSciNetMATH
32.
Liu, Y., Nediak, M.: Planar case of the maximum box and related problems. In: Canadian Conference on Computational Geometry (CCCG), pp. 14–18 (2003)
33.
34.
Melkemi, M., Djebali, M.: Computing the shape of a planar points set. Pattern Recogn. 33(9), 1423–1436 (2000)CrossRef
35.
Melkemi, M., Djebali, M.: Weighted A-shape: a descriptor of the shape of a point set. Pattern Recogn. 34(6), 1159–1170 (2001)MATHCrossRef
36.
37.
Methirumangalath, S., Kannan, S.S., Parakkat, A.D., Muthuganapathy, R.: Hole detection in a planar point set: an empty disk approach. Comput. Graph. 66, 124–134 (2017)CrossRef
38.
Methirumangalath, S., Parakkat, A.D., Muthuganapathy, R.: A unified approach towards reconstruction of a planar point set. Comput. Graph. 51, 90–97 (2015)CrossRef
39.
Moreira, A., Santos, M.Y.: Concave hull: a \(k\)-nearest neighbours approach for the computation of the region occupied by a set of points. In: Proceedings of the Second International Conference on Computer Graphics Theory and Applications (2007)
40.
Ohrhallinger, S., Peethambaran, J., Parakkat, A.D., Dey, T.K., Muthuganapathy, R.: 2D points curve reconstruction survey and benchmark. Comput. Graph. Forum 40(2), 611–632 (2021)CrossRef
41.
Oliveira, E., Furtado, V., Andrade, J., Makse, H.: A worldwide model for boundaries of urban settlements. R. Soc. Open Sci. 5, 180468 (2018)CrossRef
42.
Parakkat, A.D., Memari, P., Cani, M.-P.: Layered reconstruction of stippling art. In: SIGGRAPH 2019 (Poster Proceedings), Los Angeles, United States (2019). hal-02193269f
43.
Peethambaran, J., Muthuganapathy, R.: A non-parametric approach to shape reconstruction from planar point sets through Delaunay filtering. Comput. Aided Des. 62, 164–175 (2015)CrossRef
44.
Peethambaran, J., Ohrhallinger, S., Parakkat, A.D.: Shape characterization of point sets in 2D. EUROGRAPHICS 2022/ S. Hahmann and G. Patow-Tutorial (2022)
45.
Richards, F.M.: Areas, volumes, packing, and protein structure. Annu. Rev. Biophys. Bioeng. 6(1), 151–176 (1977)CrossRef
46.
Seara, C.: On geometric separability. Ph.D. thesis, Universidad Politécnica De Catalunya (2002)
47.
Serra, J.: Image Analysis and Mathematical Morphology. Academic Press Inc., USA (1983)
48.
49.
Sheikhi, F., Mohades, A.: Maximum separability by L-shapes. In: 2020 25th International Computer Conference, Computer Society of Iran (CSICC), pp. 1–7 (2020)
50.
Sheikhi, F., Mohades, A., de Berg, M., Davoodi, M.: Separating bichromatic point sets by L-shapes. Comput. Geom. 48(9), 673–687 (2015)MathSciNetMATHCrossRef
51.
52.
53.
Thayyil, S.B., Parakkat, A.D., Muthuganapathy, R.: An input-independent single pass algorithm for reconstruction from dot patterns and boundary samples. Comput. Aided Geom. Des. 80, 101879 (2020)MathSciNetMATHCrossRef
54.
Toussaint, G.: Solving geometric problems with the rotating calipers. In: Proceedings of IEEE MELECON ’83, pp. A10.02/1–4 (1983)
55.
Toussaint, G.T.: A graph-theoretical primal sketch. In: Toussaint, G.T. (ed.) Computational Morphology, Volume 6 of Machine Intelligence and Pattern Recognition, pp. 229–260. North-Holland, Amsterdam (1988)
56.
Toussaint, G.T.: The sphere of influence graph: theory and applications. Int. J. Inf. Technol. Comput. Sci. 14, 37–42 (2014)
57.
van Kreveld, M., van Lankveld, T., de Rie, M.: (\(\alpha ,\delta \))-sleeves for reconstruction of rectilinear building facets. In: Proceedings of the 7th International 3D GeoInfo Conference, Lecture Notes in Geoinformation and Cartography, pp. 231–248. Springer, Berlin (2013)
58.
van Kreveld, M., van Lankveld, T., Veltkamp, R.: Identifying well-covered minimal bounding rectangles in 2D point data. In: 25th European Workshop on Computational Geometry, pp. 277–280 (2009)
59.
van Lankveld, T., van Kreveld, M., Veltkamp, R.: Identifying rectangles in laser range data for urban scene reconstruction. Comput. Graph. 35(3), 719–725 (2011)CrossRef
60.
Veltkamp, R.C.: Shape matching: similarity measures and algorithms. In: Proceedings International Conference on Shape Modeling and Applications, pp. 188–197 (2001)
Metadata
Title
Dot to dot, simple or sophisticated: a survey on shape reconstruction algorithms
Authors
Farnaz Sheikhi
Behnam Zeraatkar
Sama Hanaie
Publication date
01-08-2023
Publisher
Springer Berlin Heidelberg
Published in
Acta Informatica / Issue 4/2023
Print ISSN: 0001-5903
Electronic ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-023-00443-7

Other articles of this Issue 4/2023

Acta Informatica 4/2023 Go to the issue

Editorial

Editorial 2023: changes and invariants

Original Article

Testing membership for timed automata

Original Article

The second step in characterizing a three-word code

Original Article

On first-order runtime enforcement of branching-time properties

Premium Partner

    Image Credits