Círculo dados 2 puntos y tangente en el Algoritmo de Voronoi de Fortune

Question

Aproximación bisectriz

Hola

Intento comprender y implementar una adaptación del algoritmo de Fortune para Diagramas de Voronoi en cuanto a su extensión al manejo de líneas, pero estoy atascado en lo siguiente: Habiendo calculado $x_t$ en la tangente a la Bisectriz B por $x_0$ , necesito encontrar la intersección con la Bisectriz B y la línea que une los Focos E y $x_t$ .

Esto parecía un problema simple, donde sólo calcular la intersección de B y g, sin embargo me parece que no puede averiguar cómo encontrar $x_1$ dada una directriz y un foco arbitrarios, ya que esta Bisectriz no es una función (porque la directriz no es de la forma y=c, c una constante).

En el artículo "Voronoi Diagrams of Polygons, A Framework for Shape Representation" de Niranjan Mayya y V. T. Rajan dan una prueba utilizando la segunda imagen Prueba . Aquí construyen un círculo a través de $x_0$ E y la directriz como tangente. Ahora $x_1$ debe ser el centro de este círculo. Este sería el circuncentro del triángulo con vértices E, P y $x_0$ (siendo P la intersección de la recta perpendicular que pasa por $x_0$ sobre la directriz y la propia directriz). Como no conozco P, necesitaría encontrar el centro utilizando las siguientes fórmulas:

Tome el centro C(a,b), E( $e_1,e_2$ ), $x_0$ ( $x_1,y_1$ ) y $v = \frac{-a}{b}$ entonces

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 y 2 porque E y $x_0$ están en el círculo y R debido a la distancia perpendicular de C a M

He intentado resolver esto para a y b, pero por alguna razón esto me da una ecuación cuadrática (no entiendo por qué, ya que sólo habría 1 centro) y honestamente, no parece el enfoque correcto.

Por eso mi pregunta: ¿Podría alguien ayudarme con esto? Parece que necesito encontrar el centro de una circunferencia dados 2 puntos y una tangente en su forma general. No puede ser tan difícil, ya que describen calcular $x_1$ como "muy fácil". Parece que necesito ayuda con algo "muy fácil" :)

editado para notación.

Answer 1

No he leído toda la pregunta, pero la esencia --- quiero encontrar una circunferencia, dados dos puntos y una tangente, y no entiendo por qué esto debería hacerme resolver una cuadrática --- parecía relativamente fácil. El siguiente diagrama muestra que para algunas instancias del problema (dos puntos azules; una tangente verde) hay de hecho dos círculos resolviéndolo, por lo tanto deberías esperar una ecuación que tiene (o puede tener) múltiples raíces.

Answer 2

La respuesta de John Hughes responde a su pregunta central de por qué se trata de una ecuación cuadrática. Me gustaría ofrecerte una forma alternativa de calcular los círculos que podría ser un poco menos tediosa. Sean los dos puntos por los que debe pasar la circunferencia $P_1=(x_1,y_1)$ y $P_2=(x_2,y_2)$ y que $M=(x_m,y_m)$ sea su punto medio. El círculo centrado en $M$ que pasa por $P_1$ y $P_2$ tiene ecuación $$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$$ y la recta que pasa por estos puntos tiene ecuación $$g(x,y) = (y_1-y_2)x-(x_1-x_2)y+(x_1y_2-x_2y_1)= 0.$$ Cada círculo a través de $P_1$ y $P_2$ tiene por tanto una ecuación de la forma $$f(x,y)+\lambda g(x,y)=0\tag{*}$$ con centro $$\left(x_m-\frac\lambda2(y_1-y_2), y_m+\frac\lambda2(x_1-x_2)\right).$$ Estos centros se encuentran en la mediatriz de $P_1P_2$ . Sustituyendo el valor de $x$ o $y$ de la ecuación de la recta tangente en (*) te da una ecuación cuadrática en la otra variable que debe tener una raíz repetida. Ajustando el discriminante de esta ecuación a cero se obtiene una ecuación cuadrática en $\lambda$ resolver.