Next Article in Journal
MRSO: Balancing Exploration and Exploitation through Modified Rat Swarm Optimization for Global Optimization
Next Article in Special Issue
Analytical Solution for the Problem of Point Location in Arbitrary Planar Domains
Previous Article in Journal
Connected and Autonomous Vehicle Scheduling Problems: Some Models and Algorithms
Previous Article in Special Issue
Meshfree Variational-Physics-Informed Neural Networks (MF-VPINN): An Adaptive Training Strategy
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Cubic q-Bézier Triangular Patch for Scattered Data Interpolation and Its Algorithm

by
Owen Tamin
1 and
Samsul Ariffin Abdul Karim
2,*
1
Faculty of Science and Natural Resources, Universiti Malaysia Sabah, Jalan UMS, Kota Kinabalu 88400, Malaysia
2
School of Quantitative Sciences, UUM College of Arts and Sciences, Universiti Utara Malaysia, Sintok 06010, Malaysia
*
Author to whom correspondence should be addressed.
Algorithms 2024, 17(9), 422; https://doi.org/10.3390/a17090422
Submission received: 10 July 2024 / Revised: 5 August 2024 / Accepted: 7 August 2024 / Published: 23 September 2024
(This article belongs to the Special Issue Numerical Optimization and Algorithms: 2nd Edition)

Abstract

:
This paper presents an approach to scattered data interpolation using q-Bézier triangular patches via an efficient algorithm. While existing studies have formed q-Bézier triangular patches through convex combination, their application to scattered data interpolation has not been previously explored. Therefore, this study aims to extend the use of q-Bézier triangular patches to scattered data interpolation by achieving C 1 continuity throughout the data points. We test the proposed scheme using both established data points and real-life engineering problems. We compared the performance of the proposed interpolation scheme with a well-known existing scheme by varying the q parameter. The comparison was based on visualization and error analysis. Numerical and graphical results were generated using MATLAB. The findings indicate that the proposed scheme outperforms the existing scheme, demonstrating a higher coefficient of determination ( R 2 ), smaller root mean square error (RMSE), and faster central processing unit (CPU) time. These results highlight the potential of the proposed q-Bézier triangular patches scheme for more accurate and reliable scattered data interpolation via the proposed algorithm.

1. Introduction

Scattered data interpolation is crucial in computational science, providing a method to estimate values at arbitrary points within datasets characterized by irregularly distributed data points. Unlike structured datasets, which are arranged on grids or meshes, scattered data often arise from real-world observations or simulations where data points are irregularly positioned in multidimensional space. Interpolating these data involves constructing a continuous function that approximates the dataset’s underlying behavior, allowing for the inference of values at unobserved locations within the domain [1].
There are two primary approaches to scattered data interpolation: triangulation-based methods and meshless techniques. Triangulation-based approaches involve creating a mesh from the scattered data points. However, not all interpolation methods require such a mesh. For example, some variants of the Shepard method do not require creating a mesh; instead, barycentric coordinates are used to obtain the explicit expression of the polynomial interpolant [2]. Common basis functions used in these methods include Bézier, B-spline, and radial basis functions (RBFs). To mitigate noise in the scattered data, least squares approximation is often employed.
Liu [3] developed a local multi-level scattered data interpolation method by introducing layered datasets and adjusting compactly supported radial basis functions. Borne and Wende [4,5] explored meshless methods using specific RBFs for interpolation, employing domain decomposition methods to generate symmetric saddle point systems. Skala et al. [5] presented an innovative variant of the normalized RBFs known as the Squared Normalized RBFs (SN-RBFs), specifically designed for spatio-temporal data. This new formulation involves the normalization of the rows of the RBF matrix, a process that significantly improves the conditioning of the RBF matrix. As a result, the SN-RBF method enhances the robustness and accuracy of RBF interpolation, making it more suitable for a wide range of applications.
Joldes et al. [6] enhanced the moving least squares (MLS) technique by incorporating polynomial bases to improve scattered data interpolation. Brodlie et al. [7] examined constrained surface interpolation using the Shepard interpolant, addressing the problem with optimization techniques. Lai and Meile [8] reviewed the use of non-negative bivariate triangular splines for maintaining the shape of scattered data. Schumaker and Speleers [9] investigated preserving non-negativity using macro-element spline spaces with Clough–Tocher macro-elements.
Karim et al. [10,11] explored spatial interpolation for rainfall data and terrain data using cubic Bézier and cubic Ball triangular patches. These studies demonstrated that the scattered data interpolation approach by Said and Rahmat [12] does not exhibit C 1 continuity, prompting the establishment of new criteria for C 1 continuity. Their method yielded a differentiable surface with a seamless appearance.
Feng and Zhang [13] introduced segmented bivariate Hermite interpolation using triangulation for precise surface reconstruction from extensive scattered datasets. Sun et al. [14] developed a bivariate rational interpolation on a triangular domain but noted increased computation time with rational splines. Bozzini et al. [15] suggested using polyharmonic splines to estimate noisy scattered data.
Goodman and Said [16] developed a C 1 triangular interpolant using a convex combination scheme, differing from Foley and Opitz’s C 1 cubic triangular convex combination technique [17]. Said and Rahmat’s method using cubic Ball triangular patches yielded results equivalent to cubic Bézier triangular patches with reduced computation [12]. Karim and Saaban’s study confirmed the non-continuous differentiability of Said and Rahmat’s function [18].
Hussain et al. [19] introduced rational cubic Bézier triangular methods for positivity-preserving interpolation, asserting continuous differentiability. Chan and Ong [20] examined range-restricted interpolation using cubic Bézier triangles with partial derivatives calculated using Goodman’s approach.
Research has also explored quartic Bézier triangular patches for scattered data interpolation. Saaban et al. [21] and Piah et al. [22] developed C 1 (or G 1 ) methods using quartic Bézier triangles, optimizing inner Bézier points to maintain range and positivity. Hussain et al. [23] expanded this to convexity-preserving interpolation with rational quartic Bézier triangles, addressing optimization challenges for C 1 continuity. Comprehensive surveys on scattered data interpolation are available in sources like [1,24,25,26,27].
Among the various generalizations of Bézier curves, q-Bézier curves introduce greater versatility to the classical Bézier curves through the use of the parameter q. This parameter allows for more flexible and dynamic curve modeling, accommodating a wider range of shapes and applications [28,29,30,31,32,33]. Lewanowicz et al. [30] expanded the q-Bernstein basis of univariate polynomials to a triangular domain, providing a novel framework for handling scattered data.
However, the evaluation algorithm they proposed does not generally involve linear convex combinations, which limits its practical utility in some applications [30]. Foley [17] addressed this limitation by extending the evaluation algorithm to incorporate convex combinations, enhancing the algorithm’s applicability and robustness. Inspired by these advancements, we aim to further explore and apply these extended q-Bézier curve techniques to the challenging problem of scattered data interpolation, leveraging their flexibility to achieve more accurate and efficient interpolation results.

2. q-Bézier Triangular Patch

