This paper discusses scattered data interpolation using cubic trigonometric Bézier triangular patches with C1 continuity everywhere. We derive the C1 condition on each adjacent triangle. On each triangular patch, we employ convex combination method between three local schemes. The final interpolant with the rational corrected scheme is suitable for regular and irregular scattered data sets. We tested the proposed scheme with 36,65, and 100 data points for some well-known test functions. The scheme is also applied to interpolate the data for the electric potential. We compared the performance between our proposed method and existing scattered data interpolation schemes such as Powell–Sabin (PS) and Clough–Tocher (CT) by measuring the maximum error, root mean square error (RMSE) and coefficient of determination (R2). From the results obtained, our proposed method is competent with cubic Bézier, cubic Ball, PS and CT triangles splitting schemes to interpolate scattered data surface. This is very significant since PS and CT requires that each triangle be splitting into several micro triangles.
Cubic trigonometricBézier triangular patchesC1sufficient conditionscattered data interpolationIntroduction
This paper investigates scattered data interpolation using trigonometric Bézier triangular patch that has been proposed by Zhu et al. [1]. Scattered data interpolation is about the construction of a smooth surface for non-uniform set of data. It can be prescribed by a given a set of scattered data V={(xi,yi),i=1,…,n}∈R2 over a polygon domain and a corresponding set of real numbers {Zi}i=1n. Besides that, scattered data interpolation is very vital in many areas such as engineering fields, predicting rainfall and other data that needed to be measured or generated at irregular positions.
In a previous study, Saaban et al. [2] performed scattered data interpolation by using minimized sum of squares of principal curvatures. In additions, this scheme also uses geometric continuity which is G1 continuity between adjacent triangular patches to reconstruct surfaces. They applied the proposed scheme to some functions and to some real data such as soil erosion.
Butt et al. [3] proposed a scheme which exhibits the shape preserving properties by positivity, monotonicity and convexity 2D data by inserting more knots in the interval. The positivity of regular data arranged over a rectangular grid was discussed. Hussain et al. [4] proposed C1 continuity scattered data interpolation by preserving the positivity property. This scheme is modified by adding weights to the functions if the Bézier ordinates do not satisfy the derived positivity conditions.
Han [5] proposed cubic trigonometric polynomial curves with shape parameter where the order of continuity is dependent upon the knot vector (uniform or non-uniform) and the value of shape parameters. This scheme shows that the proposed scheme is closer to the control polygon than the corresponding B-spline curves. Besides that, the degree of the cubic trigonometric polynomial curves can be reduced to quadratic trigonometric polynomial curves which represent the ellipse.
Butt [6] preserved the shape of positive data by deriving sufficient conditions for the first partial derivatives and twist values by using a piecewise bi-cubic interpolant. Lamberti et al. [7] also proposed a method for the construction of C2 interpolating function. This scheme preserved the shape of curve via tension parameters. The calculation for approximation order and numerical examples is shown.
Floater [8,9] proposed another shape preserving property which is the convexity where [8] shows derivation of sufficient conditions convexity of tensor-product Bézier surfaces. The conditions focused on C1 tensor product B-spline surfaces. Unfortunately, the sufficient conditions in the form of inequalities which involved control points. Floater also defined convexity and rational convexity preservation of systems of functions. It is proven that the total positivity and rational convexity preservation are equivalent. Ali et al. [10] have constructed a new cubic Timmer triangular patch and applied it for scattered data interpolation. Based on the numerical results, their proposed scheme is better than the existing schemes in term of higher R2 and smaller SMSE and maximum error, however, their scheme took longer computational time to generate the results. Meanwhile Draman et al. [11] have constructed scattered data interpolation scheme by using rational quartic spline with three parameters. Karim et al. [12] have constructed new cubic Bézier-Like triangular patches with three parameters for scattered data interpolation. From numerical results, their proposed scheme is better than Radial basis functions (RBFs) scheme such as thin plate spline, gaussian etc.
The aim of this paper is to apply scattered data interpolation with trigonometric function which is cubic trigonometric Bézier. To our knowledge, this is the first study that applies trigonometric Bézier triangular for scattered data interpolation. We summarize the main advantages of the proposed scheme as follows:
The proposed scattered data interpolation uses cubic trigonometric Bézier with three parameters meanwhile Ali et al. [10], Draman et al. [11] and Karim et al. [12] have used different types of rational interpolants.
Our scheme only needs to triangulate the data one time. Meanwhile, Powell–Sabin (PS) and Clough–Tocher (CT) schemes needed to split the macro triangles into several micro triangles for each triangle. This will increase computation time to construct the final interpolating surface.
This paper is organized as follows: Section 2 discusses trigonometric Bézier triangular patches with three shape parameters. Section 3 states the properties of cubic trigonometric Bézier. Section 4 discusses the scattered data interpolation. Section 5 presents the numerical results including comparison with existing schemes. Conclusion and future work are given in Section 6.
Trigonometric Bézier Triangular Patch with Three Shape Parameters
Trigonometric Bézier triangular patches is constructed by Zhu et al. [1]. The trigonometric Bézier triangular patches are defined as follows:
Definition 1.Letα,β,γ∈[2,+∞), given control pointsPijk∈R3(i,j,k∈N,i+j+k=3), and a domain triangleD={(u,v,w)∣u+v+w=π/2,u≥0,v≥0,w≥0}in which(u,v,w)are barycentric coordinates of the points in D. We call
Properties of Cubic Trigonometric Bézier Triangular Patches
From the definition of the basis function of trigonometric triangular patches, the list below is important properties of the basis [1].
Affine invariance and convex hull. The basis function have the properties of partition of unity and nonnegativity, so its simply corresponding that cubic trigonometric Bézier has
Geometric property at the corner points. Direct computation such as
R(π/2,v,w)=P3,0,0R(u,π/2,w)=P0,3,0R(u,v,π/2)=P3,0,0 corner.
Corner points tangent plane.
Boundary property.
Shape adjustable property.
Scattered Data Interpolation
In this section, we will discuss the constrution of a smooth surface for given a set of scattered data V=(xi,yi,zi),i=1,2,…,N with corresponding a set of real numbers zi=F(xi,yi),i=1,2,…,N. We wish to reconstruct a surface which has C1 continuity everywhere. Throughout this section, we have adopted the main ideas from [11–15].
Local scheme
This scheme comprises of the convex combination of three local schemes P1,P2 and P3 and is defined as
where the local scheme P1,P2,P3 is derived and replaces the inner ordinates in the proposed method as show in Fig. 1.
For inner ordinates, we have employed the cubic precision that was proposed by Foley et al. [15] while Goodman et al. [14] methods are used to calculate the boundary ordinates for each triangle. The vertices V1,V2 and V3 with barycentric coordinates (1, 0, 0), (0, 1, 0) and (0, 0, 1) respectively meanwhile e1,e2 and e3 are direction vectors which are (0, −1, 1), (1, 0, 1) and (−1, 1, 0) respectively.
Directional derivatives
Let the directional derivatives along e3 and e2 at V1 be
Then, applying directional derivative into (3), yields
δRδe2(V1)=(2+α)(P300−P201)
δRδe3(V1)=(2+α)(P210−P300)
From (5) until (8), we get
P201=P300−1(2+α)[(x1−x3)Fx(V1)+(y1−y3)Fy(V1)]
P210=P300+1(2+α)[(x2−x1)Fx(V1)+(y2−y1)Fy(V1)]
Other directional derivatives along e1,e3 at V2 and e1,e2 at V3 are given as follows:
P120=1(2+β)[(x2−x1)Fx(V2)+(y2−y1)Fy(V2)]−P030
P021=1(2+β)[(x3−x2)Fx(V2)+(y2−y1)Fy(V2)]+P030
P012=−1(2+γ)[(x3−x2)Fx(V3)+(y3−y2)Fy(V3)]+P003
P102=1(2+γ)[(x1−x3)Fx(V3)+(y1−y2)Fy(V3)]+P003
Now, we need to calculate the inner ordinates for each triangle. In order to calculate inner ordinates b111k,k=1,2,3, we have adopted Foley et al. [15] to achieve cubic precision. Since the proposed scheme is cubic degree, then cubic precision will produce surface up to degree three [15].
The remaining inner ordinates are obtained by symmetry [11].
Now, we establish the algorithm that can be used for surface reconstruction using the proposed scheme.
Reconstruction of surface for scattered data interpolation
1) Input data points
2) Triangulate the data sites using Delaunay triangulation method.
3) Derivation C1 continuity for scattered data interpolation.
4) Generate the surfaces using cubic trigonometric triangular patches
5) Compute the error–maximum error, RMSE and R2
6) Compare the performances with two existing method–cubic Ball and cubic Bézier.
7) Repeat 1 until 6 using different test function.
Results and Discussion
In this subsection, we discuss the performance of our proposed method by measuring 36,65 and 100 data points. Besides that, we also compare the maximum error, root mean square error (RMSE) and coefficient determination (R2). All numerical simulations are done by using MATLAB version 2019 installed on Intel® CORE™ i5-2410M CPU@2.30 GHz. Four tested functions are chosen by sampling the points to 36, 65 and 100.
Delaunay triangulations. (a) Delaunay triangulation: 36 data points. (b) Delaunay triangulation: 65 data points. (c) Delaunay triangulation: 100 data points
Gentle function
F(x,y)=exp(−(8116)((x−0.5)2+(y−0.5)2))3
Fig. 2 shows Delaunay Triangulation of 36, 65 and 100 data points with domain of [0,1]×[0,1]. Fig. 3 until Fig. 4 shows surface interpolation for 36 and 65 data points.
Surface interpolation for 36 data points. (a) H(x,y) (b) P(x,y) (c) R(x,y) (d) F(x,y)
Surface interpolation for 65 data points. (a) H(x,y) (b) P(x,y) (c) R(x,y) (d) F(x,y)
Tabs. 1–3 shows numerical result for error measurement for 36, 65 and 100 data points.
Tabs. 1–3 show numerical results for 36, 65 and 100 data points. We can see in Tabs. 1–3, the proposed scheme is on par with two established schemes i.e., Goodman et al. [14] and Karim et al. [16].
Now, we compare the performance between the proposed scattered data interpolation scheme against two well-known scattered data interpolation methods i.e., C1 Cubic Clough–Tocher (CT) and C1 quadratic Powell–Sabin (PS) schemes (Schumaker [17–18]). Tabs. 4 and 5 summarize all results. Overall, the proposed scheme is also on par with PS and CT schemes. However, in term of RMSE, both PS and CT are better than the proposed scheme. This is understandable since, both PS and CT have refining the macro triangles into many macro triangles. This will reduce the interpolation error but at a cost, CPU time will be increased. All schemes are equivalent good in term of R2. Figs. 5, 6 show the PS and CT splitting schemes. PS schemes tend to produce not smooth surfaces around the corner compared with the proposed scattered data interpolation scheme.
(Two Stage Method [17]) Reconstruction of surface for scattered data interpolation using C1 quadratic Powell–Sabin interpolant and C1 cubic Clough–Tocher interpolant
Input data points
Data are triangulated using Delaunay triangulation method.
Estimate the gradients at the vertices of the triangulation from the scattered data for PS and CT Schemes.
Compute the interpolants and generate the surfaces
Calculate the error–maximum error, RMSE and R2
Repeat 1 until 6 using different test function.
Error measurement for 36 data points
Test function
Method
Shape parameter
Max error
RMSE
R2
α
β
γ
H(x,y)
Cubic ball
0.1122
0.0264
0.9915
Cubic Bézier
0.1051
0.0263
0.9916
Cubic trigonometric Bézier
4
3
4
0.0975
0.0275
0.9908
5
3
4.5
0.0930
0.0278
0.9906
6
5
4.5
0.0984
0.0288
0.9899
P(x,y)
Cubic ball
0.0265
0.0060
0.9936
Cubic Bézier
0.0262
0.0061
0.9934
Cubic trigonometric Bézier
3
3
4
0.0262
0.0062
0.9944
3
4
5
0.0263
0.0068
0.9928
2
4
5
0.0262
0.0068
0.9930
R(x,y)
Cubic ball
0.0491
0.0130
0.9829
Cubic Bézier
0.0483
0.0129
0.9832
Cubic trigonometric Bézier
2
2.5
4
0.0531
0.0132
0.9825
3
2
4
0.0526
0.0131
0.9826
3
2
5
0.0535
0.0131
0.9837
F(x,y)
Cubic ball
0.0127
0.0041
0.9973
Cubic Bézier
0.0103
0.0037
0.9978
Cubic trigonometric Bézier
2
2
2
0.0119
0.0042
0.9973
3
2
2
0.0123
0.0040
0.9982
2
2
3
0.0132
0.0042
0.9972
Our final example in this study is to apply the proposed scheme to visualize real scattered data obtained from Ali et al. [19] and Gilat [20]. The electric potential V around a charged particle is given by:
V=14πε0qr
where ε0=8.8541878×10−12CNm2 is the permittivity constant, r is the distance from the particle in meters and q is the magnitude of the charge in Coulombs. The electric potential at a point due to two particles is given as
V=14πεo(q1r1+q2r2)
where q1,q2,r1 and r2 are the charges of the particles and the distance form the points to the corresponding particles, respectively. Two particles with a charge is q1=2×10−10C and q1=3×10−10C. Noted that r1=(x+0.25)2+y2 and r2=(x−0.25)2+y2.
Fig. 7 shows the Delaunay triangulation for electric potential, and Fig. 8 shows surface interpolant using the proposed scheme.
Error measurement for 65 data points
Test function
Method
Shape parameter
Max error
RMSE
R2
α
β
γ
H(x,y)
Cubic ball
0.0611
0.0154
0.9971
Cubic Bézier
0.0643
0.0152
0.9972
Cubic trigonometric Bézier
2
4.5
4
0.0625
0.0153
0.9977
2
4
5
0.0627
0.0157
0.9970
3
6
5
0.0631
0.0162
0.9968
P(x,y)
Cubic ball
0.0130
0.0031
0.9983
Cubic Bézier
0.0153
0.0033
0.9981
Cubic trigonometric Bézier
4
3
4
0.0178
0.0039
0.9973
3
2
3
0.0164
0.0037
0.9987
3
3
3
0.0181
0.0037
0.9976
R(x,y)
Cubic ball
0.0309
0.0049
0.9976
Cubic Bézier
0.0312
0.0049
0.9975
Cubic trigonometric Bézier
2
2
2
0.0327
0.0054
0.9971
2
2
3
0.0318
0.0050
0.9978
3
2
2
0.0327
0.0054
0.9970
F(x,y)
Cubic ball
0.0072
0.0020
0.9994
Cubic Bézier
0.0060
0.0018
0.9995
Cubic trigonometric Bézier
2
2
2
0.0075
0.0020
0.9995
2
3
3
0.0087
0.0023
0.9991
2
2
3
0.0082
0.0023
0.9992
Error measurement for 100 data points
Testfunction
Method
Shape parameter
Maxerror
RMSE
R2
α
β
γ
H(x,y)
Cubic ball
0.0336
0.0067
0.9995
Cubic Bézier
0.0342
0.0070
0.9994
Cubic trigonometric Bézier
3
3
3
0.0362
0.0082
0.9992
2
3
2
0.0352
0.0080
0.9992
3
3
2
0.0351
0.0080
0.9995
P(x,y)
Cubic ball
0.0057
0.0013
0.9997
Cubic Bézier
0.0046
0.0011
0.9998
Cubic trigonometric Bézier
4
3
3
0.0057
0.0015
0.9996
4
3.5
4
0.0067
0.0012
0.9997
5
3
3
0.0064
0.0017
0.9995
R(x,y)
Cubic ball
0.0226
0.0035
0.9988
Cubic Bézier
0.0238
0.0035
0.9988
Cubic trigonometric Bézier
2
2
2
0.0280
0.0038
0.9985
3
2
2
0.0275
0.0038
0.9985
4
3
2
0.0271
0.0039
0.9985
F(x,y)
Cubic ball
0.0054
0.0010
0.9998
Cubic Bézier
0.0034
0.0007
0.9999
Cubic trigonometric Bézier
2
2
2
0.0039
0.0011
0.9998
2
2
3
0.0038
0.0011
0.9998
2
3
2
0.0041
0.0012
0.9998
Errors using PS and CT schemes
Num. of data points
Function
Maximum error (MaxE)
RMSE
PS interpolant
CT interpolant
PS interpolant
CT interpolant
100
1
3.40e−02
3.41e−02
7.12e−03
6.48e−03
2
3.89e−03
3.62e−03
6.55e−04
6.15e−04
3
2.02e−02
2.08e−02
3.84e−03
3.75e−03
4
7.63e−03
6.66e−03
1.51e−03
1.38e−03
65
1
9.43e−02
1.01e−01
1.96e−02
1.83e−02
2
1.91e−02
1.82e−02
3.27e−03
3.23e−03
3
2.97e−02
2.89e−02
6.44e−03
5.90e−03
4
1.37e−02
1.22e−02
3.04e−03
2.82e−03
36
1
1.47e−01
1.44e−01
4.01e−02
3.90e−02
2
3.76e−02
3.08e−02
7.74e−03
7.87e−03
3
6.45e−02
5.24e−02
1.49e−02
1.47e−02
4
6.10e−02
5.34e−02
1.26e−02
1.20e−02
R2 values for PS and CT
Num. of data points
Function
PS Interpolant
CT Interpolant
100
1
0.9994
0.9995
2
0.9999
1.0000
3
0.9985
0.9986
4
0.9997
0.9997
65
1
0.9953
0.9960
2
0.9987
0.9987
3
0.9958
0.9965
4
0.9987
0.9989
36
1
0.9805
0.9822
2
0.9927
0.9930
3
0.9775
0.9782
4
0.9773
0.9797
Powell–Sabin split
Clough–Tocher split
Delaunay triangulation
Surface interpolation
Conclusion
This paper discusses scattered data interpolation by using cubic trigonometric Bézier triangular patches initiated by Zhu et al. [1]. Sufficient condition for C1 continuity on each adjacent triangle is developed by using cubic precision method. An efficient algorithm is presented. We test the proposed scheme by using four well-known tested functions. We compare the performance against some established schemes such as Goodman et al. [14], Karim et al. [16] and Powell–Sabin (PS) and Clough–Tocher (CT) split schemes. From error analysis, we found that the proposed scheme is on par and for all data sets, we achieve higher R2 values. Finally, we test the proposed scheme to interpolate real scattered data set. For future research, we can apply the proposed scheme for shape preserving interpolation such as positivity and convexity. The proposed scheme also can be applied for constrained surface modeling above, below or between two planes as discussed in Karim et al. [21].
Funding Statement: This research was fully supported by Universiti Teknologi PETRONAS (UTP) and Ministry of Education, Malaysia through research grant FRGS/ 1/2018/STG06/UTP/03/1/015 MA0-020 (New rational quartic spline interpolation for image refinement) and UTP through a research grant YUTP: 0153AA-H24 (Spline Triangulation for Spatial Interpolation of Geophysical Data).
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
ReferencesY.Zhu and X.Han, “New trigonometric basis possessing exponential shape parameters,” , vol. 33, no. 6, pp. 642–684, 2015.A.Saaban, A. R. M.Piah, A. A.Majid and L. H. T.Chang, “G1scattered data interpolation with minimized sum of squares of principal curvatures,” in Int. Conf. on Computer Graphics, Imaging and Visualization, Beijing, China, pp. 385–390, 2005. S.Butt and K. W.Brodlie, “Preserving positivity using piecewise cubic interpolation,” , vol. 17, no. 1, pp. 55–64, 1993.M. Z.Hussain and M.Hussain, “C1 positivity preserving scattered data interpolation using rational Bernstein–Bézier triangular patch,” , vol. 35, no. 1–2, pp. 281–293, 2011.X.Han, “Cubic trigonometric polynomial curves with a shape parameter,” , vol. 21, no. 6, pp. 535–548, 2004.S.Butt, “Shape preserving curves and surfaces for Computer Graphics,” Ph.D. Thesis. School of Computer Studies, The University of Leeds, UK, 1991. P.Lamberti and C.Manni, “Shape-preserving C2 functional interpolation via parametric cubics,” , vol. 28, no. 1–4, pp. 229–254, 2001.M. S.Floater, “A weak condition for the convexity of tensor-product Bézier and B-spline surfaces,” , vol. 2, no. 1, pp. 67–80, 1994.M. S.Floater, “Total positivity and convexity preservation,” , vol. 96, no. 1, pp. 46–66, 1999.F. A. M.Ali, S. A. A.Karim, A.Saaban, M. K.Hasan, A.Ghaffaret al., “Construction of cubic Timmer triangular patches and its application in scattered data interpolation,” , vol. 8, no. 2, pp. 159, 2020.C. N. N.Draman, S. A. A.Karim and I.Hashim, “Scattered data interpolation using rational quartic triangular patches with three parameters,” , vol. 8, pp. 44239–44262, 2020.S. A. A.Karim, A.Saaban, V.Skala, A.Ghaffar, K. S.Nisaret al., “Construction of new cubic Bézier-like triangular patches with application in scattered data interpolation,” , vol. 2020, Article no. 151, 2020.S. A. A.Karim, A.Saaban, M. K.Hasan, J.Sulaiman and I.Hashim, “Interpolation using cubic Bèzier triangular patches,” , vol. 8, no. 4–2, pp. 1746–1752, 2018.T. N. T.Goodman and H. B. A.Said, “C1 triangular interpolant suitable for scattered data interpolation,” , vol. 7, no. 6, pp. 479–485, 1991.T. A.Foley and K.Opitz, “Hybrid cubic Bézier triangle patches,” in . Cambridge, Massachusetts, United States: Academic Press, pp. 275–286, 1992.S. A. B. A.Karim and A.Saaban, “Visualization terrain data using cubic ball triangular patches,” in MATEC Web of Conferences, vol. 225, pp. 06023, 2018. L. L.Schumaker, . Philadelphia, USA: SIAM, 2015.M. J.Lai and L. L.Schumaker, . Cambridge: Cambridge University Press, 2007.F. A. M.Ali, S. A. A.Karim, S. C.Dass, V.Skala, M. K.Hasanet al., “Efficient visualization of scattered energy distribution data by using cubic trimmer triangular patches,” in . Singapore: Springer, pp. 145–180, 2020.A.Gilat, , 4th ed., USA: John Wiley & Sons, 2013.S. A. A.Karim, A.Saaban and V.Skala, “Range-restricted surface interpolation using rational bi-cubic spline functions with 12 parameters,” , vol. 7, pp. 104992– 105007, 2019.