0
$\begingroup$

For a optimisation task I'm facing a problem that my limited geometrical knowledge can't solve. I have a cloud of points in a 2d plane, where I want to perform some binary metric on to select a threshold of x and y where some rules are maximized. I performed regression on the points to found a line (r^2 0.89).

By indipendent optimization of the two axis I know two limit points p = (5, 0) and o = (0,3) where the parabola should intersect. I further have the equation of the regression line where the vertex of the parabola should be. The goal would be move the vertex of the parabola until it degenerates into a line to this points

visually this is the data https://ibb.co/Smg0tpQ I want to draw a parabola that passes through the red dots and that has the vertex on the line. By doing intersect of three points the vertex is not on the line. I tried with a system with f(point1), f(point2) and then the third one in vertex form but as I need to do it programmatically it got very messy. I would like to have some theoretical insights about how to tackle this problem algorithmically

$\endgroup$
  • $\begingroup$ Does one of the points lie on the line and thus is a vertex? Or is it a coincidence? Also, directrix isn't a vertex, so please change the title so it is no longer confusing $\endgroup$ – Vasily Mitch Nov 27 '18 at 15:28
  • $\begingroup$ @VasilyMitch yep the vertex should be on the line, while intersecting the other two points. The algorithm will move the parabola until it degenerates into a line (i.e a = 0 in y=ax*2 + bx +c). $\endgroup$ – D.A. Nov 27 '18 at 16:45
  • $\begingroup$ Just to make things clear: the position of the vertex for the parabola to become a line is obviously at the intersection between line $AB$ and the line of the vertex. But you want the equation of the parabola for a generic vertex. Is that correct? $\endgroup$ – Aretino Nov 30 '18 at 19:06
  • 1
    $\begingroup$ Seems like it should be doable. Three points are not in themselves enough to determine a parabola uniquely, but the additional constraint that one is the vertex ought to be enough. However, everything that I’ve tried so far devolves to solving a rather unpleasant-looking cubic. $\endgroup$ – amd Dec 1 '18 at 1:10
  • $\begingroup$ @amd I agree with you: a cubic equation pops up and I see no way to avoid it. This could also explain why this construction is not covered, to my knowledge, in any text on parabolas. $\endgroup$ – Aretino Dec 1 '18 at 12:33
0
$\begingroup$

Once you’ve nailed down the vertex of a parabola, there are two degrees of freedom left (e.g., axis direction and scale factor, focus location, &c). The two other known points provide additional constraints that can be used to determine the values of the remaining parameters. Unfortunately, it appears that doing so unavoidably leads to having to solve a cubic equation. Of the methods that I’ve tried, the following leads to probably the “nicest” cubic.

The one-parameter family of parabolas with vertex at $(x_0,y_0)$ and axis direction $(c,s)$ has equations of the form $$(s(x-x_0)-c(y-y_0))^2 = p(c(x-x_0)+s(y-y_0)).\tag 1$$ The parabolas’ common axis of symmetry is the line $s(x-x_0)-c(y-y_0)=0$, while $c(x-x_0)+s(y-y_0)=0$ is their tangent at the vertex. By construction, the two left-hand sides vanish only at the vertex, so for any other point on the parabola we can solve for $p$: $$p = {(s(x-x_0)-c(y-y_0))^2 \over c(x-x_0)+s(y-y_0)}. \tag 2$$ For simplicity, let’s assume that the vertex is at the origin; translation doesn’t affect the axis direction or scale factor $p$. Substituting the two known (translated) points $(x_1,y_1)$ and $(x_2,y_2)$ leads to the homogeneous cubic equation $$(x_1y_2^2-x_2y_1^2) c^3 + (2x_1x_2(y_1-y_2)+y_1y_2^2-y_1^2y_2) c^2s + (2y_1y_2(x_1-x_2)+x_1x_2^2-x_1^2x_2) cs^2 + (x_2^2y_1-x_1^2y_2) s^3 = 0 \tag 3$$ in $c$ and $s$. With a real solution to this equation in hand, you can compute $p$ and substitute back into (1) for an equation of the parabola. Indeed, we can do part of this substitution now to obtain $$(s(x-x_0)-c(y-y_0))^2(c(x_1-x_0)+s(y_1-y_0)) = (s(x_1-x_0)-c(y_1-y_0))^2(c(x-x_0)+s(y-y_0)) \tag 4$$ or a similar equation with $x_2$ and $y_2$ instead of $x_1$ and $y_1$.

The good news is that there’s an algorithm for solving equations of this form of cubic, so it can be automated even if you don’t have access to an equation solver. You can find this algorithm in J. Richter-Gebert's Perspectives on Projective Geometry section 11.4 as part of a method of intersecting two conics. The not-so-good news for your application is that for some configurations the solution set consists of two (points are colinear) or three distinct lines through the origin instead of one—the parabola is not unique. If you want to show a smooth progression of parabolas as the vertex moves along the line, you’ll have to do a bit of extra work to choose the appropriate solution of the three. It might be possible, for instance, to parameterize the moving vertex and use the same parameter for family of parabolas generated by it given the fixed pair of other points through which the parabolas should go.

Here’s a plot from Mathematica approximating your diagram, and the parabolas that result from some equally-spaced vertices along the line.

enter image description here

I’ve also put together a little GeoGebra demo that you can play with to see this solution in action.

You mention in a comment that you don’t necessarily need a parabola for your application. Working up a smoothly-varying family of hyperbolas might be a bit easier than the above, but with a hyperbola you’ve got an extra degree of freedom, so you’ll have to make some additional choices for each one as compared to computing these parabolas.

Addendum: The number of real solutions of the single-varible cubic equation $ax^3+bx^2+cx+d=0$ with real coefficients can be determined by examining its discriminant $$\Delta = 18abcd-4b^3d+b^2c^2-4ac^3-27a^2d^2.$$ If $\Delta\gt0$, then the equation has three distinct real roots; if $\Delta=0$, then there is a multiple root and all roots are real; if $\Delta\lt0$, there is only one real root. We want a non-trivial solution to equation (3), so we can divide through by whichever of $c$ or $s$ is nonzero to convert that equation into a single-variable cubic equation and then compute $\Delta$ to determine whether or not we will need to deal with multiple solutions to (3). Observe that the formula for $\Delta$ is the same if we swap $a$ with $d$ and $b$ with $c$, so we don’t actually need to worry about either $c$ or $s$ being zero: the discriminant is the same for both of the single-variable equations that might result. Computing the discriminant of (3) yields a rather complicated expression that has a factor of $(x_1y2-x_2y_1)^2$, so the equation has a repeated real root when the three points are colinear (as noted earlier). This term is positive for other configurations, so the number of roots depends on the remaining term, but I’ve gained no geometric insight from looking at it.

$\endgroup$
  • $\begingroup$ Perfect thank a lot, exactly what I was looking for. No matter how complicated it is as long as it is a clear solution it can be implemented. If interested I will post here the code for future reference. So just out of curiosity to have only one solution what else would it be needed? $\endgroup$ – D.A. Dec 3 '18 at 7:50
  • $\begingroup$ @D.A. I haven’t looked into the precise conditions under which there are multiple independent real solutions. When the points are colinear, then the solution set is exactly the two lines that define the family, with one of them doubled. From playing around in GeoGebra, it looks like you also get three real lines when the points are almost colinear, with the vertex not “between” the other two points. For your application, I think I’d explore the parameterization that I suggested in my latest edit first. $\endgroup$ – amd Dec 3 '18 at 8:03

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.