Definition 1.
Given a non-negative integer n and three indices i , j , k 0 such that i + j + k = n , the triangular q-Bernstein from [34] is defined as
B i , j , k n ( u , v ) = n k i + j i u i v j s = 0 k 1 1 q s u q s v , i , j , k 0 , i + j + k = n where q [ 0 , 1 ]
In order to construct a q-Bézier triangular patch for scattered data interpolation, the existing triangular Bernstein polynomials B i , j , k n ( u , v ) are extended to B i , j , k n ( u , v , w ) , which is defined in Proposition 1.
Proposition 1.
The triangular q-Bernstein polynomials from Equation (1) are extended to B i , j , k n ( u , v , w ) , which are given by
B i , j , k n ( u , v , w ) = n k i + j i u i v j s = 0 k 1 1 q s + q s w , i , j , k 0 , i + j + k = n where q [ 0 , 1 ]
Proof. 
Given a non-negative integer n and three indices i , j , k 0 such that i + j + k = n ,
B i , j , k n ( u , v ) = n k i + j i u i v j s = 0 k 1 ( 1 q s u q s v )
= n k i + j i u i v j s = 0 k 1 ( 1 q s u q s v ) + q s q s
By factorizing Equation (4), we have
B i , j , k n ( u , v ) = n k i + j i u i v j s = 0 k 1 ( 1 q s + q s ( 1 u v ) )
Taking into account that w = 1 u v , we can therefore rewrite B i , j , k n ( u , v ) as
B i , j , k n ( u , v , w ) = n k i + j i u i v j s = 0 k 1 ( 1 q s + q s w )
   □
Definition 2.
Let D : = { ( u , v , w ) u + v + w = 1 , u > 0 , v > 0 , w > 0 } . The following ten functions are a cubic q-Bézier basis function over the triangular domain D shown in Figure 1.
Let α = 1 + q + q 2 , β = 1 q + q w , and γ = 1 q 2 + q 2 w .
B 3 , 0 , 0 3 ( u , v , w ) = u 3 , B 0 , 3 , 0 3 ( u , v , w ) = v 3 , B 0 , 0 , 3 3 ( u , v , w ) = β γ w , B 2 , 1 , 0 3 ( u , v , w ) = 3 u 2 v , B 2 , 0 , 1 3 ( u , v , w ) = α u 2 w , B 1 , 2 , 0 3 ( u , v , w ) = 3 u v 2 , B 0 , 2 , 1 3 ( u , v , w ) = α v 2 w , B 1 , 0 , 2 3 ( u , v , w ) = α β u w , B 0 , 1 , 2 3 ( u , v , w ) = α β v w , B 1 , 1 , 1 3 ( u , v , w ) = 1 i + j + k = 3 , i , j , k 1 B i , j , k 3 ( u , v , w )
Theorem 1.
The basis function defined over a triangular domain has the following properties:
(a) 
Partition of unity: i + j + k = 3 B i , j , k 3 ( u , v , w ) = 1 .
(b) 
Non-negativity: B i , j , k 3 ( u , v , w ) 0 , i , j , k N , i + j + k = 3 .
(c) 
Property at the corner points: for i , j , k N , i + j + k = 3 , we have
B i , j , k 3 ( 1 , 0 , 0 ) = 1 , i = 3 , 0 , i 3 , B i , j , k 3 ( 0 , 1 , 0 ) = 1 , j = 3 , 0 , j 3 , B i , j , k 3 ( 0 , 0 , 1 ) = 1 , k = 3 , 0 , k 3 ,
(d) 
When q = 1 , the cubic q-Bézier triangular is reduced to the standard cubic Bézier.
Definition 3.
A cubic q-Bézier triangular patch is defined as
R ( u , v , w ) = i + j + k = 3 B i , j , k 3 ( u , v , w ) b i , j , k
where B i , j , k 3 ( u , v , w ) is defined by Equation (6) for all q [ 0 , 1 ] .
Figure 2 presents a comparison of the interpolation surfaces for one cubic q-Bézier patch, with varying values of q where the values are 0.25, 0.5, 0.75, and 1.0. As the value of q increases, the surface gradually shifts closer to the control polygon, reflecting the influence of q on the overall interpolation. When q = 1.0 , the surface conforms more closely to the shape of the control polygon, while for smaller q values (e.g., 0.25), the surface tends to be smoother and less influenced by the control points. This demonstrates the flexibility of the q-Bézier interpolation scheme in controlling the tension and shape of the interpolating surface.

3. Scattered Data Interpolation Using q-Bézier Triangular Patch

In this section, we will extend the cubic q-Bézier triangular patch discussed in Section 2 to the application of scattered data interpolation. Figure 3 shows the arrangement of control points on one patch of a cubic q-Bézier triangular patch.

3.1. Derivative Estimation

The partial derivatives f x V i and f y V i at the vertices x i , y i , i = 1 , 2 , 3 , , n of th triangle are estimated using the method proposed in [16]. These partial derivatives are used to find derivatives in the direction of ε , which is an edge of the triangle that is shown in Figure 4.
The derivative along the side ε i is given by
f ε i = x i 1 x i + 1 f x + y i 1 y i + 1 f y

3.2. Boundary Bézier Ordinates

Boundary Bézier ordinates are calculated using the C 1 continuity condition at the vertices of the triangle. At each vertex there are two directional derivatives in the direction of both the edges incident at the vertex.
The q-Bézier triangular patch is C 1 at the vertices of the triangle if the boundary Bézier ordinates are
b 3 , 0 , 0 = F ( V 1 ) b 2 , 0 , 1 = q 3 1 b 1 , 0 , 2 + q 3 + q 2 + q 1 F ( V 3 ) + 3 F ( V 1 ) q 2 + q + 1 1 q 2 + q + 1 F ( V 1 ) e 2 b 2 , 1 , 0 = F ( V 1 ) + 1 3 F ( V 1 ) e 3 b 0 , 3 , 0 = F ( V 2 ) b 0 , 2 , 1 = q 3 1 b 0 , 1 , 2 + q 3 + q 2 + q 1 F ( V 3 ) + 3 F ( V 2 ) q 2 + q + 1 + 1 q 2 + q + 1 F ( V 2 ) e 1 b 1 , 2 , 0 = F ( V 2 ) 1 3 F ( V 2 ) e 3 b 0 , 0 , 3 = F ( V 3 ) b 0 , 1 , 2 = F ( V 3 ) 1 q 2 + q + 1 F ( V 3 ) e 1 b 1 , 0 , 2 = F ( V 3 ) + 1 q 2 + q + 1 F ( V 3 ) e 2

3.3. Inner Bézier Ordinates

