So I am trying to implement the Fortune's algorithm in order to have a Voronoi pattern (wonderful post about it here : http://www.ams.org/publicoutreach/feature-column/fcarc-voronoi)
For this, I need to know intersections between two parabolas, which I know how to do (thanks to this article : http://www.zonalandeducation.com/mmts/intersections/intersectionOfTwoParabollas1/intersectionOfTwoParabolas1.htm) but also something that the first article doesn't cover : how to find the value Y of the directrix when I want two parabolas to intersect in a specific X coordinate (while the two parabolas share the same directrix - 'the sweep line').
Let me explain better : See the image descripting the thing - As I am not allowed to have embed image yet :'( The thing that the 1st article doesn't cover is that the edges between some sites infinitely continue to the left or to the right. What I want is to limit it into a plane (a square). So, I have :
- A plane with its edges (I know the X and Y coordinates of its edges)
- Two focus points, f1 and f2 (for Fortune, those focus points are the sites), of the two parabolas, p1 and p2.
- A directrix (for Fortune, 'the sweep line') which is the same for all the focus points, and which I can move up and down as I want.
And I don't have the intersection between p1, p2 and the edges of the plane.
Actually, what I would like to have is the intersections circled in red here : https://i.stack.imgur.com/vp0Ql.jpg (I already have those in purple, thanks to the second article), but in order to get them, I need to find the Y-value of the directrix where two parabolas will intersect with the edge of the plane.
So, as shown in the image, how to find the Y value of the directrix, in order to get the intersection between p1, p2 and the left edge ?
Thank you for your time,
Cyril G
This circled point $P$ is such that $d:=PF_1=PF_2=PH$ by definition of a parabola (same distance from a focus than to the directrix), you just have to take the directrix at vertical distance $d$ from $P$.