Chaikin algorithm – Calculate the coordinate points of the smooth curve corresponding to the polyline
This article will introduce an algorithm for calculating the coordinate points of a smooth curve corresponding to a polyline. This algorithm uses the Chaikin curve smoothing method to adjust the smoothness and accuracy of the curve by controlling the tension factor and the number of iterations. By cutting and interpolating the original point set, a smooth curve coordinate point set is obtained. Experimental results show that the algorithm can effectively smooth polylines and has high accuracy and controllability.
Article directory
- Chaikin algorithm – calculate the coordinate points of the smooth curve corresponding to the polyline
-
- introduction
- algorithm
-
- Algorithm process
- Chaikin curve smoothing
- Experiments and results
-
- Test 1: Verify the algorithm results under different iteration numbers
- Test 2: Observe the algorithm results under different tension factors
- in conclusion
- References
Introduction
In the fields of computer graphics and data visualization, the generation of smooth curves is an important problem. Smooth curves can make data easier to understand and analyze, and can also improve the aesthetics of graphics. Polyline is a common method of representing curves, but the polyline itself has high noise and jagged characteristics and needs to be smoothed. This paper proposes an algorithm based on Chaikin curve smoothing, which can convert polylines into smooth curves.
Algorithm
Algorithm process
The specific steps of the process are as follows:
- Check the validity of the input coordinate point set and ensure that there are at least 3 coordinate points.
- Perform range constraints on the input parameters to ensure that the number of iterations is greater than or equal to 1 and the tension factor is between 0 and 1.
- Maps the tension factor to between 0.05 and 0.45 for use when calculating cutting distance.
- Iterative calculation, using Chaikin curve smoothing method to process the coordinate point set.
- Returns the smoothed curve coordinate point collection.
/// <summary>
/// Calculate the coordinate points of the smooth curve corresponding to the polyline
/// </summary>
/// <param name="points">Coordinate collection</param>
/// <param name="tension">Tension factor [0,1], used to control the smoothness of the curve. The smaller the tension factor, the closer the cutting point will be to the starting point of the line segment, and vice versa. </param>
/// <param name="iterationCount">Number of iterations, used to control the accuracy of curve smoothing</param>
/// <returns></returns>
/// <exception cref="ArgumentException"></exception>
private List<Point> SmoothCurveChaikin(Point[] points, float tension = 0.5f, byte iterationCount = 1)
{<!-- -->
//Coordinate point legality check
if (points == null || points.Length < 3)
{<!-- -->
throw new ArgumentException("At least 3 coordinate points are required.", nameof(points));
}
// Parameter range constraints
iterationCount = Math.Max(iterationCount, (byte)1);
tension = Math.Max(tension, 0);
tension = Math.Min(tension, 1);
// The parameter limit is between 0 and 1 to simplify the use and understanding of parameters. Mapping the value range of the tension factor to between 0 and 1 makes the parameter range more intuitive and easier to control.
// By multiplying the tension factor by 0.4 and adding 0.05, a parameter between 0 and 1 can be mapped to between 0.05 and 0.45 for use when calculating the cutting distance.
//The tension factor is used here to control the smoothness of the curve. Specifically, the tension factor defines a scale for the half-length tangent distance of a line segment, with values ranging from 0.05 to 0.45.
// When the tension factor is 0.5, it is equivalent to using the classic Chaikin algorithm, which is to cut each line segment into two points, one-quarter and three-quarters. This maintains the symmetry of the curve.
double cutlist = 0.05 + (tension * 0.4);
// iterative calculation
List<Point> lst = points.ToList();
for (int i = 1; i <= iterationCount; i + + )
{<!-- -->
lst = SmoothChaikin(lst, cutdist);
}
return lst;
}
Chaikin curve smoothing
Chaikin curve smoothing is a method based on cutting and interpolation. By cutting and interpolating line segments, a smooth curve is obtained.
Specific steps are as follows:
- Adds the first point, which is the first point in the original set of points.
- Split each point into two points before and after, and perform interpolation calculations by calculating the cutting distance parameter and the coordinates of the original point.
- Add the two points calculated by interpolation.
- Adds the last point, which is the last point in the original set of points.
- Returns the smoothed curve coordinate point collection.
/// <summary>
/// Perform Chaikin curve smoothing on point collections
/// </summary>
/// <param name="points">Original points of the curve to be smoothed</param>
/// <param name="cuttingDist">Cutting distance parameter, used to define the scale of line segment cutting. The value range is usually between 0.05 and 0.45, used to control the smoothness of the curve</param>
/// <returns></returns>
private List<Point> SmoothChaikin(List<Point> points, double cuttingDist)
{<!-- -->
//Add first point
List<Point> nl = new List<Point> {<!-- --> points[0] };
// Split each point into two points before and after
Point q, r;
for (int i = 0; i < points.Count - 1; i + + )
{<!-- -->
q = new Point(
(int)Math.Round(((1 - cuttingDist) * points[i].X + cuttingDist * points[i + 1].X)),
(int)Math.Round(((1 - cuttingDist) * points[i].Y + cuttingDist * points[i + 1].Y))
);
r = new Point(
(int)Math.Round((cuttingDist * points[i].X + (1 - cuttingDist) * points[i + 1].X)),
(int)Math.Round((cuttingDist * points[i].Y + (1 - cuttingDist) * points[i + 1].Y))
);
nl.Add(q);
nl.Add(r);
}
//Add the last point
nl.Add(points.Last());
return nl;
}
Experiments and results
In order to verify the effectiveness and reliability of the algorithm, we conducted two sets of tests.
Test 1: Verify the algorithm results under different iteration times
Test steps:
- Set the tension factor to 0.5.
- Adjust the number of iterations to 1, 2, and 3.
- Compare the algorithm results under different iteration numbers.
Test 2: Observe the algorithm results under different tension factors
Test steps:
- Set the number of iterations to 1.
- Adjust the tension factor to 0, 0.2, 0.4, 0.6, 0.8.
- Observe the algorithm results under different tension factors.
This algorithm was tested under different parameter settings, and curves with different smoothness and accuracy were obtained. Experimental results show that when the tension factor is small, the cutting point will be close to the starting point of the line segment, and the smoothness of the curve is low; when the tension factor is large, the cutting point will be close to the end point of the line segment, and the smoothness of the curve is high. Increasing the number of iterations can improve the smoothing accuracy of the curve, but it will also increase the time complexity of the calculation. Experimental results also show that this algorithm can effectively smooth polylines and has high accuracy and controllability.
Conclusion
This article introduces an algorithm for calculating the coordinate points of a smooth curve corresponding to a polyline. This algorithm uses the Chaikin curve smoothing method to adjust the smoothness and accuracy of the curve by controlling the tension factor and the number of iterations. Experimental results show that the algorithm can effectively smooth polylines and has high accuracy and controllability. Future work can further optimize the performance of the algorithm and expand the application scope of the algorithm.
Reference materials
- 2D Polyline Vertex Smoothing