The remaining b 1 , 1 , 1 i , i = 1 , 2 , 3 is obtained using the cubic precision method of Foley and Opitz [17], as shown in Figure 5. For complete derivation, the reader can refer to [17].
Let ( r , s , t ) be the barycentric coordinates of P 1 ¯ with respect to the triangle P 1 P 2 P 3 . In order to achieve C 1 continuity along all edges, the following equations must be satisfied:
d 0 , 1 , 2 = r 2 b 0 , 3 , 0 + 2 r s b 1 , 2 , 0 + 2 r t b 0 , 2 , 1 + s 2 b 2 , 1 , 0 + 2 s t b 1 , 1 , 1 1 + t 2 b 0 , 1 , 2
d 1 , 0 , 2 = r 2 b 1 , 2 , 0 + 2 r s b 2 , 1 , 0 + 2 s t b 2 , 0 , 1 + s 2 b 3 , 0 , 0 + 2 r t b 1 , 1 , 1 1 + t 2 b 1 , 0 , 2
In reversing the triangles where ( u , v , w ) are the barycentric coordinates of P 1 with respect to the triangle P 1 ¯ P 2 ¯ P 3 ¯ , the following equation is obtained:
b 0 , 1 , 2 = u 2 d 0 , 3 , 0 + 2 u v d 1 , 2 , 0 + 2 u w d 0 , 2 , 1 + v 2 d 2 , 1 , 0 + 2 v w d 1 , 1 , 1 1 + w 2 d 0 , 1 , 2
b 1 , 0 , 2 = u 2 d 1 , 2 , 0 + 2 u v d 2 , 1 , 0 + 2 v w d 2 , 0 , 1 + v 2 d 3 , 0 , 0 + 2 u w d 1 , 1 , 1 1 + w 2 d 1 , 0 , 2
The value of d 111 1 is obtained by adding Equations (10) and (11) together. Thus, we obtain
d 1 , 1 , 1 1 = 1 2 w ( u + v ) u 2 d 0 , 3 , 0 u 2 d 1 , 2 , 0 2 u v d 1 , 2 , 0 2 u v d 2 , 1 , 0 2 u w d 0 , 2 , 1 v 2 d 2 , 1 , 0 v 2 d 3 , 0 , 0 2 v w d 2 , 0 , 1 w 2 d 0 , 1 , 2 w 2 d 1 , 0 , 2 )
Similarly, by adding Equations (8) and (9), we obtain
b 1 , 1 , 1 1 = 1 2 t ( r + s ) ( r 2 b 0 , 3 , 0 r 2 b 1 , 2 , 0 2 r s b 1 , 2 , 0 2 r s b 2 , 1 , 0 2 r t b 0 , 2 , 1 s 2 b 2 , 1 , 0 s 2 b 3 , 0 , 0 2 s t b 2 , 0 , 1 t 2 b 0 , 1 , 2 t 2 b 1 , 0 , 2 )
The final scattered data interpolation scheme using the cubic q-Bézier triangular patch can be expressed as follows:
R ( u , v , w ) = i + j + k = 3 B i , j , k 3 ( u , v , w ) b i , j , k + 6 u v w ( τ 1 b 1 , 1 , 1 1 + τ 2 b 1 , 1 , 1 2 + τ 3 b 1 , 1 , 1 3 )
where
τ 1 = v w u v + v w + w u , τ 2 = w u u v + v w + w u , τ 3 = u v u v + v w + w u
The computational complexity of our proposed scattered data interpolation scheme for a single triangular patch involves 38 multiplications, 13 additions, and 1 division. This complexity is comparable to that of classical methods, such as those in [16], which require a total of 52 operations.
The overall algorithm used in this study with descriptions is below.

4. Results and Discussion

In this study, we implemented the proposed scheme using MATLAB 2023a to conduct the experiment. The MATLAB coding was developed based on Algorithm 1, and the processor used was 1.6 GHz Dual-Core Intel Core i5 (Intel, Santa Clara, CA, USA). The error norms were computed using a 33 × 33 uniform rectangular grid of evaluation points in the unit square. The error measurements used were the (a) coefficient of determination, R 2 ; (b) root mean square error (RMSE); and (c) central processing unit (CPU) time.
Algorithm 1 q-Bézier Triangular Patches for Scattered Data Interpolation
  1:
Input: Scattered data points { ( x i , y i , z i ) } i = 1 n
  2:
Output: Interpolated surface, R 2 , RMSE, and CPU time
  3:
 
  4:
Step 1: Estimate Partial Derivatives
  5:
 
  • Compute the partial derivatives f ε 1 , f ε 2 and f ε 3 at each data point using Equation (8).
  • MATLAB functions: diff, gradient
  6:
 
  7:
Step 2: Perform Delaunay Triangulation
  8:
 
  • Use a Delaunay triangulation algorithm to create a mesh from the scattered data points.
  • MATLAB functions: delaunay, triplot
  9:
 
10:
Step 3: Calculate Boundary Control Points
11:
 
  • Determine the boundary control points for each triangle in the triangulated mesh.
  • MATLAB functions: convhull, boundary
12:
 
13:
Step 4: Calculate Inner Control Points
14:
 
  • For each triangle, compute the inner control points for the local scheme b 1 , 1 , 1 i , i = 1 , 2 , 3 .
  • MATLAB function: custom implementation based on Foley and Opitz [17]
15:
 
16:
Step 5: Construct the Interpolated Surface
17:
 
  • Use the convex combination method to combine the three local schemes defined by Equation (15).
  • MATLAB functions: sum, minus, divide
18:
 
19:
Step 6: Evaluate Performance Metrics
20:
 
  • Calculate R 2 , RMSE, and CPU time.
  • MATLAB functions: sum, abs, sqrt, mean, tic, toc
The error bound for the proposed scattered data interpolation scheme was adopted from [35]. Let the proposed scheme be denoted as p and Φ be the convex hull of points x i , y i , i = 1 , 2 , , N . Let Δ be a triangulation of Φ .
Theorem 2.
For every f ϵ C 4 ( Φ ) . Its C 1  q-Bézier interpolant p satisfies
f p K | Δ | 4 | f | 4
where the constant K depends on the smallest angle in Δ. Furthermore, | Δ | is the size of the triangulation, i.e., the Δ largest length of edges of Δ.
The proposed scheme was tested using three well-known test functions F 1 ( x , y ) , F 2 ( x , y ) , and F 3 ( x , y ) for surface interpolation (Karim et al. [36]):
  • Sphere function:
    F 1 ( x , y ) = 0.75 e ( 9 x 2 ) 2 + ( 9 y 2 ) 2 4 + 0.75 e ( 9 x + 1 ) 2 49 ( 9 y + 1 ) 2 10 + 0.5 e ( 9 x 7 ) 2 + ( 9 y 3 ) 2 4 0.2 e ( 9 x 4 ) 2 ( 9 y 7 ) 2
  • Cliff function:
    F 2 ( x , y ) = ( 1.25 + cos ( 5.4 y ) ) 6 + 6 ( 3 x 1 ) 2
  • Gentle function:
    F 3 ( x , y ) = 1 3 e 81 16 ( ( x 0.5 ) 2 ( y 0.5 ) 2 )
Figure 6 shows the Delaunay triangulation of 36, 65, and 100 data points on the rectangular domain of [0, 1] × [0, 1] with uniform distribution. The Delaunay triangulation presented in Figure 6 is constrained, ensuring that specific segments are included as edges. This approach is particularly useful for maintaining specific boundary conditions and incorporating predefined features into the mesh structure [37].
Figure 7, Figure 8, Figure 9, Figure 10, Figure 11, Figure 12, Figure 13 and Figure 14 display the surface interpolation and corresponding contour plots with various q parameters and data points derived from the F 1 ( x , y ) function. The visual inspection reveals that surface interpolation and its contour plots exhibit noticeable smoothness with 100 data points compared to 36 and 65 data points. Despite the change in the q parameter, differentiating the resulting surfaces proves visually challenging.
Similarly, Figure 15, Figure 16, Figure 17, Figure 18, Figure 19, Figure 20, Figure 21 and Figure 22 illustrate surface interpolation and contour plots based on the F 2 ( x , y ) function under a varying q parameter and data points. Consistent with the observations from the F 1 ( x , y ) function, the surface interpolation and its contour plots are visually smoother with 100 data points compared to 36 and 65 data points. However, like before, distinguishing the effects of different q values remains difficult.
Figure 23, Figure 24, Figure 25, Figure 26, Figure 27, Figure 28, Figure 29 and Figure 30 present the surface interpolation and contour plots for the F 3 ( x , y ) function, again with different q values and data points. The visual smoothness of surface interpolation for 100 data points, as opposed to 36 and 65 data points, mirrors the trends observed with the F 1 ( x , y ) and F 2 ( x , y ) functions. Across all three test functions, the interpolation results generated with 100 data points are accurate, suggesting that an increased number of data points enhances the interpolation accuracy relative to the true surface. However, the similarity in results across different q parameters indicates that visual inspection alone is insufficient to determine the optimal q parameter value.
Since visualization alone is not sufficient to determine which q parameter yields the best interpolation results, error analysis was employed to provide a more robust comparison. Table 1 and Table 2 present the overall measurements for 36, 65, and 100 data points with different q values for the proposed q-Bézier interpolation scheme. Based on these tables, it is evident that as the q parameter increases, there is an improvement in the interpolation quality, reflected by higher R 2 values, a reduced RMSE, and faster CPU time. Specifically, the q values of 0.75 and 1.00 show significant enhancements, indicating a trend toward the properties of the classical Bézier curve when q parameter equals 1.
The error analysis further supports the visual observations: the results for 100 data points consistently outperform those for 36 and 65 data points. This improvement is expected, as a higher number of data points provides a more detailed representation of the underlying function, thus enhancing the interpolation accuracy. Additionally, the CPU time analysis reveals that higher q values lead to faster computations. The combination of a higher R 2 , lower RMSE, and reduced CPU time demonstrates the effectiveness of using a higher q parameter. The subsequent subsection will compare the proposed method with another state-of-the-art interpolation technique, focusing on the two best-performing q parameter values.

