3
$\begingroup$

Let $x(t)$ and $y(t)$ be unknown polynomials (of maximum order 3) defining a parametric curve

$$ \mathbf{r}(t)=\begin{bmatrix}x(t)\\y(t)\end{bmatrix} $$

that fits known tangential end-points:

$$ \mathbf{r}(0)=\begin{bmatrix}x_0\\y_0\end{bmatrix} $$ $$ \mathbf{r}(1)=\begin{bmatrix}x_1\\y_1\end{bmatrix} $$ $$ \mathbf{r}'(0)=k_0\begin{bmatrix}x'_0\\y'_0\end{bmatrix} $$ $$ \mathbf{r}'(1)=k_1\begin{bmatrix}x'_1\\y'_1\end{bmatrix} $$

where $x_0$, $y_0$, $x_1$, $y_1$, $x'_0$, $y'_0$, $x'_1$, $y'_1$ are known constants specifying the end-point locations and directions, and $k_0$, $k_1$ are scaling factors we don't care about.

To find $\mathbf{r}(t)$ it is possible to set $k_1=k_2=1$, and then split the problem into two independent cubic Hermite interpolations in x and in y. The resulting $\mathbf{r}(t)$ technically satisfies all constraints above, but when I tested this by interpolating between tangential points drawn from the unit-circle, I got the following result.

The blue data points enforce position and local direction.

Is there an approach that would give a more reasonable result than the above?

My problem specifically concerns data points with pre-determined directions at each data point.

$\endgroup$
  • $\begingroup$ Just for clarification: If you have at most 3rd order polynomials in x and y, then to do the piecewise cubic interpolation, you need to know the derivatives of x and y and their values at all seven points. In addition, you need two boundary conditions for both x and y at the end points. I'm assuming you have done all this. $\endgroup$ – D.B. May 3 '18 at 17:59
  • $\begingroup$ @D.B. The direction is known at each control point. This is part of the input data. $\endgroup$ – Museful May 3 '18 at 18:02
  • $\begingroup$ I haven't tried the problem, but I'm guessing that there is not a single-valued function relationship between $x$ and $y$. In other words, it appears that between each point, there are multiple values of $y$ that exist for a single calculated value of $x$ (hence, the loops). When you find the $x(t)$ and $y(t)$ independently, you are not controlling the relationship between $x$ and $y$. $\endgroup$ – D.B. May 3 '18 at 18:09
  • $\begingroup$ Do you want to solve it for small problems by hand or for large sets of points and vectors? I did something like that last summer, but maybe it's a bit overkill to what you want. $\endgroup$ – mathreadler May 3 '18 at 18:20
  • 1
    $\begingroup$ @mathreadler I'm writing a software library for use with arbitrary size sets. $\endgroup$ – Museful May 3 '18 at 18:24
4
$\begingroup$

It look like the loops you get is due too big tangent vectors, something like this:

enter image description here

As an heuristic (which might not always work well), try to scale given tangents at both ends of every segment to fit the distance between given endpoints of the segment, and you'll get something like this:

enter image description here

More examples with original curve in red:

6 segments:

enter image description here

7 segments:

enter image description here

The example curves were obtained by the following procedure:

given $n+1$ points $p_i=(x_i,y_i)$ and vectors $p'_i=(x'_i,y'_i)$, $i=0\,\ldots\,,n$, construct $n$ cubic Bezier segments

\begin{align} s_i&\left(p_i, \ p_i+\tfrac13\left(\frac{\|p_{i+1}-p_i\|}{\|p'_i\|} \right)\,p'_i, \ p_{i+1}-\tfrac13\left(\frac{\|p_{i+1}-p_i\|}{\|p'_{i+1}\|} \right)\,p'_{i+1}, \ p_{i+1}\right) ,\quad i=0,\,\ldots\,,n-1 . \end{align}

$\endgroup$
  • $\begingroup$ I had tried to scale $k0$ and $k1$ with no apparent effect. Are you talking about Bezier curve control points? $\endgroup$ – Museful May 3 '18 at 20:55
  • $\begingroup$ @Museful: Scale vector $(x'_i,y'_i)$ to fit the length $|(x_i,y_i)-(x_{i+1},y_{i+1})|$ The effect is shown in the pictures. It works surprisingly well with different curves, I must admit. $\endgroup$ – g.kov May 3 '18 at 21:40
  • 1
    $\begingroup$ After some reading up, I think this scaling can be automated by restricting the curve to a quadratic Bezier. There is exactly one feasible quadratic Bezier for each segment. $\endgroup$ – Museful May 3 '18 at 23:10
0
$\begingroup$

Try clamped spline interpolation. You'll get a piecewise cubic curve interpolating the given points for which you can prescribe the tangent directions at the endpoints.

$\endgroup$
  • $\begingroup$ In my case each data point has a known tangent direction. So I am performing one-hop clamped spline interpolation 6 times. Actually 12 times in my attempt to separate x and y. $\endgroup$ – Museful May 3 '18 at 18:21
  • $\begingroup$ Oh, interesting. So at each point, you have an independent tangent vector? Then it sounds like you would be in a 4-dimensional space. $\endgroup$ – D.B. May 3 '18 at 18:31
  • $\begingroup$ @D.B. Yes, an independent tangent vector at each point. But they are only meaningful up to factor of scale. $\endgroup$ – Museful May 3 '18 at 18:34
  • $\begingroup$ If I am given a set of points {x(t},y(t)}, and I want to find a curve r(t) = x(t)i+y(t)j, where I declare the derivatives of x and y with respect to t at each point, then I would simply have two piecewise cubic splines, one for x and the other for y. So, on one graph, you would have x(t), and on a separate graph, you would have y(t). $\endgroup$ – D.B. May 3 '18 at 18:42
0
$\begingroup$

Here is a suggested solution. You do not need two independent functions of $t$ because you are just in a two-dimensional space. Just focus on fitting a third order polynomial to the function $y(t)$. Then, the vector-valued solution will automatically be $r(t) = t\hat{i} + y(t)\hat{j}$. Does this make sense?

$\endgroup$
  • $\begingroup$ That would have been simpler, but my curves cannot necessarily be expressed as $y(x)$. Also I would like the curve shape to be independent of choice of coordinate axes direction. $\endgroup$ – Museful May 3 '18 at 18:26
0
$\begingroup$

Sorry I have been swamped in a sea of work for a bit, but now as promised my contribution.


You can achieve this by linear fusion of two models,

  1. One set of discretized "snake" vectors, like proposed in question here.

    (This approach also partially answers that question.)

  2. Polynomial regression on both coordinates separately.

You then assign each vector in the snake sum / integral : $$\cases{P_x(\Delta_t k) = \displaystyle\sum_{i=0}^k {\bf v[k]}_x\\P_y(\Delta_t k) = \displaystyle\sum_{i=0}^k {\bf v[k]}_y}$$

Then you choose the nodes in your snake to carry the end-point constraints. Especially constraints about derivatives (tangent vectors) and position are practical to carry such constraints.

Then you build a big linear least squares system out of it and solve it. This will be super general, you can even split and let different polynomials take responsibility of fitting individual areas of the snake and to fuse their end-points (kind of similar to what splines will do), you can also regularize the snake to minimize total curve length, it's first, second partial derivatives and so on.

enter image description here

Here is an example with a black contour and we choose to try and fix the yellow points. Then we fit a snake to the yellow points, and simultaneously force it to be pushed towards a polynomial and simultaneously regularize it's curve length, first derivatives (a bit). As we can see order 3 (red) is not big enough polynomial to fit all points.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.