A Survey and Comparative Study for Connecting 2D points

Authors

  • Jijith K  M. Tech Scholar, Department of Computer Science and Engineering, Government Engineering College, Idukki, Kerala, India
  • Philumon Joseph  Assistant Professor, , Department of Computer Science and Engineering, Government Engineering College, Idukki, Kerala, India

DOI:

https://doi.org//10.32628/IJSRSET207133

Keywords:

Curve reconstruction, shape reconstruction, sampling, 2D point sets

Abstract

Reconstruction from noisy point sets has many ap-plications in the areas of science and engineering. Research effort in reconstructing shape from noisy point sets. Reconstruction on planar point including shape, surface, curve and manifold recon-struction. Good algorithms are required to create a good shape from a given point set. Better local and global sampling conditions form the base of these algorithms. Reconstruction from noisy point set is not extensively studied and therefore the researchers do not have a successful algorithm. Reconstruction from the stage is begun before many decades and these activities are now being extended for a few days. Extending any older reconstruction algorithms needs a good understanding and comparison of all previous algorithms. This survey is spamming on different reconstruction algorithms, various local sampling conditions, extension of different works and their working conditions and reconstruction implementation from point sets. Survey begins after 1997 and compares various extension works. The sampling condition for all these algorithms contributes significantly to the construction of algorithms, thus different local sampling conditions are investigated. During this study, all algorithms for reconstruction are tabulated and different parameters for these algorithms are compared. This survey is concluding with several promising directions for the future works on reconstruction.