4.1. Comparison with Goodman and Said’s Method

Based on the results from Table 1 and Table 2, the optimal q values for the proposed interpolation method are between 0.75 and 1.00. To further validate the effectiveness of the proposed method, we compare it with the cross-derivative method of Goodman and Said [16]. Table 3 and Table 4 present the overall error measurements between the proposed method and the cross derivative method for q values of 0.75 and 1.00 across three test functions.
The result indicate that the proposed method outperforms the cross-derivative method, particularly when the q value is 1.00. Specifically, the proposed method achieves higher R 2 values and lower RMSEs for all three test functions. For instance, with a q value of 1.00, the R 2 values are consistently higher, and the RMSE values are lower, indicating a more accurate fit to the data.
Although the differences in R 2 and RMSE between the proposed method and the cross-derivative method are not significant, the CPU time required for the proposed method is significantly shorter. The proposed method only takes 0.2557 s, 0.2807 s, and 0.2078 s to construct the surface interpolation for the F 1 ( x , y ) , F 2 ( x , y ) , and F 3 ( x , y ) functions, respectively. In contrast, the cross-derivative method requires substantially more time for similar tasks.
These findings suggest that the proposed method not only provides a high degree of accuracy but also offers significant computational advantages. Given these promising results, the next subsection will explore the application of the proposed method on real-life data.

4.2. Testing on Seamount Real Data Points

In this subsection, we apply the proposed method to reconstruct real-life geologic data from the Seamount dataset. This dataset, obtained from MATLAB, represents the underwater surface of a seamount located on the Louisville Ridge in the South Pacific, mapped in 1984. Figure 31 illustrates the Delaunay triangulation of the Seamount data, comprising 294 data points, along with the corresponding 3D interpolation. In Figure 32, the surface interpolation of the Seamount data points is presented for various q values. Furthermore, Figure 33 showcases the 3D interpolation derived from Figure 32.
Table 5 provides a comparative analysis of CPU times for different q values based on the average of three experimental runs. Notably, the q value of 1.00 consistently results in the shortest average time of 157.99 s. This observation aligns with previous findings, reinforcing that a q value of 1.00 not only ensures computational efficiency but also maintains interpolation accuracy.
Upon examining the visualizations, it is evident that the interpolations with a q value of 1.00 yield a smoother and more accurate representation of the Seamount surface compared to other q values. The reduced computational time further emphasizes the practicality of the proposed method for large and complex datasets. The following subsections will present a more detailed comparative analysis applied to engineering-related problems.

4.3. Application to the Electric Potential of Two Point Charges

The scattered data interpolation method obtained in the previous subsection can be applied directly to the problem of the electric potential of two point charges proposed in [38].
The equation can be written as
V = 1 4 π κ 0 g h
where κ 0 = 8.8541878 × 10 12 C N m 2 represents the permittivity constant. g is the magnitude of the charge in coulombs, whereas h is the distance from the particle in meters. Normally, the electric field of two or more particles is calculated using superposition. Based on Figure 34, the electric potential at a point due to two particles is given by
V = 1 4 π κ 0 ( g 1 h 1 + g 2 h 2 )
where g 1 , g 2 , h 1 , and h 2 are the charges of the particles and the distance from the point to the corresponding particle, respectively. In taking g 1 = 2 × 10 10 C and g 2 = 3 × 10 10 C , which are positioned in the x y plane at points ( 0.25 , 0 , 0 ) and ( 0.25 , 0 , 0 ), the scattered data interpolation that uses the q-Bézier triangular patch can solve the proposed problem. The existing Delaunay triangulation for the proposed problem is illustrated in Figure 35 as presented by Ali et al. [39]. Figure 36 showcases the surface interpolation and its corresponding contour plot for both the true function and the existing scheme of Ali et al. [39]. However, our observation indicates that their Delaunay triangulation could be enhanced for better interpolation accuracy by creating a more scattered data distribution. Another critical observation from Figure 36 is that the method of Ali et al. does not approximate the problem accurately, as the results do not closely resemble the actual contour plot.
To address these issues, we manually constructed our own Delaunay triangulation by carefully plotting scattered data with an uneven distribution, not only for 25 data points but also for 36, 65, and 100 data points, as shown in Figure 37. This extension aims to provide a more comprehensive comparative analysis of the proposed scheme. Figure 38 and Figure 39 illustrate the surface interpolation and its contour plot when the q parameter is set to 1. Based on the figures, using 100 data points results in a smoother and more refined surface interpolation and contour plot that closely resembles the true function of the proposed problem. This pattern is consistent with previous sections of this study, where an increased number of data points provided more detailed information and features, better representing the proposed solution.
Table 6 and Table 7 present the error analysis comparing Ali et al.’s method [39] and our proposed method across various q parameter values. Our proposed method achieves the best performance with 100 data points, showing an R 2 value of 0.9908 and an RMSE of 0.5753 when the q parameter is 0.25. This is particularly interesting because, in contrast to the previous sections with different functions, our proposed method performed best when the q parameter was equal to 1. This discrepancy suggests the potential for further exploration of optimal q parameter values to enhance scattered data interpolation schemes. This observation also highlights that different q values may yield the best results depending on the specific function and the nature of the real-life engineering problem being addressed.
Another noteworthy observation is that different arrangements of points, even with the same number of points, yield similar Delaunay triangulation results, as illustrated in Table 6 and Table 7. The performance metrics for these different point arrangements do not show significant variation, indicating that the spatial positioning of points, given a fixed number of points, is not a crucial factor in enhancing the performance of the proposed scheme. This observation suggests that the robustness of the Delaunay triangulation method is maintained irrespective of point arrangement.

4.4. Optimal Value of q

