VectSharp  2.2.1
A light library for C# vector graphics
SmoothSpline.cs
1 /*
2  VectSharp - A light library for C# vector graphics.
3  Copyright (C) 2020-2022 Giorgio Bianchini
4 
5  This program is free software: you can redistribute it and/or modify
6  it under the terms of the GNU Lesser General Public License as published by
7  the Free Software Foundation, version 3.
8 
9  This program is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU Lesser General Public License for more details.
13 
14  You should have received a copy of the GNU Lesser General Public License
15  along with this program. If not, see <https://www.gnu.org/licenses/>.
16 */
17 
18 using System;
19 using System.Collections.Generic;
20 using System.Linq;
21 using System.Text;
22 
23 namespace VectSharp
24 {
25  //derived from https://www.particleincell.com/wp-content/uploads/2012/06/bezier-spline.js
26 
27  internal static class SmoothSpline
28  {
29  public static Point[] SmoothSplines(Point[] points)
30  {
31  double[] x = (from el in points select el.X).ToArray();
32  double[] y = (from el in points select el.Y).ToArray();
33 
34  (double[] p1, double[] p2) px = ComputeControlPoints(x);
35  (double[] p1, double[] p2) py = ComputeControlPoints(y);
36 
37  List<Point> tbr = new List<Point>();
38 
39  for (int i = 0; i < points.Length - 1; i++)
40  {
41  tbr.Add(new Point(x[i], y[i]));
42  tbr.Add(new Point(px.p1[i], py.p1[i]));
43  tbr.Add(new Point(px.p2[i], py.p2[i]));
44  }
45 
46  tbr.Add(new Point(x[x.Length - 1], y[x.Length - 1]));
47 
48  return tbr.ToArray();
49  }
50 
51  /*computes control points given knots K, this is the brain of the operation*/
52  private static (double[] p1, double[] p2) ComputeControlPoints(double[] K)
53  {
54  int n = K.Length - 1;
55 
56 
57  double[] p1 = new double[n];
58  double[] p2 = new double[n];
59 
60 
61  /*rhs vector*/
62  double[] a = new double[n];
63  double[] b = new double[n];
64  double[] c = new double[n];
65  double[] r = new double[n];
66 
67  /*left most segment*/
68  a[0] = 0;
69  b[0] = 2;
70  c[0] = 1;
71  r[0] = K[0] + 2 * K[1];
72 
73  /*internal segments*/
74  for (int i = 1; i < n - 1; i++)
75  {
76  a[i] = 1;
77  b[i] = 4;
78  c[i] = 1;
79  r[i] = 4 * K[i] + 2 * K[i + 1];
80  }
81 
82  /*right segment*/
83  a[n - 1] = 2;
84  b[n - 1] = 7;
85  c[n - 1] = 0;
86  r[n - 1] = 8 * K[n - 1] + K[n];
87 
88  /*solves Ax=b with the Thomas algorithm (from Wikipedia)*/
89  for (int i = 1; i < n; i++)
90  {
91  double m = a[i] / b[i - 1];
92  b[i] = b[i] - m * c[i - 1];
93  r[i] = r[i] - m * r[i - 1];
94  }
95 
96  p1[n - 1] = r[n - 1] / b[n - 1];
97  for (int i = n - 2; i >= 0; i--)
98  {
99  p1[i] = (r[i] - c[i] * p1[i + 1]) / b[i];
100  }
101 
102  /*we have p1, now compute p2*/
103  for (int i = 0; i < n - 1; i++)
104  {
105  p2[i] = 2 * K[i + 1] - p1[i + 1];
106  }
107 
108  p2[n - 1] = 0.5 * (K[n] + p1[n - 1]);
109 
110  return (p1, p2);
111  }
112 
113  }
114 }
VectSharp
Definition: Brush.cs:26