Project a parabolic curve to straight lines.

conic sectionsgeometric-constructiongeometry

I am working with Voronoi Diagrams and I'm given a parabolic curve that is described through four parameters:

A start point, say $P_0(x_0,y_0)$.
An end point, say $P_1(x_1,y_1)$.
A focus point, say $F(x_f,y_f)$.
And a directrix line $l$, say from point $L_0$ to $L_1$.

Instead of calculating the parabola points (as in the Wiki), I'd like to find a third point, let's say $C$, that creates two straight lines (e.g. horizontal and vertical) between $P_0$ and $P_1$, such that it "follows" the curve. For example, for the following image, if $P_0 = (3,3)$ and $P_1 = (5,1)$, then I want to find $C = (3,1)$.

I was looking into Bezier curves, but it does not seem to fulfill my needs. The control point seems to depend on the curvature of the parabola, thus it might not give the straight lines I seek.

Is there a proper way to calculate such a point?

EDIT: For the figure above there are two possible solutions to connect $P_0$ to $P_1$ with two straight lines (i.e. horizontal or vertical). Either we go east then south; or south then east. Following the curve means the later solution is the one I am seeking because it somewhat follows the parabola.

I could say point $C$ is farthest from the focal point; but rather than this simple algorithm I would like to know if there's a more robust and mathematical definition for such point, such as Bezier Curves. You could this simply does not exist and that would be a valid solution.

Brainstorming: I've thought about using the tangent crossing (as in the comments below) but they don't yield the exact point I need as they depend on the slope. I've also thought about interpreting this parabola as part of a circle and computing the tangent crossings, but, intuitively, that seems to run into the same problem.

Best Answer

As far as I can see, your question is not related to the parabola. You have two points, $P_0 =(x_0, y_0)$ and $P_1 = (x_0, y_0)$, and you want to construct a third point, $C = (C_x, C_y)$. The coordinates of $C$ are given by $C_x = \min(x_0, x_1)$ and $C_y = \min(y_0, y_1)$.

But perhaps I’m not correctly understanding what you mean by “follows the curve”. If you can give a better definition of that term, then the folks here can give you a better answer.

Edit (after you improved the question)
There are only two choices for the point $C$. I described one of them above. The right choice of $C$ depends on whether the parabola lies above or below the line $P_0P_1$. So, take the mid-point of the parabola (or some other convenient point lying on the parabola) and check whether it lies above or below the line $P_0P_1$.

If above, then $C_x = \max(x_0, x_1)$ and $C_y = \max(y_0, y_1)$.

If below, then $C_x = \min(x_0, x_1)$ and $C_y = \min(y_0, y_1)$.

The locus

After doing some computations in the spirit (and building on the code) of my vertex anser, I found the locus of $P$ to be a quadric

$$ a\,x^2 + b\,y^2 + c\,xy + d\,x + e\,y + f = 0 $$

with the following parameters:

\begin{align*} a&=4\left(-A_y\,B_y + B_y^2 + A_y\,C_y - B_y\,C_y\right)\\ b&=4\left(-A_x\,B_x + B_x^2 + A_x\,C_x - B_x\,C_x\right)\\ c&=4\left(A_y\,B_x + A_x\,B_y - 2\,B_x\,B_y - A_y\,C_x + B_y\,C_x - A_x\,C_y + B_x\,C_y\right)\\ d&=4\left(A_y\,B_x\,B_y - A_x\,B_y^2 + A_y\,B_y\,C_x - B_y^2\,C_x - 2\,A_y\,B_x\,C_y + A_x\,B_y\,C_y + B_x\,B_y\,C_y\right)\\ e&=4\left(-A_y\,B_x^2 + A_x\,B_x\,B_y + A_y\,B_x\,C_x - 2\,A_x\,B_y\,C_x + B_x\,B_y\,C_x + A_x\,B_x\,C_y - B_x^2\,C_y\right)\\ f&=A_y^2\,B_x^2 - 2\,A_x\,A_y\,B_x\,B_y + A_x^2\,B_y^2 - 2\,A_y^2\,B_x\,C_x + 2\,A_x\,A_y\,B_y\,C_x \\&\quad{} - 2\,A_y\,B_x\,B_y\,C_x + 2\,A_x\,B_y^2\,C_x + A_y^2\,C_x^2 - 2\,A_y\,B_y\,C_x^2 + B_y^2\,C_x^2 \\&\quad{} + 2\,A_x\,A_y\,B_x\,C_y + 2\,A_y\,B_x^2\,C_y - 2\,A_x^2\,B_y\,C_y - 2\,A_x\,B_x\,B_y\,C_y \\&\quad{} - 2\,A_x\,A_y\,C_x\,C_y + 2\,A_y\,B_x\,C_x\,C_y + 2\,A_x\,B_y\,C_x\,C_y - 2\,B_x\,B_y\,C_x\,C_y \\&\quad{} + A_x^2\,C_y^2 - 2\,A_x\,B_x\,C_y^2 + B_x^2\,C_y^2 \end{align*}

Assumption confirmed

Using this formulation, I could verify your assumption: the conic is indeed a hyperbola, with the lines $AB$ and $CB$ as asymptotes. The way to check this is by ensuring that the lines are tangents, and that they touch the conic at infinity.

Special location

In a comment below, you mention that you might assume $B_x=B_y=0$. With that your conic will become

\begin{align*} a&=4\,A_y\,C_y\\ b&=4\,A_x\,C_x\\ c&=-4\left(A_y\,C_x + A_x\,C_y\right)\\ d&=0\\ e&=0\\ f&=A_y^2\,C_x^2 - 2\,A_x\,A_y\,C_x\,C_y + A_x^2\,C_y^2 \end{align*}

