Efficient plotting the functions with discontinuities based on combined sampling
DOI:
https://doi.org/10.14311/gi.17.2.2Keywords:
adaptive sampling, combined sampling, recursive approach, stack, discontinuity, polygonal approximation, visualization, map projection, plotting, GIS,Abstract
This article presents a new algorithm for interval plotting of the function y = f(x) based on combined sampling. The proposed method synthesizes the uniform and adaptive sampling approaches and provides a more compact and efficient function representation. During the combined sampling, the polygonal approximation with a given threshold α between the adjacent segments is constructed. The automated detection and treatment of the discontinuities based on the LR criterion are involved. Two implementations, the recursive-based and stack-based, are introduced. Finally, several tests of the proposed algorithms for the different functions involving the discontinuities and several map projection graticules are presented. The proposed method may be used for more efficient sampling the curves (map projection graticules, contour lines, or buffers) in geoinformatics.References
Francesc Arandiga and Albert Cohen and Rosa Donat and Nira Dyn, "Interpolation and Approximation of Piecewise Smooth Functions", SIAM Journal on Numerical Analysis 43, 1 (2005), pp. 41-57.
Archibald, Rick and Gelb, Anne and Yoon, Jungho, "Determining the locations and discontinuities in the derivatives of functions", Applied Numerical Mathematics 58, 5 (2008), pp. 577--592.
Backes, André Ricardo and Bruno, Odemir Martinez, "Polygonal approximation of digital planar curves through vertex betweenness", Information Sciences 222 (2013), pp. 795--804.
Banerjee, Nana S. and Geer, James F. and Langley Research Center., Exponential approximations using fourier series partial sums [microform] / Nana S. Banerjee and James F. Geer (National Aeronautics and Space Administration, Langley Research Center ; National Technical Information Service, distributor Ha…, 1997).
Bauer, Robert Bruce, "Band pass filters for determining shock locations", ().
Frédéric Benhamou and William J. Older, "Applying interval arithmetic to real, integer, and boolean constraints", The Journal of Logic Programming 32, 1 (1997), pp. 1 - 24.
Binev, P. and Dahmen, W. and DeVore, R. and Dyn, N., "Adaptive approximation of curves", Approximation Theory (2004), pp. 43-57.
Mira Bozzini and Milvia Rossini, "The detection and recovery of discontinuity curves from scattered data", Journal of Computational and Applied Mathematics 240, Supplement C (2013), pp. 148 - 162. MATA 2012
Carmona-Poyato, A and Madrid-Cuevas, Francisco José and Medina-Carnicer, R and Muñoz-Salinas, Rafael, "Polygonal approximation of digital planar curves through break point suppression", Pattern Recognition 43, 1 (2010), pp. 14--25.
Cates, Dennis and Gelb, Anne, "Detecting derivative discontinuity locations in piecewise continuous functions from Fourier spectral data", Numerical Algorithms 46, 1 (2007), pp. 59--84.
Eckhoff, Knut S, "Accurate reconstructions of functions of finite regularity from truncated Fourier series expansions", Mathematics of Computation 64, 210 (1995), pp. 671--690.
Fateman, Richard, "Honest Plotting, Global Extrema, and Interval Arithmetic", in Papers from the International Symposium on Symbolic and Algebraic Computation (New York, NY, USA: ACM, 1992), pp. 216--223.
Gelb, Anne and Tadmor, Eitan, "Spectral reconstruction of piecewise smooth functions from their discrete data", ESAIM: Mathematical Modelling and Numerical Analysis 36, 2 (2002), pp. 155--175.
Gelb, Anne and Tadmor, Eitan, "Adaptive edge detectors for piecewise smooth data based on the minmod limiter", Journal of Scientific Computing 28, 2 (2006), pp. 279--306.
Geman, Stuart and Geman, Donald, "Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images", IEEE Transactions on pattern analysis and machine intelligence (1984), pp. 721--741.
Gutzmer, Tim and Iske, Armin, "Detection of discontinuities in scattered data approximation", Numerical Algorithms 16, 2 (1997), pp. 155--170.
Hickey, Timothy J. and Qju, Zhe and Van Emden, Maarten H., "Interval Constraint Plotting for Interactive Visual Exploration of Implicitly Defined Relations", Reliable Computing 6, 1 (2000), pp. 81--92.
Hu, Yifan, "Efficient, high-quality force-directed graph drawing", Mathematica Journal 10, 1 (2005), pp. 37--71.
Jiang, Guang-Shan and Shu, Chi-Wang, "Efficient implementation of weighted ENO schemes", Journal of computational physics 126, 1 (1996), pp. 202--228.
Kvernadze, George, "Determination of the jumps of a bounded function by its Fourier series", Journal of approximation theory 92, 2 (1998), pp. 167--190.
David Lee, "Detection, Classification, and Measurement of Discontinuities", SIAM Journal on Scientific and Statistical Computing 12, 2 (1991), pp. 311-341.
Lee, David and Wasilkowski, Grzegorz W, "Discontinuity detection and thresholding-a stochastic approach", Journal of Complexity 9, 1 (1993), pp. 76--96.
Licia Lenarduzzi and Robert Schaback, "Kernel-based adaptive approximation of functions with discontinuities", Applied Mathematics and Computation 307, Supplement C (2017), pp. 113 - 123.
Lopes, Hélio and Oliveira, João Batista and de Figueiredo, Luiz Henrique, "Robust adaptive polygonal approximation of implicit curves", Computers & Graphics 26, 6 (2002), pp. 841--852.
Marroquin, Jose and Mitter, Sanjoy and Poggio, Tomaso, "Probabilistic solution of ill-posed problems in computational vision", Journal of the american statistical association 82, 397 (1987), pp. 76--89.
Nakos, Byron and Miropoulos, V, "Local length ratio as a measure of critical points detection for line simplification", in Fifth Workshop on Progress in Automated Map Generalization, Paris, France (, 2003).
Oliveria, M and Lu, P and Liu, X and Liu, C, "Universal high order subroutine with new shock detector for shock boundary layer interaction", In other words 10 (2009), pp. 1--2.
Pachón, Ricardo and Platte, Rodrigo B and Trefethen, Lloyd N, "Piecewise-smooth chebfuns", IMA journal of numerical analysis 30, 4 (2009), pp. 898--916.
Paiva, Afonso and de Carvalho Nascimento, Filipe and de Figueiredo, Luiz Henrique and Stolfi, Jorge, "Approximating implicit curves on triangulations with affine arithmetic", in Graphics, Patterns and Images (SIBGRAPI), 2012 25th SIBGRAPI Conference on (, 2012), pp. 94--101.
Parvez, Mohammad Tanvir and Mahmoud, Sabri A, "Polygonal approximation of digital planar curves through adaptive optimizations", Pattern Recognition Letters 31, 13 (2010), pp. 1997--2005.
Plaskota, Leszek and Wasilkowski, Grzegorz W, "Adaption allows efficient integration of functions with unknown singularities", Numerische Mathematik 102, 1 (2005), pp. 123--144.
Rossini, M., "2D-discontinuity detection from scattered data", Computing 61, 3 (1998), pp. 215--234.
Shen, Yiqing and Zha, Gecheng, "Improvement of the WENO scheme smoothness estimator", International Journal for Numerical Methods in Fluids 64, 6 (2010), pp. 653--675.
Shpitalni, Moshe and Koren, Yoram and Lo, CC, "Realtime curve interpolators", Computer-Aided Design 26, 11 (1994), pp. 832--838.
Siddiqi, Kaleem and Kimia, Benjamin B and Shu, Chi-Wang, "Geometric shock-capturing ENO schemes for subpixel interpolation, computation, and curve evolution", in Computer Vision, 1995. Proceedings., International Symposium on (, 1995), pp. 437--442.
Smith, C. and Blachman, N., The Mathematica graphics guidebook (Addison-Wesley, 1995).
Tupper, Jeffrey Allen, Graphing equations with generalized interval arithmetic. (University of Toronto, 1996).
Wilkinson, Leland, "Algorithms for choosing the domain and range when plotting a function", (1991), pp. 1--8.
Daniel C.H. Yang and Tom Kong, "Parametric interpolator versus linear interpolator for precision CNC machining", Computer-Aided Design 26, 3 (1994), pp. 225 - 234. Special Issue:NC machining and cutter-path generation
Yeh, S-S and Hsu, P-L, "The speed-controlled interpolator for machining parametric curves", Computer-Aided Design 31, 5 (1999), pp. 349--357.
Yeh, Syh-Shiuh and Hsu, Pau-Lo, "Adaptive-feedrate interpolation for parametric curves with a confined chord error", Computer-aided design 34, 3 (2002), pp. 229--237.
Zhou, Tony Chan and Zhou, HM, "Adaptive Eno-Wavelet Transforms For Discontinuous Functions", in CAM Report, No. 99-21, Dept. of Math., UCLA, Submit to SIAM Numer. Anal (, 1999).
de Carvalho Nascimento, Filipe and Paiva, Afonso and De Figueiredo, Luiz Henrique and Stolfi, Jorge, "Approximating implicit curves on plane and surface triangulations with affine arithmetic", Computers & Graphics 40 (2014), pp. 36--48.
de Figueiredo, Luiz Henrique, "Adaptive sampling of parametric curves", Graphics Gems V 5 (1995), pp. 173-178.
van Emden, M.H., "Value Constraints in the CLP Scheme", Constraints 2, 2 (1997), pp. 163--183.
Downloads
Published
Issue
Section
License
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
