Efficient plotting the functions with discontinuities based on combined sampling

Authors

  • Tomáš Bayer Department of Applied Geoinformatics and Cartography, Charles University in Prague

DOI:

https://doi.org/10.14311/gi.17.2.2

Keywords:

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

2018-08-23

Issue

Section

Articles