Finding the arc above a point

One of the first things we need to do when a site event occurs is to find the arc within the beach line which is directly above the new site 'S'. For this we cycle through all of the break points within the beach line and find the next break point. We compare the 'x' coordinate of the new site and the next break point, if the new site is greater than the 'x' coordinate of the next break point we continue, if it isn't we stop and the associated arc is the one which is above the new site. Listed below is the general equation for a parabolas equation; this is required for both the parabolas to work out the intersection point:

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


$$ \begin{align} a &= \frac{1}{4p}\\[5px] b &= \frac{-h}{2p}\\[5px] c &= \frac{h^2}{4p}+k\\[5px] \end{align} $$


$$ \begin{align} (h, k) &= (x, y)\textit{ of parabolas vertex}\\ p &= \textit{the distance between the parabolas focus and its vertex OR}\\ &= \textit{distance from the parabolas vertex to its directrix (sweep line)}\\ \therefore p &= \frac{site.y - sweepline.y}{2} \end{align} $$

Where the parabolas intersect their respective 'x' and 'y' coordinates are equal. If we subtract one parabolas equation from the other we're left with the quadratic equation. We can then use the quadratic formula to solve for 'x', we can then plug this 'x' value back one of the parabolas equations to solve 'y'.

$$ \begin{align} a &= a_1 - a_2\\ b &= b_1 - b_2\\ c &= c_1 - c_2\\ x &= \frac{-b\pm\sqrt{b^2-4ac}}{2a} \end{align} $$


$$ \begin{align} x_1 &= \frac{-b+\sqrt{b^2-4ac}}{2a}\\[5px] x_2 &= \frac{-b-\sqrt{b^2-4ac}}{2a}\\[5px] \end{align} $$

Notice two 'x' coordinates are found, the one you want depends on the 'y' coordinate of the parabola's focus. The parabolas, and the edges are stored within a binary tree. Two leafs are compared at a time, then the next pair are compared (moving along one leaf at a time). If the left parabola's focus is lower than the rights we select the maximum 'x' value, if not we select the minimum value. See the diagrams below for a bit of an explanation of why this is the case. We start with three parabolas, A, B and C and we want to insert a new point shown on the sweep line below:

We start at the left most pairing within the beach line and we come up with the intersection between the parabolas A and B. The new points 'x' coordinate is greater than the intersections 'x' value so we continue and compare the next two pairs, B and C:

The intersections 'x' coordinate is still less than the 'x' coordinate of the new point, so we need to check out the intersection between the next two parabolas, C and A. We can see this now produces an intersection whose 'x' value us greater than the new point 'x' value, therefore the new point has to be located under parabola C:


Also note there are degenerate cases, for example:

  1. If both parabolas share the same y coordinate they will only intersect in one location. In this situation the x coordinate is halfway between the two parabolas.
  2. If we have two parabolas which are exactly the same on the beach line, this would mean then is an infinite amount of intersections. The way around this in the case of the fortune sweep algorithm is to simply not accept two sites with the same x,y coordinate.
  3. If the new point occurs exactly on a break point between two parabolas.