0
$\begingroup$

I am trying to understand the steps in a modified version of the Fortune's algorithm for voronoi generation (http://blog.ivank.net/fortunes-algorithm-and-implementation.html).

I've stumbled on the following solution for finding the point(s) of intersection of two parabolas (both with a directrix parallel to the x axis and a focus above the directrix):

  1. Given two parabolas:

    y = $a_{1}x^2 + b_{1}x + c_{1}$

    y = $a_{2}x^2 + b_{2}x + c_{2}$

  2. Solve the following equation:

    $(a_{1}-a_{2})x^2 + (b_{1}-b_{2})x + (c_{1}-c_{2})$

  3. Then x of the intersection(s) is the solution to the equation in 2.:

    $a = a_{1}-a_{2}$; $b = b_{1}-b_{2}$; $c = c_{1}-c_{2}$

    $x_{1} = \frac{-b + \sqrt{b^2 - 4ac}}{2a}$

    $x_{2} = \frac{-b - \sqrt{b^2 - 4ac}}{2a}$

    and y of the first intersection(s) is:

    $y_{1} = a_{1} * x_{1}^2 + b_{1} * x_{1} + c_{1}$

    $y_{2} = a_{2} * x_{2}^2 + b_{2} * x_{2} + c_{2}$

where X is the solution of the quadratic the two parabolas are:

Looking for explanations I found this Stack overflow post that mentions the same solution: Algebraic solution for the intersection point(s) of two parabolas.

I also found many online calculators (mostly written in JavaScript) that use the same technique to calculate the intersection of two parabolas (for example this calculator: http://zonalandeducation.com/mmts/intersections/intersectionOfTwoParabollas1/intersectionOfTwoParabolas1.htm).

Can someone explain in simple terms why this solution holds true and what is the mathematical proof behind that?

I understand that at the points of intersection the two parabolas have equal values for both x and y. But I don't have a clue how taking the difference of the coefficients helps in finding the points.

$\endgroup$
  • 1
    $\begingroup$ aren't you just solving the two equations simultaneously, which in this case means equating the $y$ expressions? The result is then the expression in part 2 set $=0$ $\endgroup$ – David Quinn Mar 20 '18 at 11:44
  • $\begingroup$ @DavidQuinn You are right, seems that the code is actually solving $a_{1}x^2 + b_{1}x + c_{1} = a_{2}x^2 + b_{2}x + c_{2}$, which is simplified to $a_{1}x^2-a_{2}x^2 + b_{1}x-b_{2}x + c_{1}-c_{2} = 0$, and then again to $(a_{1}-a_{2})x^2 + (b_{1}-b_{2})x + (c_{1}-c_{2}) = 0$ $\endgroup$ – quasoft Mar 20 '18 at 13:02
1
$\begingroup$

At first to solve for $x$ equate $y$ expressions. When same power $x$ terms are brought to LHS of quadratic equation to solve you get another quadratic equation whose coefficients are difference of the individual parabola coefficients.

If

$$ a_2-a_1 = a, b_2-b_1=b, c_2-c_1=c$$

then roots of

$$ax^2+bx+c =0 $$

give all points of intersection.

They may be none(imaginary roots, parabolas are disjunct), one real coincident ( roots, parabolas tangential) or two real roots for two points of intersection.

Each of the three case is discussed in the link (zonalandeducation) you gave.

Please note that in the case of real points of intersection of (red,blue parabolas ) whose coefficients are taken from link the roots of the difference quadratic (green) are situated directly below the cutting point. So it is necessary to draw the third graph in this case.

enter image description here

$\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.