The formula is indeed a lot easier, so it might be a good starting point for a geometric description of the curve. For example, it is readily apparent that this hyperbola will be symmetric around the origin. But we already knew $B$ to be the center due to the asymptotes. You can even take this one step further and, via an affine transformation, consider only the case where

\begin{align*} A &= \begin{pmatrix}1\\0\end{pmatrix} & B &= \begin{pmatrix}0\\0\end{pmatrix} & C &= \begin{pmatrix}0\\1\end{pmatrix} \end{align*}

You end up with the hyperbola

$$4xy=1$$

From this you can e.g. conclude that the midpoint between $A$ and $C$ will also lie on that hyperbola. It will of course correspond to a Bézier curve which passes through $B$ for some $t<0$ or $t>1$. You can take that midpoint and reflect it in $B$ to obtain a point on the segment of the hyperbola you get for $0\le t\le 1$. This construction is invariant under affine transformations, so it still holds for the general case. Two asymptotes plus one point on the hyperbola amounts to five real degrees of freedom, so this should be enough to uniquely define your hyperbola.

Summary

To sum it up: the locus of the apex $P$ is the unique hyperbola with asymptotes $AB$ and $CB$ which passes through the midpoint between $A$ and $C$. The portion of it which corresponds to parabolas where $B$ lies between $A$ and $C$, i.e. is obtained in the Bézier curve for $0<t<1$, is the component of the hyperbola which does not contain that midpoint. It does contain the point obtained by reflecting that midpoint in $B$.

The code

Here is the sage code I used to obtain this representation:

# Define multivariate polynomial ring and points
PR1.<A_x, A_y, B_x, B_y, C_x, C_y, P_x, P_y, t> = QQ[]
A = vector(PR1, [A_x, A_y, 1])
B = vector(PR1, [B_x, B_y, 1])
C = vector(PR1, [C_x, C_y, 1])
P = vector(PR1, [P_x, P_y, 1])

# Quadratic Bézier curve parametrized by t
Bt = (1-t)^2*A + 2*(1-t)*t*P + t^2*C
r1 = (Bt[0] - B_x).resultant(Bt[1] - B_y, t) # eliminate t

# Obtain coefficients for coordinates of P
c1 = vector(PR1, flatten([list(i.polynomial(i.parent()(P_y)))
                          for i in r1.polynomial(P_x)]))
f, e, b, d, c, a = c1

# Print result
fmt1 = [str(i/4).replace('*','\\,')
        for i in [a, b, c, d, e]] + [str(f)]
fmt2 = [i + '&=4\\left(' + j + '\\right)'
        for i, j in zip('abcdef', fmt1)]
fmt2[-1] = 'f&='+fmt1[-1]
print('\\\\\n'.join(fmt2))

# Check whether lines AB and CB are asymptotes of the Hyperbola
Hyperbola = Matrix([
  [2*a, c, d],
  [c, 2*b, e],
  [d, e, 2*f]])
def onConic(p, c=Hyperbola):
    return (p.row()*c*p.column())[0,0].is_zero()
asymptotes = [B.cross_product(p) for p in [A, C]]
infLine = vector(QQ, [0,0,1])
# asymptotes are tangents to the hyperbola:
assert(all(onConic(i, Hyperbola.adjoint()) for i in asymptotes))
# asymptotes touch the hyperbola at infinity:
assert(all(onConic(i.cross_product(infLine)) for i in asymptotes))

# The midpoint between A and C is on the hyperbola:
assert(onConic(A+C))

Originally I had more complicated code which did not rely on the interpretation as a Bézier curve. The result was the same, though.

Generalizing to rational case

Can we generalize to rational quadratic Bezier curves (i.e. to conic section curves that are not necessarily parabolas)?

A parabola has four real degrees of freedom. If you choose a non-rational Bézier curve, you have two real degrees of freedom, but with these you not only specify a parabola but also select a start point and an end point on that parabola, so the degrees of freedom match. A conic in general has five real degrees of freedom. So if you want it to pass through three given points, that still leaves a two-parameter family of corresponding conics. Therefore your locus will not be a single curve, but either the whole plane or some portion of it.

You can define a conic using five points through which it should pass. In addition to your $A,B,C$ you might use two more points, which you move close to the end points $A$ and $C$. By making them arbitrary close (i.e. computing some limit), you can use these control points to exactly and arbitrarily determine the direction of the tangents in $A$ and $C$. Therefore you can choose any point $P$ in the plance, and find a conic through $A,B,C$ which will have $P$ as its apex. In this sense, the whole plane will be your locus.

I'm not completely sure whether a rational Bézier curve can be defined in such a way that it passes through infinity, but I believe that to be the case. If not, then there might be cases where the resulting conic would be a hyperbola, and $A,B,C$ are not all three in the same of its components. This might result in a restriction to part of the plane.

[Math] Can different control points lead to the same Bézier curve

The equation for the cubic Bézier curve is $$ F(u) = (1-u)^3 P_0 + 3 (1-u)^2 u P_1 + 3 (1-u)u^2 P_2 + u^3 P_3 $$ and therefore $$F(0) = P_0, \quad F(1) = P_3$$ and, by differentiation, $$ F'(0) = 3(P_1 - P_0), \quad F'(1) = 3(P_3 - P_2) $$

Therefore all control points are uniquely determined by the function $F$.

But, as you already noted, there can be two different Bézier curves having the same image, e.g. if all control points are on a line. I don't have an answer for the question

When are the control points uniquely determined by the image of a Bézier curve?