Intersection of Parabolas for Voronoi Diagram

Question

I asked another question with the same title and relating to the same problem on Stack Overflow, here. In short, I am trying to implement Fortune's Algorithm for creating a Voronoi diagram and I can't figure out how to find the (x,y) intersection of two parabolas each created by the equation $y=\frac{(x - x_f)^2}{2(y_f - y_d)} + \frac{y_f + y_d}{2}$ where x is a variable, $x_f$ and $y_f$ are the x and y coordinates of a focus and $y_d$ is the y coordinate of the directrix. I have been unable to get the equation into the standard form of a quadratic despite it creating the shape of a parabola. So far, I've gotten set two copies of the equation equal to itself, set them equal to zero, and put the resulting equation through wolfram Alpha's online polynomial expander, producing $$\frac{-X^2f_{x1} + X^2f_{y2} + 2d_yf_{x1}X - 2d_yf_{x2}X + 2f_{x2}f_{y1}X - 2f_{x1}f_{y2}X + d_y^2f_{y1} - d_y^2f_{y2} - d_yf_{y1}^2 + d_yf_{y2}^2 - f_{y1}f_{y2}^2 + f_{y1}^2f_{y2} + d_yf_{x2}^2 - f_{x2}^2f_{y1} - d_yf_{x1}^2 + f_{x1}^2f_{y2}}{2(d_y^2 - d_yf_{y1} - d_yf_{y2} + f_{y1}f_{y2})}$$

but I am unsure of how to precede from here.

Answer 1

Starting from the quadratic equation given by this form. Please review each step and make sure I didn't make mistakes on the way: $$y=\frac{1}{2(y_f-y_d)}(x-x_f)^2+\frac{y_f+y_d}{2}$$

Using two of these equations renaming the parameters, you equate them:

$$\frac{1}{2(y_f-y_d)}(x-x_f)^2+\frac{y_f+y_d}{2} = \frac{1}{2(y_{f2}-y_{d2})}(x-x_{f2})^2+\frac{y_{f2}+y_{d2}}{2}$$

Now comes the rearangement of the terms in the following steps:

$$(x-x_f)^2 = \frac{(y_f-y_d)}{(y_{f2}-y_{d2})}(x-x_{f2})^2+2(y_f-y_d)\left(\frac{y_{f2}+y_{d2}}{2}-\frac{y_f+y_d}{2}\right)$$

Then,

$$x^2-2xx_f+x_f^2 = \frac{(y_f-y_d)}{(y_{f2}-y_{d2})}(x^2-2xx_{f2}+x_{f2}^2)+2(y_f-y_d)\left(\frac{y_{f2}+y_{d2}}{2}-\frac{y_f+y_d}{2}\right)$$

Then,

$$x^2-\frac{(y_f-y_d)}{(y_{f2}-y_{d2})}x^2-2xx_f+2\frac{(y_f-y_d)}{(y_{f2}-y_{d2})}xx_{f2} = x_{f2}^2\frac{(y_f-y_d)}{(y_{f2}-y_{d2})}+2(y_f-y_d)\left(\frac{y_{f2}+y_{d2}}{2}-\frac{y_f+y_d}{2}\right)-x_f^2$$

Then,

$$x^2\left(1-\frac{(y_f-y_d)}{(y_{f2}-y_{d2})}\right)-x\left(2x_f+2\frac{(y_f-y_d)}{(y_{f2}-y_{d2})}x_{f2}\right) = x_{f2}^2\frac{(y_f-y_d)}{(y_{f2}-y_{d2})}+2(y_f-y_d)\left(\frac{y_{f2}+y_{d2}}{2}-\frac{y_f+y_d}{2}\right)-x_f^2$$

Then,

$$x^2\left(1-\frac{(y_f-y_d)}{(y_{f2}-y_{d2})}\right)+x\left(-2x_f-2\frac{(y_f-y_d)}{(y_{f2}-y_{d2})}x_{f2}\right) -x_{f2}^2\frac{(y_f-y_d)}{(y_{f2}-y_{d2})}-2(y_f-y_d)\left(\frac{y_{f2}+y_{d2}}{2}-\frac{y_f+y_d}{2}\right)+x_f^2=0$$

After getting this we can rename the terms:

$$a=1-\frac{(y_f-y_d)}{(y_{f2}-y_{d2})}$$

$$b=-2x_f-2\frac{(y_f-y_d)}{(y_{f2}-y_{d2})}x_{f2}$$

$$c=-x_{f2}^2\frac{(y_f-y_d)}{(y_{f2}-y_{d2})}-2(y_f-y_d)\left(\frac{y_{f2}+y_{d2}}{2}-\frac{y_f+y_d}{2}\right)+x_f^2$$

And simply use the formula to get the intersection x values.

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

To get the y values simply replace in the original quadratic equation each of the x values.