This section describes the optimal value of the q parameter. Previous results from visualization and error analysis indicated that the proposed scheme performs best when the q parameter is set to 1. To explore the potential for other values close to 1, we conducted additional simulations starting from a q value of 0.9 to 1.00 with a step size of 0.01. Table 8 presents the error measurements for 36, 65, and 100 data points across three test functions, ranging from q = 0.90 to q = 1.00 in increments of 0.01.
The results indicate that the R 2 and RMSE values are nearly identical for q values of 0.95, 0.96, 0.97, and 1. To facilitate visualization, we compare these four best q values using error analysis metrics in Figure 40, Figure 41 and Figure 42. The bar chart visualization reveals no significant differences in the R 2 and RMSE values among these selected q values. Notably, the R 2 value is lowest for 36 data points based on the F 2 function, corresponding to the highest RMSE value observed for the same data points.
However, a q value of 0.96 outperforms the other three q values in terms of CPU time. Therefore, considering all error analysis metrics, a q value of 0.96 is optimal. This finding is intriguing, suggesting deviation from the classical Bézier curve typically used in state-of-the-art methods, despite q = 0.96 being close to 1. This presents opportunities for future research to explore optimal q values for enhancing scattered data interpolation methods.

5. Conclusions

In conclusion, this study successfully extends the application of q-Bézier curves to a scattered data interpolation scheme on well-known mathematical functions as well as real-life data. The proposed interpolation scheme was constructed using three local schemes that are blended through a convex combination via an efficient algorithm. The performance of the scheme was rigorously tested with 36, 65, and 100 uniformly distributed data points. Our results indicate that the proposed scheme achieves optimal visualization and error analysis outcomes when the q parameter is set between 0.75 and 1. This finding suggests that the careful tuning of the q parameter is crucial for enhancing interpolation accuracy.
The method presented in this paper is novel and still under exploration, particularly in finding the optimal q parameter. Our current approach is heuristic, and we recognize the need for a more systematic method to determine this parameter. One promising direction is to employ deep learning techniques, particularly Convolutional Neural Networks (CNNs) to optimize the q parameter. This approach involves training a CNN on a comprehensive dataset of scattered data points and their Delaunay triangulations to predict the optimal q parameter.
Additionally, our study is limited by the relatively small number of data points. Increasing the dataset size could provide more comprehensive validation of the proposed scheme and enhance its applicability to a wider range of problems.
Future research will also explore the application of the proposed scheme to image interpolation, particularly for RGB images. This extension could provide significant improvements in image processing tasks, where accurate interpolation is critical for enhancing image quality and resolution.

Author Contributions

Conceptualization, O.T.; data curation, O.T.; formal analysis, O.T. and S.A.A.K.; funding acquisition, S.A.A.K.; investigation, O.T.; methodology, O.T. and S.A.A.K.; project administration, S.A.A.K.; software, O.T. and S.A.A.K.; supervision, S.A.A.K.; validation, O.T. and S.A.A.K.; visualization, O.T. and S.A.A.K.; writing—original draft, O.T.; writing—review and editing, O.T. and S.A.A.K. All authors have read and agreed to the published version of the manuscript.

Funding

This research was fully supported by the Ministry of Higher Education (MOHE) of Malaysia through Fundamental Research Grant Scheme [FRGS/1/2023/ICT06/ UMS/02/1] (New Scattered Data Interpolation Scheme Using Quasi Cubic Triangular Patches for RGB Image Interpolation) and Universiti Malaysia Sabah.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

The data are shared in this paper.

Acknowledgments

The authors give special thanks to the Faculty of Computing and Informatics, Universiti Malaysia Sabah and School of Quantitative Sciences, College of Arts and Sciences, Universiti Utara Malaysia for the tremendous computing facility support.

Conflicts of Interest

The authors declare no conflicts of interest.

Abbreviations

The following abbreviations are used in this manuscript:
RBFsRadial Basis Functions
SNRBFsSquare Normalized Radial Basis Functions
MLSMoving Least Square
RMSERoot Mean Square Error
CPUCentral Processing Unit

