Bisector approximation


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.


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.

  • $\begingroup$ 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 :) $\endgroup$ – 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.

enter image description here

  • $\begingroup$ 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. $\endgroup$ – Arthur C Jul 12 '18 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.