References

  1. Herbert Edelsbrunner, David G . Kirkpatrick,And Raimund Seidel, “On the shape of a set of points in the plane,” in IEEE ,2000,
  2. Luiz Henrique de FigueiredoJonas de Miranda Gomes, Computational morphology of curves.The Visual Computer , February 1994, Volume 11, Issue 2, pp 105–112
  3. David G.Kirkpatrick, John D.Radke, “A Framework for Computational Morphology,” Elsevier Machine Intelligence and Pattern Recognition, Volume 2, 1985, Pages 217-248
  4. RemcoC.Veltkamp,3DComputationalMorphologyr,CWI,Dept.Interactive Systems ATTALI D, “r -regular shape reconstruction from unorga- nized points.,” In Symp. Comp. Geom.., (1997), pp. 248–253. 2
  5. A MENTA N., B ERN M. W., E PPSTEIN D, “The crust and the beta-skeleton: Combinatorial curve reconstruction.,”Graphical Models and Image Processing. 60, 2 (1998), 125–135. 2, 3, 13, 14, 15, 16
  6. DEY T.K., K UMAR P, A simple provable algorithm for curve recon-struction.In Proc. 10th ACM-SIAM SODA ’99 (1999), pp. 893–894. 2, 15, 16
  7. D EY T. K., M EHLHORN K., R AMOS E. A, Curve reconstruction: Connecting dots with good reason.In Proc. 15th ACM Symp. Comp. Geom 15 (1999), 229–244. 2
  8. ZENG Y.,N GUYEN T. A., YAN B., LIS, A distance- based parameter free algorithm for curve reconstruction.Computer Aided Des. 40, 2 (2008), 210–222. 2, 9, 13
  9. N GUYEN T. A., ZENG Y, Vicur: A human-vision-based algorithm for curve reconstruction.Robotics and Computer Integrated Manufacturing 24, 6 (2008), 824 – 834. FAIM 2007, 17th Int. Conf. on Flexible Automation and Intellig. Manufact.
  10. G LANVILL M., B ROUGHAN K, Curve and surface re- construction in r2 and r3.In HPC-ASIA ’97: Proceedings of the High-Performance Computing on the Information Superhighway, HPC-Asia ’97 (Washing-ton, DC, USA, 1997), IEEE Computer Society,
  11. G IESEN J, Curve reconstruction in arbitrary dimension and the traveling salesman problem.In Proc. 8th DCGI ’99 (1999), pp. 164–176. 3
  12. A LTHAUS E., M EHLHORN K, Tsp-based curve reconstruction in polynomial timeIn SODA ’00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms (Philadelphia, PA, USA, 2000), Society for Industrial and Applied Mathematics, pp. 686–695. 3, 5, 9
  13. ARORA S, Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems.In Journal of the ACM (1996), pp. 2–11. 3
  14. ALTHAUS E., M EHLHORN K, N AHER S., S CHIRRASs, Experi-ments on curve reconstruction.In Proc. 2nd Workshop Algorithm Eng. Exper (2000), pp. 103–114. 3, 13
  15. GIESEN J, Curve reconstruction in arbitrary dimension and the trav-eling salesman problem.In Proc. 8th DCGI ’99 (1999), pp. 164–176. 3
  16. HOOSH. H, On the Empirical Scaling of Run-time for Finding Optimal Solutions to the Traveling Salesman Problem.Technical Report 17, University of British Columbia, Department of Computer Science, 2009. 3
  17. OHRHALLINGER S., MUDUR S, Minimising Longest Edge for Closed Surface Construction from Unorganised 3DPoint Sets. In EG 2012 - Poster Proc. (2012), pp. 25–26. 17
  18. OHRHALLINGER S, Source-code for shape extraction algorithm,.May 2011. https://sourceforge.net/p/connect2dlib/home/. 8
  19. DEY T. K., MEHLHORN K., RAMOS E. A, Curve recon- struction: Connecting dots with good reason.In Proc. 15th ACM Symp. Comp. Geom 15 (1999), 229–244. 2
  20. DEY T. K., WENGER R, Fast reconstruction of curves with sharp cornersInt. J. Comp. Geom. Appl. 12, 5 (2002), 353 – 400. 2, 7, 8
  21. FUNKE S., RAMOS E. A, Reconstructing a collection of curves with corners and endpointsIn Proceedings of the twelfth annual ACMSIAM symposium on Discrete algorithms (Philadelphia, PA, USA, 2001), SODA ’01, Society for Industrial and Applied Math., pp. 344–353. 2
  22. ZENG Y., NGUYEN T. A., YAN B., LIS.:, A distance-based parameter free algorithm for curve reconstruction.Comput. Aided Des. 40, 2 (2008), 210–222. 2
  23. NGUYEN T. A., ZENG Y, Vicur: A human-vision-based algorithm for curve reconstruction.Robotics and Computer-Integrated Manufacturing 24, 6 (2008), 824 – 834. FAIM 2007, 17th International Con- ference on Flexible Automation and Intelligent Manufacturing. 2
  24. LEEI.-K, : Curve reconstruction from unorganized points.Com- puter aided geometric design 17, 2 (2000), 161–177. 2, 5, 7, 9
  25. KAZHDAN M., HOPPE H., Screened poisson surface reconstruc-tion.ACM Transactions on Graphics (TOG) 32, 3 (2013), 29. 2
  26. MEHRA R., TRIPATHI P., SHEFFER A., M ITRA N. J, Visibility of noisy point cloud data.Computers Graphics 34, 3 (2010),219–230. 2, 5,7,8
  27. DEGOES F., COHEN -STEINER D., ALLIEZ P, An optimal transport approach to robust reconstruction and simplification of 2d shapes.In Computer Graphics Forum (2011),vol. 30, Wiley Online Library, pp. 1593–1602. 2
  28. WANG J., YUZ., ZHANG W., WEIM., TAN C., DAIN., Z HANG X, Robust reconstruction of 2d curves from scattered noisy point data.Computer-Aided Design 50 (2014), 27–40. 2
  29. RUPNIEWSKI M. Ws, Curve reconstruction from noisy and unordered samples.In 3rd International Conference on Pattern Recognition Appli-cations and Methods (2014), SciTePress. 2
  30. HRHALLINGER S., WIMMER , Fitconnect: Connecting noisy 2d samples by fitted neighbourhoods.In Computer Graphics Forum (2018), Wiley Online Library. 2, 3, 5
  31. GUENNEBAUD G., GROSS M., Algebraic point set surfacesIn ACM Transactions on Graphics (TOG) (2007), vol. 26, ACM, p. 23. 2
  32. OHRHALLINGER S., MITCHELL S. A., WIMMER M, Curve recon-struction with many fewer samples.In Computer Graphics Forum (2016), vol. 35, Wiley Online Library, pp. 167–176. 2
  33. BIRKAS D., BIRKAS K., POPA T, A mobile system for scene mon-itoring and object retrieval.In Proceedings of the 29th International Conference on Computer Animation and Social Agents (2016), ACM, pp. 83–88., Nina amenta and Marshel ben surface reconstruction by veronoi filter-ingACM 1998

International Journal of Scientific Research in Science, Engineering and Technology

Downloads

Published

2020-03-30

Issue

Volume 7, Issue 2, March-April-2020

Section

Research Articles

License

Copyright (c) IJSRSET

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Jijith K, Philumon Joseph, " A Survey and Comparative Study for Connecting 2D points, International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 7, Issue 2, pp.10-18, March-April-2020. Available at doi : https://doi.org/10.32628/IJSRSET207133