References

  1. Franke, R.; Nielson, G. Scattered data interpolation of large sets of scattered data. Int. J. Numer. Methods Eng. 1991, 15, 1–691. [Google Scholar]
  2. Cavoretto, R.; De Rossi, A.; Dell’Accio, F.; Di Tommaso, F. Fast computation of triangular Shepard interpolants. J. Comput. Appl. Math. 2019, 354, 457–470. [Google Scholar] [CrossRef]
  3. Liu, Z. Local multilevel scattered data interpolation. Eng. Anal. Bound. Elem. 2018, 92, 101–107. [Google Scholar] [CrossRef]
  4. Le Borne, S.; Wende, M. Domain decomposition methods in scattered data interpolation with conditionally positive definite radial basis functions. Comput. Math. Appl. 2019, 77, 1178–1196. [Google Scholar] [CrossRef]
  5. Skala, V.; Mourycova, E. Meshfree Interpolation of Multidimensional Time-Varying Scattered Data. Computers 2023, 12, 243. [Google Scholar] [CrossRef]
  6. Joldes, G.R.; Chowdhury, H.A.; Wittek, A.; Doyle, B.; Miller, K. Modified moving least squares with polynomial bases for scattered data approximation. Appl. Math. Comput. 2015, 266, 893–902. [Google Scholar] [CrossRef]
  7. Brodlie, K.W.; Asim, M.R.; Unsworth, K. Constrained visualization using the Shepard interpolation family. Comput. Graph. Forum 2005, 24, 809–820. [Google Scholar] [CrossRef]
  8. Lai, M.J.; Meile, C. Scattered data interpolation with nonnegative preservation using bivariate splines and its application. Comput. Aided Geom. Des. 2015, 34, 37–49. [Google Scholar] [CrossRef]
  9. Schumaker, L.L.; Speleers, H. Nonnegativity preserving macro-element interpolation of scattered data. Comput. Aided Geom. Des. 2010, 27, 245–261. [Google Scholar] [CrossRef]
  10. Karim, S.A.; Saaban, A.; Hasan, M.K.; Sulaiman, J.; Hashim, I. Interpolation using cubic Bézier triangular patches. Int. J. Adv. Sci. Eng. Inf. Technol. 2018, 8, 1746–1752. [Google Scholar] [CrossRef]
  11. Karim, S.A.A.; Saaban, A.; Skala, V.; Ghaffar, A.; Nisar, K.S.; Baleanu, D. Construction of new cubic Bézier-like triangular patches with application in scattered data interpolation. Adv. Differ. Equ. 2020, 2020, 151. [Google Scholar] [CrossRef]
  12. Said, H.; Wirza, R. A Cubic Ball Triangular Patch for the Scattered Data Interpolation. Master’s Thesis, Pulau Pinang, Malaysia, 1994. [Google Scholar]
  13. Feng, R.; Zhang, Y. Piecewise Bivariate Hermite Interpolations for large sets of scattered data. J. Appl. Math. 2013, 2013, 239703. [Google Scholar] [CrossRef]
  14. Sun, Q.; Bao, F.; Zhang, Y.; Duan, Q. A bivariate rational interpolation based on scattered data on parallel lines. J. Vis. Commun. Image Represent. 2013, 24, 75–80. [Google Scholar] [CrossRef]
  15. Bozzini, M.; Lenarduzzi, L.; Rossini, M. Polyharmonic splines: An approximation method for noisy scattered data of extra-large size. Appl. Math. Comput. 2010, 216, 317–331. [Google Scholar] [CrossRef]
  16. Goodman, T.; Said, H. A C1 triangular interpolant suitable for scattered data interpolation. Commun. Appl. Numer. Methods 1991, 7, 479–485. [Google Scholar] [CrossRef]
  17. Foley, T.A.; Opitz, K. Hybrid cubic Bézier triangle patches. In Mathematical Methods in Computer Aided Geometric Design II; Elsevier: Amsterdam, The Netherlands, 1992; pp. 275–286. [Google Scholar] [CrossRef]
  18. Karim, S.A.B.A.; Saaban, A. Visualization terrain data using cubic Ball triangular patches. MATEC Web Conf. 2018, 225, 06023. [Google Scholar] [CrossRef]
  19. Hussain, M.Z.; Hussain, M. C1 positivity preserving scattered data interpolation using rational Bernstein-Bézier triangular patch. J. Appl. Math. Comput. 2011, 35, 281–293. [Google Scholar] [CrossRef]
  20. Chan, E.; Ong, B. Range restricted scattered data interpolation using convex combination of cubic Bézier triangles. J. Comput. Appl. Math. 2001, 136, 135–147. [Google Scholar] [CrossRef]
  21. Azizan, S.; Piah, A.R.M.; Ahmad, A.M. G1 scattered data interpolation with minimized sum of squares of principal curvatures. In Proceedings of the International Conference on Computer Graphics, Imaging and Visualization (CGIV’05), Beijing, China, 26–29 July 2005. [Google Scholar]
  22. Piah, A.R.M.; Saaban, A.; Majid, A.A. Range restricted positivity-preserving scattered data interpolation. Malays. J. Fundam. Appl. Sci. 2006, 2, 63–75. [Google Scholar] [CrossRef]
  23. Hussain, M.; Hussain, M.Z.; Buttar, M. C1 positive Bernstein-Bézier rational quartic interpolation. Triangle 2014, 1, 3. [Google Scholar]
  24. Farin, G.E. Curves and Surfaces for CAGD: A Practical Guide, 5th ed.; Morgan Kaufmann: Burlington, MA, USA, 2002; pp. 1–499. [Google Scholar] [CrossRef]
  25. Franke, R. Scattered data interpolation: Tests of some methods. Math. Comput. 1982, 38, 181–200. [Google Scholar] [CrossRef]
  26. Franke, R.; Nielson, G.M. Scattered data interpolation and applications: A tutorial and survey. In Geometric Modeling: Methods and Applications; Springer: Berlin/Heidelberg, Germany, 1991; pp. 131–160. [Google Scholar]
  27. Lodha, S.K.; Franke, R. Scattered data techniques for surfaces. In Proceedings of the Scientific Visualization Conference (Dagstuhl’97), Dagstuhl, Germany, 9–13 June 1997; IEEE: Piscataway, NJ, USA, 1997; p. 181. [Google Scholar]
  28. Goldman, R.; Simeonov, P. Two essential properties of (q, h)-Bernstein–Bézier curves. Appl. Numer. Math. 2015, 96, 82–93. [Google Scholar] [CrossRef]
  29. Goldman, R.; Simeonov, P.; Simsek, Y. Generating functions for the q-Bernstein bases. SIAM J. Discret. Math. 2014, 28, 1009–1025. [Google Scholar] [CrossRef]
  30. Lewanowicz, S.; Woźny, P.; Area, I.; Godoy, E. Multivariate generalized Bernstein polynomials: Identities for orthogonal polynomials of two variables. Numer. Algorithms 2008, 49, 199–220. [Google Scholar] [CrossRef]
  31. Oruç, H.; Phillips, G.M. q-Bernstein polynomials and Bézier curves. J. Comput. Appl. Math. 2003, 151, 1–12. [Google Scholar] [CrossRef]
  32. Phillips, G.M. A de Casteljau algorithm for generalized Bernstein polynomials. BIT Numer. Math. 1997, 37, 232–236. [Google Scholar] [CrossRef]
  33. Simeonov, P.; Zafiris, V.; Goldman, R. q-Blossoming: A new approach to algorithms and identities for q-Bernstein bases and q-Bézier curves. J. Approx. Theory 2012, 164, 77–104. [Google Scholar] [CrossRef]
  34. Delgado, J.; Orera, H.; Peña, J.M. An evaluation algorithm for q-Bézier triangular patches formed by convex combinations. J. Comput. Appl. Math. 2023, 428, 115184. [Google Scholar] [CrossRef]
  35. Schumaker, L.L. Spline Functions: Computational Methods; SIAM: Philadelphia, PA, USA, 2015. [Google Scholar]
  36. Karim, S.A.A.; Saaban, A.; Nguyen, V.T. Scattered data interpolation using quartic triangular patch for shape-preserving interpolation and comparison with mesh-free methods. Symmetry 2020, 12, 1071. [Google Scholar] [CrossRef]
  37. Fortune, S. A sweepline algorithm for Voronoi diagrams. In Proceedings of the Second Annual Symposium on Computational Geometry, Yorktown Heights, NY, USA, 2–4 June 1986; pp. 313–322. [Google Scholar] [CrossRef]
  38. Gilat, A. MATLAB: An Introduction with Applications; John Wiley & Sons: Hoboken, NJ, USA, 2004. [Google Scholar]
  39. Ali, F.A.M.; Karim, S.A.A.; Dass, S.C.; Skala, V.; Hasan, M.K.; Hashim, I. Efficient visualization of scattered energy distribution data by using cubic timmer triangular patches. In Energy Efficiency in Mobility Systems; Springer: Singapore, 2020; pp. 145–180. [Google Scholar] [CrossRef]
