1
$\begingroup$

Suppose I have an algebraic curve in its implicit form, i.e. described as the set of points $(x,y)$ where some polynomial $P(x,y)$ becomes zero. All of this is in the real Euclidean (or with minor modifications projective) plane. If the degree of that polynomial isn't too high, I can compute a bunch of points on that curve by explicitely computing roots of the polynomial. Otherwise numeric root finding techniques might be used. So assume I have a bunch of points on the curve.

Now I want to approximate this curve using cubic Bezier splines, as many computer graphics environments provide them. To do so, I guess I'd use the points I computed above as end points of the individual spline segments. Getting them into the correct order might be tricky, in the presence of unconnected components or even self-intersections, but let's assume I manage to do so.

Next I need the Bezier control points. I guess I'd want to choose them in such a way that the tangent direction and curvature of the Bezier interpolation matches that of the algebraic curve at the point where the spline segment begins. Computing the tangent at a given point is described on Wikipedia. So I know the line connecting the end point and the control point.

But how large should the distance between the end point and the corresponding control point for the spline segment be, in order to match curvature?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You can get four equations for the four coordinates of the two control points by twice differentiating the defining equation $P(x,y)=0$ with respect to the curve parameter $t$:

$$ \dot xP_x+\dot yP_y=0\;,\\ \ddot xP_x+\ddot yP_y+\dot x^2P_{xx}+2\dot x\dot yP_{xy}+\dot y^2P_{yy}=0\;. $$

Each of these yields two equations, one at each endpoint. The first two express the same as the tangent calculation in the Wikipedia article. Together the four equations determine the four coordinates of the control points such that the spline coincides with the curve up to second order.

At both points, you can use the first equation to express $\dot x$ and $\dot y$ linearly in terms of the distance $d$ to the control point and then substitute that into the second equation to obtain an equation of the form

$$ \ddot xP_x+ \ddot yP_y+ad^2=0\;. $$

Then you can express the second derivatives of the coordinates as linear combinations of the distances (in contrast to the first derivatives, they will depend on both distances), and solve the resulting system of two quadratic equations in the two distances.

$\endgroup$
4
  • $\begingroup$ Hi @joriki, I am after something similar. However I don't understand your notation. What is $\dot x$ and $P_x$ etc, derivatives? e.g. if I have two points, their first and second derivatives, how do I fit the curve? If it is just a normal polynomial do the y's disappear? $\endgroup$
    – geometrikal
    Jan 17, 2013 at 12:27
  • $\begingroup$ @geometrikal: The dots denote differentiation with respect to the curve parameter $t$ (a convention used in physics). The subscripts $x$ and $y$ denote partial differentiation with respect to $x$ and $y$, respectively. I don't understand your last question about the $y$'s disappearing. $\endgroup$
    – joriki
    Jan 17, 2013 at 13:36
  • $\begingroup$ thanks. I understand what they mean now. With the y's disappearing, what I was thinking was that if the function was a polynomial, $a_0 + a_1 x + a_2 x^2 ... a_n x^n = y$, then would $P_y = -1$ and $P_{yy} = 0$? Apologies if I'm missing something. $\endgroup$
    – geometrikal
    Jan 17, 2013 at 13:51
  • $\begingroup$ @geometrikal: Yes, that's right. $\endgroup$
    – joriki
    Jan 17, 2013 at 14:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .