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
- $(e1-a)^2 + (e2-b)^2 = r^2$
- $(x1-a)^2 + (y1-b)^2 = r^2$
- $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.
Best Answer
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.