Figure 1. Bases for q-Bézier triangular.
Figure 1. Bases for q-Bézier triangular.
Algorithms 17 00422 g001
Figure 2. Cubic q-Bézier triangular with different values of q.
Figure 2. Cubic q-Bézier triangular with different values of q.
Algorithms 17 00422 g002
Figure 3. Control points for cubic q-Bézier triangular patch.
Figure 3. Control points for cubic q-Bézier triangular patch.
Algorithms 17 00422 g003
Figure 4. Directionals ε 1 , ε 2 , and ε 3 .
Figure 4. Directionals ε 1 , ε 2 , and ε 3 .
Algorithms 17 00422 g004
Figure 5. Two adjacent q-Bézier triangular patches.
Figure 5. Two adjacent q-Bézier triangular patches.
Algorithms 17 00422 g005
Figure 6. Triangulation domain for (a) 36 data points, (b) 65 data points, and (c) 100 data points.
Figure 6. Triangulation domain for (a) 36 data points, (b) 65 data points, and (c) 100 data points.
Algorithms 17 00422 g006
Figure 7. Surface interpolation based on F 1 function with 36, 65, and 100 data points when q = 1 : (a) true surface; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Figure 7. Surface interpolation based on F 1 function with 36, 65, and 100 data points when q = 1 : (a) true surface; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Algorithms 17 00422 g007
Figure 8. Contour plots based on F 1 function with 36, 65, and 100 data points when q = 1 : (a) true surface; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Figure 8. Contour plots based on F 1 function with 36, 65, and 100 data points when q = 1 : (a) true surface; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Algorithms 17 00422 g008
Figure 9. Surface interpolation for 36 data points based on F 1 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 9. Surface interpolation for 36 data points based on F 1 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g009
Figure 10. Contour plots for 36 data points based on F 1 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 10. Contour plots for 36 data points based on F 1 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g010
Figure 11. Surface interpolation for 65 data points based on F 1 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 11. Surface interpolation for 65 data points based on F 1 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g011
Figure 12. Contour plots for 65 data points based on F 1 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 12. Contour plots for 65 data points based on F 1 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g012
Figure 13. Surface interpolation for 100 data points based on F 1 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 13. Surface interpolation for 100 data points based on F 1 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g013
Figure 14. Contour plots for 100 data points based on F 1 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 14. Contour plots for 100 data points based on F 1 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g014
Figure 15. Surface interpolation based on F 2 function with 36, 65, and 100 data points when q = 1 : (a) true surface; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Figure 15. Surface interpolation based on F 2 function with 36, 65, and 100 data points when q = 1 : (a) true surface; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Algorithms 17 00422 g015
Figure 16. Contour plots based on F 2 function with 36, 65, and 100 data points when q = 1 : (a) true surface; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Figure 16. Contour plots based on F 2 function with 36, 65, and 100 data points when q = 1 : (a) true surface; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Algorithms 17 00422 g016
Figure 17. Surface interpolation for 36 data points based on F 2 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 17. Surface interpolation for 36 data points based on F 2 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g017
Figure 18. Contour plots for 36 data points based on F 2 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 18. Contour plots for 36 data points based on F 2 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g018
Figure 19. Surface interpolation for 65 data points based on F 2 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 19. Surface interpolation for 65 data points based on F 2 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g019
Figure 20. Contour plots for 65 data points based on F 2 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 20. Contour plots for 65 data points based on F 2 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g020
Figure 21. Surface interpolation for 100 data points based on F 2 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 21. Surface interpolation for 100 data points based on F 2 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g021
Figure 22. Contour plots for 100 data points based on F 2 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 22. Contour plots for 100 data points based on F 2 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g022
Figure 23. Surface interpolation based on F 3 function with 36, 65, and 100 data points when q = 1 : (a) true surface; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Figure 23. Surface interpolation based on F 3 function with 36, 65, and 100 data points when q = 1 : (a) true surface; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Algorithms 17 00422 g023
Figure 24. Contour plots based on F 3 function with 36, 65, and 100 data points when q = 1 : (a) true surface; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Figure 24. Contour plots based on F 3 function with 36, 65, and 100 data points when q = 1 : (a) true surface; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Algorithms 17 00422 g024
Figure 25. Surface interpolation for 36 data points based on F 3 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 25. Surface interpolation for 36 data points based on F 3 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g025
Figure 26. Contour plots for 36 data points based on F 3 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 26. Contour plots for 36 data points based on F 3 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g026
Figure 27. Surface interpolation for 65 data points based on F 3 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 27. Surface interpolation for 65 data points based on F 3 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g027
Figure 28. Contour plots for 65 data points based on F 3 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 28. Contour plots for 65 data points based on F 3 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g028
Figure 29. Surface interpolation for 100 data points based on F 3 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 29. Surface interpolation for 100 data points based on F 3 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g029
Figure 30. Contour plots for 100 data points based on F 3 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 30. Contour plots for 100 data points based on F 3 function. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g030
Figure 31. Example for (a) true surface, (b) 3D interpolation, and (c) Delaunay triangulation of Seamount data points.
Figure 31. Example for (a) true surface, (b) 3D interpolation, and (c) Delaunay triangulation of Seamount data points.
Algorithms 17 00422 g031
Figure 32. Surface interpolation with different q values based on Seamount data points. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 32. Surface interpolation with different q values based on Seamount data points. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g032
Figure 33. Three-dimensional interpolation with different q values based on Seamount data points. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Figure 33. Three-dimensional interpolation with different q values based on Seamount data points. (a) q = 0.25. (b) q = 0.5. (c) q = 0.75. (d) q = 1.
Algorithms 17 00422 g033
Figure 34. Example of electric potential of two point charges (Adopted from [38]).
Figure 34. Example of electric potential of two point charges (Adopted from [38]).
Algorithms 17 00422 g034
Figure 35. Delaunay triangulation of 25 data points (adopted from [39]).
Figure 35. Delaunay triangulation of 25 data points (adopted from [39]).
Algorithms 17 00422 g035
Figure 36. Surface and contour plot for (a) true function and (b) Ali et al. [39].
Figure 36. Surface and contour plot for (a) true function and (b) Ali et al. [39].
Algorithms 17 00422 g036
Figure 37. Delaunay triangulation of 25, 35, 65, and 100 data points: (a) 25 data points; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Figure 37. Delaunay triangulation of 25, 35, 65, and 100 data points: (a) 25 data points; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Algorithms 17 00422 g037
Figure 38. Surface interpolation with 25, 36, 65, and 100 data points for q value of 1: (a) 25 data points; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Figure 38. Surface interpolation with 25, 36, 65, and 100 data points for q value of 1: (a) 25 data points; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Algorithms 17 00422 g038
Figure 39. Contour plot with 25, 36, 65, and 100 data points for q value of 1: (a) 25 data points; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Figure 39. Contour plot with 25, 36, 65, and 100 data points for q value of 1: (a) 25 data points; (b) 36 data points; (c) 65 data points; (d) 100 data points.
Algorithms 17 00422 g039
Figure 40. R 2 values for 36, 65, and 100 data points across three test functions, evaluated at four selected q values.
Figure 40. R 2 values for 36, 65, and 100 data points across three test functions, evaluated at four selected q values.
Algorithms 17 00422 g040
Figure 41. RMSE values for 36, 65, and 100 data points across three test functions, evaluated at four selected q values.
Figure 41. RMSE values for 36, 65, and 100 data points across three test functions, evaluated at four selected q values.
Algorithms 17 00422 g041
Figure 42. CPU time (in seconds) for 36, 65, and 100 data points across three test functions, evaluated at four selected q values.
Figure 42. CPU time (in seconds) for 36, 65, and 100 data points across three test functions, evaluated at four selected q values.
Algorithms 17 00422 g042
Table 1. Overall error measurements for 36, 65, and 100 data points for q-Bézier with values of 0.25 and 0.50.
Table 1. Overall error measurements for 36, 65, and 100 data points for q-Bézier with values of 0.25 and 0.50.
FunctionData Points R 2 RMSECPU Time (s)
Q 1Q 2Q 1Q 2Q 1Q 2
360.99740.99740.00380.00370.09810.1734
F 1 650.99900.99910.00230.00230.26210.2743
1000.99980.99980.00110.00100.44950.4800
360.98320.98320.01290.01290.15540.1819
F 2 650.99700.99710.00550.00530.27140.3210
1000.99860.99870.00370.00360.52130.4021
360.99730.99750.00420.00400.13360.1562
F 3 650.99930.99940.00210.00200.28170.2079
1000.99980.99990.00110.00100.36530.3178
1  q = 0.25 ; 2  q = 0.50 .
Table 2. Overall error measurements for 36, 65, and 100 data points for q-Bézier with values of 0.75 and 1.00.
Table 2. Overall error measurements for 36, 65, and 100 data points for q-Bézier with values of 0.75 and 1.00.
FunctionData Points R 2 RMSECPU Time (s)
Q 3Q 4Q 3Q 4Q 3Q 4
360.99760.99770.00360.00350.19660.1893
F 1 650.99910.99920.00220.00200.24240.2545
1000.99990.99990.00090.00090.34310.2557
360.98310.98290.01290.01300.21060.1758
F 2 650.99730.99750.00510.00490.25500.1910
1000.99870.99880.00350.00350.28850.2807
360.99770.99780.00380.00370.21450.1850
F 3 650.99950.99950.00190.00180.23010.2583
1000.99990.99990.00080.00070.30590.3024
3  q = 0.75 ; 4  q = 1.00 .
Table 3. Overall error measurements for 36, 65, and 100 data points between the proposed method and Goodman and Said’s method for q-Bézier with value of 0.75.
Table 3. Overall error measurements for 36, 65, and 100 data points between the proposed method and Goodman and Said’s method for q-Bézier with value of 0.75.
FunctionData Points R 2 RMSECPU Time (s)
PS 1GS 2PS 1GS 2PS 1GS 2
360.99760.99760.00360.00360.19660.1670
F 1 650.99910.99920.00220.00210.24240.2045
1000.99990.99990.00090.00080.34310.3071
360.98310.98240.01290.01320.21060.1640
F 2 650.99730.99730.00510.00520.25500.1768
1000.99870.99870.00350.00360.28850.2968
360.99770.99770.00380.00380.21450.1746
F 3 650.99950.99940.00190.00190.23010.1817
1000.99990.99990.00080.00070.30590.2988
1 Proposed method; 2 Goodman and Said’s method.
Table 4. Overall error measurements for 36, 65, and 100 data points between the proposed method and Goodman and Said’s method for q-Bézier with value of 1.00.
Table 4. Overall error measurements for 36, 65, and 100 data points between the proposed method and Goodman and Said’s method for q-Bézier with value of 1.00.
FunctionData Points R 2 RMSECPU Time (s)
PS 1GS 2PS 1GS 2PS 1GS 2
360.99770.99760.00350.00360.18930.1986
F 1 650.99920.99920.00200.00210.21660.2374
1000.99990.99990.00090.00080.25570.3051
360.98290.98240.01300.01320.17580.1769
F 2 650.99750.99730.00490.00520.19100.2638
1000.99880.99870.00350.00360.28070.3589
360.99780.99770.00370.00380.13730.2090
F 3 650.99950.99940.00180.00190.15700.2496
1000.99990.99990.00070.00070.20780.4441
1 Proposed method; 2 Goodman and Said’s method.
Table 5. CPU time comparison between different q values.
Table 5. CPU time comparison between different q values.
q ValuesCPU Time (s)
First RunSecond RunThird RunAverage
0.25163.25159.80158.05160.37
0.50160.45158.11157.78158.78
0.75157.74157.76159.17158.22
1.00157.88158.37157.73157.99
Table 6. Overall error measurements for 25, 36, 65, and 100 data points for q-Bézier.
Table 6. Overall error measurements for 25, 36, 65, and 100 data points for q-Bézier.
MethodData Points R 2 RMSECPU Time (s)
Q 1Q 2Q 1Q 2Q 1Q 2
Fatin250.89580.89341.93741.95920.12440.0989
Proposed250.88680.88712.01952.01660.07430.1184
Proposed360.93560.93561.52331.52250.14630.1746
Proposed650.97910.97890.86740.87090.19540.2669
Proposed1000.99080.99070.57530.57770.26960.3106
1  q = 0.25 ; 2  q = 0.50 .
Table 7. Overall error measurements for 25, 36, 65, and 100 data points for q-Bézier.
Table 7. Overall error measurements for 25, 36, 65, and 100 data points for q-Bézier.
MethodData Points R 2 RMSECPU Time (s)
Q 3Q 4Q 3Q 4Q 3Q 4
Fatin250.89010.88521.98982.03350.16540.1502
Proposed250.88810.88932.00791.99710.07150.0995
Proposed360.93610.93641.51731.51360.11600.1495
Proposed650.97860.97800.87760.88980.18890.1958
Proposed1000.99050.99020.58360.59560.31250.2644
3  q = 0.75 ; 4  q = 1.00 .
Table 8. Overall error measurements for 36, 65, and 100 data points for q-Bézier with values of from 0.90 to 1.00 with step size of 0.01.
Table 8. Overall error measurements for 36, 65, and 100 data points for q-Bézier with values of from 0.90 to 1.00 with step size of 0.01.
q ValueData Points
3665100
F 1 F 2 F 3 F 1 F 2 F 3 F 1 F 2 F 3
0.99770.98300.99780.99920.99740.99950.99990.99880.9999
0.900.00360.01300.00370.00210.00500.00180.00080.00350.0007
0.14490.14190.14870.17520.22670.22100.22560.33260.2341
0.99770.98300.99780.99920.99750.99950.99990.99880.9999
0.910.00360.01300.00370.00210.00500.00180.00080.00350.0007
0.17580.15980.18270.20490.20510.19080.36620.36540.3049
0.99770.98300.99780.99920.99750.99950.99990.99880.9999
0.920.00360.01300.00370.00210.00500.00180.00080.00350.0007
0.18950.17220.17310.21960.20470.19170.34830.32530.3222
0.99770.98300.99780.99920.99750.99950.99990.99880.9999
0.930.00360.01300.00370.00210.00500.00180.00080.00350.0007
0.15090.19660.22060.21540.21060.26090.33220.38730.3712
0.99770.98300.99780.99920.99750.99950.99990.99880.9999
0.940.00360.01300.00370.00210.00500.00180.00080.00350.0007
0.17480.18500.16430.22680.22560.18480.28290.31620.3039
0.99770.98300.99780.99920.99750.99950.99990.99880.9999
0.950.00350.01300.00370.00210.00500.00180.00080.00350.0007
0.15300.16950.18200.20180.20540.25280.39950.39270.3929
0.99770.98300.99780.99920.99750.99950.99990.99880.9999
0.960.00350.01300.00370.00210.00500.00180.00080.00350.0007
0.16700.16010.17370.18400.20910.23100.21720.35760.2682
0.99770.98290.99790.99920.99750.99950.99990.99880.9999
0.970.00350.01300.00370.00210.00500.00180.00080.00350.0007
0.17380.13440.18820.19010.22890.20580.28110.54230.3327
0.99770.98290.99780.99920.99750.99950.99990.99880.9999
0.980.00350.01300.00370.00210.00500.00180.00090.00350.0007
0.16890.08500.17730.20880.21340.21850.30950.29410.6070
0.99770.98290.99780.99920.99750.99950.99990.99880.9999
0.990.00350.01300.00370.00210.00500.00180.00090.00350.0007
0.16890.08520.13090.18980.19440.18140.27920.25710.2659
0.99770.98290.99780.99920.99750.99950.99990.99880.9999
1.000.00350.01300.00370.00200.00490.00180.00090.00350.0007
0.18930.17580.18500.25450.19100.25830.25570.28070.3024
Note: For each q value, the three corresponding sub-rows represent: (i) R 2 , (ii) RMSE, (iii) CPU time (in seconds).
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Share and Cite

MDPI and ACS Style

Tamin, O.; Karim, S.A.A. Cubic q-Bézier Triangular Patch for Scattered Data Interpolation and Its Algorithm. Algorithms 2024, 17, 422. https://doi.org/10.3390/a17090422

AMA Style

Tamin O, Karim SAA. Cubic q-Bézier Triangular Patch for Scattered Data Interpolation and Its Algorithm. Algorithms. 2024; 17(9):422. https://doi.org/10.3390/a17090422

Chicago/Turabian Style

Tamin, Owen, and Samsul Ariffin Abdul Karim. 2024. "Cubic q-Bézier Triangular Patch for Scattered Data Interpolation and Its Algorithm" Algorithms 17, no. 9: 422. https://doi.org/10.3390/a17090422

APA Style

Tamin, O., & Karim, S. A. A. (2024). Cubic q-Bézier Triangular Patch for Scattered Data Interpolation and Its Algorithm. Algorithms, 17(9), 422. https://doi.org/10.3390/a17090422

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop