3
$\begingroup$

The motivation for this is Bezier curves. But, if you don't know what these are, you can skip down to the last paragraph, where the problem is described in purely algebraic terms.

Suppose I want to construct a quadratic Bezier curve that passes through some given points.

First, the standard approach: I would use three points, say $\mathbf A$, $\mathbf B$, $\mathbf C$, choose a "middle" parameter value, typically $h = \tfrac12$, and then construct a quadratic curve $\mathbf P(t)$, such that $\mathbf P(0) = \mathbf A$, $\mathbf P(h) = \mathbf B$, and $\mathbf P(1) = \mathbf C$. Easy.

But, it's fairly well known that given four coplanar points, you can (usually) construct a parabola that passes through them. This problem goes back to Newton, even. But, every parabola is a quadratic Bezier curve. So, given the four coplanar points $\mathbf A$, $\mathbf B$, $\mathbf C$, $\mathbf D$, I'm hoping that there is a fairly simple calculation that gives us a quadratic Bezier curve passing through them.

More specifically, let's call the quadratic Bezier curve $\mathbf P(t)$, again, and let $\mathbf P_0$, $\mathbf P_a$, $\mathbf P_1$ be its control points, so that $$\mathbf P(t) = (1-t)^2 \mathbf P_0 + 2t(1-t) \mathbf P_a + t^2 \mathbf P_1$$ We want to find control points $\mathbf P_0$, $\mathbf P_a$, $\mathbf P_1$ and parameter values $t=u$ and $t=v$ such that $$\mathbf P(0) = \mathbf A \quad ; \quad \mathbf P(u) = \mathbf B \quad ; \quad \mathbf P(v) = \mathbf C \quad ; \quad \mathbf P(1) = \mathbf D \quad$$ It's obvious that $\mathbf P_0 = \mathbf P(0) = \mathbf A$, and $\mathbf P_1 = \mathbf P(1) = \mathbf D$, so the remaining problem is to find the middle control point $\mathbf P_a$ and the two parameter values $u$ and $v$. I'd like to know how to calculate these remaining unknowns. Ideally a nice simple way.

There is a paper on this subject, but the authors' approach seems oddly complex and esoteric, to me. I'm hoping for a simple series of elementary calculations that a smart high-school student could understand.

As far as I can tell, you don't need to know anything about Bezier curves to solve this problem. It can be considered purely algebraically: we are given $\mathbf A$, $\mathbf B$, $\mathbf C$, $\mathbf D$ in $\mathbb R^2$, and we want to find $\mathbf P \in \mathbb R^2$ and $u,v \in \mathbb R$ such that $$(1-u)^2 \mathbf A + 2u(1-u) \mathbf P + u^2 \mathbf D = \mathbf B$$ $$(1-v)^2 \mathbf A + 2v(1-v) \mathbf P + v^2 \mathbf D = \mathbf C$$ So, it's really just an equation solving problem.

$\endgroup$
  • $\begingroup$ I see now what you want to do! I have deleted my response. $\endgroup$ – TonyK May 20 '13 at 10:21
  • $\begingroup$ @Cantlog -- I was waiting for a better one. But I guess I've waited long enough :-) $\endgroup$ – bubba Sep 27 '13 at 0:00
1
$\begingroup$

Solved it myself, as below. I don't feel that this solution is "right" somehow, because it treats the interior points $\mathbf B$ and $\mathbf C$ very asymmetrically, so improvements are invited. But, anyway ...

Let's use the notation from the last few paragraphs of the question.

It's clear that $\mathbf P(0) = \mathbf A$, and $\mathbf P(1) = \mathbf D$, so these two points are interpolated, already, and we only have to worry about the other two points, $\mathbf C$ and $\mathbf D$.

First, we find numbers $h$ and $k$ such that $$\mathbf C = \mathbf A + h(\mathbf B - \mathbf A) + k(\mathbf D - \mathbf A) = (1-h-k)\mathbf A + h\mathbf B + k\mathbf D$$ This is possible provided that $\mathbf A$, $\mathbf B$, $\mathbf D$ are not collinear. Then, since $\mathbf P(v) = \mathbf C$, we have $$(1-h-k)\mathbf A + h\mathbf B + k\mathbf D = (1-v)^2 \mathbf A + 2v(1-v) \mathbf P + v^2 \mathbf D $$ But, since $\mathbf P(u) = \mathbf B$, we know that $$ \mathbf B = (1-u)^2 \mathbf A + 2u(1-u) \mathbf P + u^2 \mathbf D$$ Substituting for $\mathbf B$ on the left-hand side, and equating coefficients of $\mathbf A$, $\mathbf P$, $\mathbf D$ gives $$(1-v)^2 = 1 - h - k +h(1-u)^2 $$ $$2v(1-v) = 2hu(1-u)$$ $$v^2 = hu^2 + k $$ We can easily eliminate $v$ from these last three equations using the fact that $[2v(1-v)]^2 = 4[v^2][(1-v)^2]$. We get: $$[2hu(1-u)]^2 = 4[hu^2 + k][1 - h - k +h(1-u)^2]$$ After a little algebra, this reduces to: $$h(1-h)u^2 - 2hku + k(1-k) = 0$$

So, we solve this quadratic for $u$, and then get the unknown interior control point $\mathbf P$ from

$$ \mathbf P = \frac{\mathbf B - (1-u)^2 \mathbf A -u^2 \mathbf D}{2u(1-u)}$$

The number of solutions depends on the number of real solutions of the quadratic. Quite often, you can draw two different quadratic Bezier curves through the four given points, as explained in the paper cited in the question.

| cite | improve this answer | |
$\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.