# Circle given 2 points and tangent in Fortune's Voronoi Algorithm

Bisector approximation

Hello

I am trying to understand and implement an adaption of Fortune's algorithm for Voronoi Diagrams regarding its extension to handling lines, but I am stuck on the following: Having calculated $x_t$ on the tangent to the Bisector B through $x_0$, I need to find the intersection with the Bisector B and the line connection the Focus E and $x_t$.

This looked like a simple problem, where you just calculate the intersection of B and g, however I can't seem to figure out how to find $x_1$ given an arbitrary directrix and focus, since this Bisector is not a function (because the directrix is not of the form y=c, c a constant).

In the paper "Voronoi Diagrams of Polygons, A Framework for Shape Representation" by Niranjan Mayya and V. T. Rajan they give a proof using the second image Proof. Here they construct a circle through $x_0$, E and the directrix as tangent. Now $x_1$ should be the center of this circle. This would be the circumcenter of the triangle with vertices E, P and $x_0$ (with P the intersection of the perpendicular line through $x_0$ on the directrix and the directrix itself). Since I don't know P, I would need to find the center using following formulas:

Take the center C(a,b), E($e_1,e_2$), $x_0$($x_1,y_1$) and $v = \frac{-a}{b}$, then

1. $(e1-a)^2 + (e2-b)^2 = r^2$
2. $(x1-a)^2 + (y1-b)^2 = r^2$
3. $r = \frac{|va-b+q| }{\sqrt{v^2+1}}$

1 and 2 because E and $x_0$ are on the circle and R because of the perpendicular distance from C to M

I tried solving this for a and b, but for some reason this gives me a quadratic equation (I don't understand why, since there would be just 1 center) and honestly, it doesn't seem the right approach.

Therefore my question: Could anyone help me on this one? Seems like I need to find the center of a circle given 2 points and a tangent in its general form. It can't be that hard, since they describe calculating $x_1$ as "very easy". Looks like I need some help with something "very easy" :)

edited for notation.

## 2 Answers

John Hughes’ answer addresses your core question of why a quadratic equation is involved. I’d like to offer you an alternative way to compute the circles that might be a bit less tedious. Let the two points that the circle must pass through be $P_1=(x_1,y_1)$ and $P_2=(x_2,y_2)$ and let $M=(x_m,y_m)$ be their midpoint. The circle centered at $M$ that passes through $P_1$ and $P_2$ has equation $$f(x,y) = (x-x_m)^2+(y-y_m)^2-\frac14\left((x_1-x_2)^2+(y_1-y_2)^2\right) = 0$$ and the line through these points has equation $$g(x,y) = (y_1-y_2)x-(x_1-x_2)y+(x_1y_2-x_2y_1)= 0.$$ Every circle through $P_1$ and $P_2$ therefore has an equation of the form $$f(x,y)+\lambda g(x,y)=0\tag{*}$$ with center $$\left(x_m-\frac\lambda2(y_1-y_2), y_m+\frac\lambda2(x_1-x_2)\right).$$ These centers lie on the perpendicular bisector of $P_1P_2$. Substituting the value of $x$ or $y$ from the equation of the tangent line into (*) gives you a quadratic equation in the other variable that must have a repeated root. Setting the discriminant of this equation to zero then yields a quadratic equation in $\lambda$ to solve.

• After calculating everything using your help, I realized the image in the paper mentioned above wasn't accurate. I thought $x_0$ was a point on the circle. It wasn't however. I did manage to find the circle I need using your method, with the difference of saying the Center C should be on the line connecting $e_i$ and x. Once I did this, I was able to calculate the Center using the steps you described. Thank you so much for your help, this was exactly what I needed :) – Arthur C Jul 13 '18 at 12:15

I didn't read the whole question, but the gist --- I want to find a circle, given two points and a tangent, and I don't understand why this should make me solve a quadratic --- seemed relatively easy. The following diagram shows that for some instances of the problem (two blue points; one green tangent) there are in fact two circles solving it, hence you should expect an equation that has (or may have) multiple roots.

• I was so focused on this 1 case I never thought about drawing another circle. This is why I get stuck on every calculation I did so far, since there is not a unique circle determined by a tangent and 2 points. I do have another constraint: $x_t$ has to be insinde the circle if I understand the paper correctly. So using that the distance from the center to $x_t$ < R should get me the correct circle, thus the unique center. Thank you for this clarification! I might try that out. However, I am sure there has to be a simpler way, since this calculation is extremely tedious. – Arthur C Jul 12 '18 at 13:11