math - software - Problema de círculos y triángulos

what is mathematics

Question

Tengo un problema interesante aquí que he estado tratando de resolver por el último momento:

Tengo 3 círculos en un plano xy 2D, cada uno con el mismo radio conocido. Conozco las coordenadas de cada uno de los tres centros (son arbitrarios y pueden estar en cualquier lugar).

¿Cuál es el triángulo más grande que se puede dibujar de manera tal que cada vértice del triángulo se asiente en un círculo separado, cuáles son las coordenadas de esas verticales?

He estado viendo este problema durante horas y le he preguntado a un grupo de personas, pero hasta ahora solo una persona ha podido sugerir una solución plausible (aunque no tengo forma de demostrarlo).

La solución que hemos encontrado implica crear primero un triángulo sobre los tres centros circulares. A continuación, observamos cada círculo individualmente y calculamos la ecuación de una línea que pasa por el centro del círculo y es perpendicular al borde opuesto. Luego calculamos dos puntos de intersección del círculo. Esto se hace para los siguientes dos círculos con un resultado de 6 puntos. Recorremos los 8 triángulos posibles de 3 puntos que crean estos 6 puntos (la restricción es que cada punto del triángulo grande debe estar en un círculo separado) y encontrar el tamaño máximo.

Los resultados parecen razonables (al menos cuando están dibujados en un papel) y pasan el caso especial de cuando todos los centros de los círculos caen en una línea recta (da un triángulo más grande conocido). Desafortunadamente no tengo manera de probar que esto sea correcto o no.

Me pregunto si alguien ha encontrado un problema similar a este y, de ser así, ¿cómo lo resolvió?

Nota: entiendo que se trata principalmente de una pregunta matemática y no de programación, sin embargo, se implementará en código y debe optimizarse para ejecutarse de manera muy rápida y eficiente. De hecho, ya tengo la solución anterior en código y he probado que funciona. Si desea echarle un vistazo, hágamelo saber, elegí no publicarlo porque todo está en forma vectorial y es casi imposible descifrarlo. exactamente lo que está pasando (porque se ha condensado para ser más eficiente).

Por último, sí, esto es para el trabajo escolar, aunque NO es una pregunta / tarea / proyecto de tarea. Es parte de mi tesis de posgrado (sobre una parte muy pequeña, pero técnicamente es parte de ella).

Gracias por tu ayuda.

Edit: Heres un nuevo algoritmo que se me ocurrió hace un rato.

Comenzando en el centro de un círculo, traza una línea hacia los otros dos centros. Calcula la línea que divide el ángulo creado y calcula las intersecciones entre el círculo y la línea que pasa por el centro de tu círculo. Obtendrás 2 resultados. Repita esto para los otros dos círculos para obtener un total de 6 puntos. Iterar sobre estos 6 puntos y obtener 8 soluciones posibles. Encuentra el máximo de las 8 soluciones.

Este algoritmo tratará el caso colineal si dibuja sus líneas en una "dirección" sobre los tres puntos.

De los pocos ensayos aleatorios que he intentado usar el software CAD para descubrir las geometrías para mí, este método parece superar a todos los otros métodos indicados anteriormente. Sin embargo, uno de los ejemplos de contador de Victor ya ha demostrado que no es una solución óptima.

Lo codificaré mañana, por alguna razón, he perdido el acceso remoto a la computadora de mi universidad y la mayoría de las cosas están en ella.

Answer 1

Algunos pensamientos iniciales.

1. Definición Llamar el triángulo buscado, el triángulo máximo . Tenga en cuenta que esto podría no ser único: si todos los círculos tienen el mismo centro, entonces hay infinitos triángulos máximos obtenidos por rotación alrededor del centro, y si los centros son colineales, entonces habrá dos triángulos máximos, cada uno de ellos una imagen de espejo del otro.
2. Definición Llama al triángulo (posiblemente, degenerado, ya sea un punto o una línea) cuyos vértices son los centros de los círculos del triángulo interior .
3. Observación La solución se puede expresar en tres ángulos, que indican dónde se encuentra el triángulo en la circunferencia de cada círculo.
4. Observación Dados dos vértices exteriores, podemos determinar un tercer vértice que da el área máxima: dibujar la altitud del triángulo entre los dos vértices exteriores y el centro del otro círculo. Esta línea intersecta la circunferencia en dos lugares; el punto más lejano es la elección maximizadora del tercer vértice. ( Se corrigió un algoritmo incorrecto, el argumento de Federico se puede adaptar para mostrar la exactitud de esta observación )
5. Consecuencia El problema se reduce de un problema en tres ángulos a uno en dos.
6. Conjetura Imagina que el diagrama es un tablero de anuncios, con tres pines en los tres centros de los círculos. Imagine también un bucle cerrado de cadena de longitud igual al perímetro del triángulo interior, más el radio de un círculo, y colocamos este bucle alrededor de los pines. Tome un bolígrafo imaginario y dibuje imaginariamente la figura de bucle donde el bucle está siempre apretado. Supongo que los puntos del triángulo máximo estarán todos en esta figura de bucle, y que en el caso de que el triángulo interior no esté degenerado, los vértices del triángulo máximo serán los tres puntos donde la figura de bucle se interseca con uno del círculo. circunferencias. Muchos contraejemplos

Más para seguir cuando puedo perder tiempo para pensar en ello.

Answer 2

Creo que este es un problema de optimización convexo (no, no lo es, ver más abajo) y, por lo tanto, se puede resolver de manera eficiente utilizando métodos bien conocidos.

Básicamente quieres resolver el problema:

maximize:  area(v1,v2,v3) ~ |cross((v2-v1), (v3-v1))|
such that: v1 in C1, v2 in C2, v3 in C3   (i.e., v_i-c_i)^2 - r_i^2 <= 0)

Cada una de las restricciones es convexa, y la función de área también es convexa. Ahora, no sé si hay una formulación más eficiente, pero al menos se puede usar un método de punto interior con derivados, ya que la derivada del área con respecto a cada posición de vértice puede resolverse analíticamente (lo tengo escrito algun lado...).

Edición: grad (área (v1, v2, v3)) (v_i) = rot90 (vec (vj, vk)), donde vec (a, b) está haciendo un vector 2D que comienza en a y termina en b, y rot90 significa una rotación de orientación positiva de 90 grados, asumiendo que (vi, vj, vk) estaba orientada positivamente.

Edit 2: El problema no es convexo, como debería ser obvio considerando el caso colineal; Dos soluciones degeneradas son un signo seguro de no convexidad. Sin embargo, la configuración que comienza en los centros circulares debe estar en el máximo local óptimo a nivel mundial.

Answer 3

Deje que A, B, C sean los vértices de su triángulo, y suponga que estén colocados como en su solución. Observe que la propiedad clave de su construcción es que cada uno de los vértices se encuentra en una tangente a su círculo que es paralelo al lado opuesto del triángulo. Obviamente, el círculo mismo se encuentra completamente en un lado de la tangente, y en la solución óptima cada tangente deja su círculo en el mismo lado que los otros vértices.

Considere AB como la "base" del triángulo, y deje que C flote en su círculo. Si mueve C a otra posición C ''dentro del círculo, obtendrá otro triángulo ABC'' con la misma base pero una altura menor, por lo tanto, también con un área más pequeña:

figura 1 http://control.ee.ethz.ch/~ramponif/stuff/circles1.png

Por la misma razón, puede ver fácilmente que cualquier posición de los vértices que no sigue su construcción no puede ser óptima. Supongamos, por ejemplo, que cada uno de los vértices A '', B'', C ''no se encuentra en una tangente paralela al lado que conecta los otros dos.

Luego, construyendo la tangente al círculo que contiene (digamos) C '', que es paralelo a A''B'' y deja el círculo en el mismo lado que A''B '', y moviendo C'' al punto de tangencia C, Siempre es posible construir un triángulo A''B''C que tenga la misma base, pero una mayor altura, por lo tanto, también un área mayor:

figura 2 http://control.ee.ethz.ch/~ramponif/stuff/circles2.png

Dado que cualquier triángulo que no siga su construcción no puede ser óptimo, creo que su construcción es óptima. En el caso cuando los centros de los círculos están alineados, estoy un poco confundido, pero supongo que es posible demostrar la optimalidad en la misma línea.

Answer 4

Esto es solo un pensamiento, todavía no hay pruebas ni cálculos que acompañen la construcción. Requiere que los centros del círculo no sean colineales si los radios son los mismos para cada círculo. Esta restricción puede ser relajada si los radios son diferentes.

Construcción:

(1) Construya un triángulo tal que cada lado del triángulo sea tangente a dos círculos, y por lo tanto, cada círculo tenga un punto tangente en dos lados del triángulo.

(2) Dibuja el acorde entre estos dos puntos tangentes en cada círculo

(3) Encuentre el punto en el límite del círculo en el rayo extendido que comienza en el centro del círculo a través del punto medio de la cuerda. Debe haber uno de esos puntos en cada uno de los tres círculos.

(4) Conéctelos tres puntos de (3) para formar un triángulo.

En ese momento no sé si es el triángulo más grande, pero si estás buscando algo aproximado, podría ser este.

Más tarde: es posible que pueda encontrar una respuesta aproximada para el caso degenerado perturbando el círculo "medio" ligeramente en una dirección perpendicular a la línea que conecta los tres círculos.

Answer 5

He creado una aplicación de lienzo HTML5 que puede ser útil para que la gente juegue. Es bastante básico (y el código no es hermoso), pero te permite mover tres círculos de igual radio, y luego calcula un triángulo máximo usando el gradiente / descenso más pronunciado. También puede guardar mapas de bits del diagrama. El diagrama también muestra el triángulo cuyos vértices son los centros circulares y una de las altitudes. Edit1 : la "altitud" es en realidad solo un segmento de línea a través de uno de los centros del círculo y perpendicular al borde opuesto del triángulo que une los centros. Está ahí porque algunas de las construcciones sugeridas lo utilizan. Edit2 : el método de descenso más pronunciado a veces se atasca en un máximo local. Puede salir de ese máximo moviendo un círculo hasta que el triángulo negro se invierta y luego devuelva el círculo a su posición original. Trabajando en cómo encontrar el máximo global.

Esto no funcionará en IE porque no admite el lienzo, pero la mayoría de los otros navegadores "modernos" deberían funcionar.

Hice esto parcialmente porque encontré algunos de los argumentos en esta página cuestionables, y parcialmente porque nunca programé un descenso más pronunciado y quise ver cómo funcionaba. De todos modos, espero que esto ayude, y espero sopesar algunos comentarios más más adelante.

Edit: He examinado un poco más la geometría y he escrito mis conclusiones en una respuesta por separado .

Answer 6

Mi primer pensamiento es que deberías poder encontrar una solución analítica.

Entonces las ecuaciones de los círculos son:

(x1-h1)^2 + (y1-k1)^2 = r^2
(x2-h2)^2 + (y2-k2)^2 = r^2
(x3-h3)^2 + (y3-k3)^2 = r^2

Los vértices de tu triángulo son (x1, y1), (x2, y2) y (x3, y3). Las longitudes laterales de tu triángulo son

A = sqrt((x1-x2)^2 + (y1-y2)^2)
B = sqrt((x1-x3)^2 + (y1-y3)^2)
C = sqrt((x2-x3)^2 + (y2-y3)^2)

Así que el área del triángulo es (usando la fórmula de Heron )

S = (A+B+C)/2
area = sqrt(S(S-A)(S-B)(S-C))

Entonces el área es una función de 6 variables.

En este punto, me doy cuenta de que esta no es una línea de razonamiento fructífera. Esto es más como algo que caería en un sistema de recocido simulado.

Entonces, mi segundo pensamiento es elegir el punto en el círculo con el centro A de la siguiente manera: Construye la línea BC que une los centros de los otros dos círculos, luego construye la línea AD que es perpendicular a BC y pasa a través de A. Un vértice del triángulo es la intersección de AD y el círculo con el centro A. Del mismo modo para los otros vértices. No puedo demostrarlo, pero creo que da resultados diferentes al método simple "más alejado del centro de todos los círculos" y, por alguna razón, me parece mejor. Lo sé, no es muy matemático, pero luego soy programador.

Answer 7

Parece que encontrar el círculo de Apolonio más grande para los tres círculos y luego inscribir un triángulo equilátero en ese círculo sería una solución. Prueba dejada como ejercicio;).

EDITAR

Este método también tiene problemas para los círculos colineales como otras soluciones aquí y no funciona.

Answer 8

Supongamos que el centro de los círculos es C0, C1 y C2; y el radio R.

Como el área de un triángulo es .5 * base * altura, primero encontremos la base máxima que se puede construir con los círculos. Base = Máximo {(| C0-C1 | + 2R), (| C1-C2 | + 2R, (| C2-C0 | + 2R}

Una vez que la longitud de la base se determina entre 2 círculos, podemos encontrar el punto perpendicular más lejano desde la línea de base hasta el tercer círculo. (producto de sus pendientes es -1)

Para casos especiales, como círculos alineados en una sola línea, necesitamos realizar verificaciones adicionales al momento de determinar la línea base.

Answer 9

No óptimo, funciona bien cuando los tres no son colineales:

No tengo una prueba (y, por lo tanto, no sé si se garantiza que sea la más grande). Tal vez voy a trabajar en uno. Pero:

Tenemos tres círculos con radio R con posiciones (desde el centro) P0 , P1 y P2 . Deseamos encontrar los vértices de un triángulo de modo que el área del triángulo sea máxima, y ​​los vértices se encuentren en cualquier punto de los bordes de los círculos.

Encuentra el centro de todos los círculos y llama a eso C. Entonces C = (P0 + P1 + P2) / 3 . Luego encontramos el punto en cada círculo más alejado de C.

Encuentre los vectores V0 , V1 y V2 , donde V _i = P _i - C. Luego encuentre los puntos Q0 , Q1 y Q2 , donde Q _i = norma (V _i ) * R + P _i . Donde norma indica normalización de un vector, norma (V) = V / | V | .

Q0 , Q1 y Q2 son los vértices del triángulo. Supongo que esto es óptimo porque es lo más lejos que podrían estar los vértices entre sí. (Yo creo que.)

Answer 10

Me he tomado la libertad de enviar una segunda respuesta, porque mi respuesta original se refería a una aplicación en línea que la gente podía jugar para obtener información. La respuesta aquí es más un argumento geométrico.

El siguiente diagrama ilumina, espero, lo que está pasando. Gran parte de esto se inspiró en la observación de @Federico Ramponi de que el triángulo más grande se caracteriza porque la tangente en cada vértice es paralela al lado opuesto.

La imagen se produjo utilizando una versión de prueba del excelente programa de escritorio Geometry Expressions . El diagrama muestra los tres círculos centrados en los puntos A , E y C Tienen radios iguales, pero la imagen realmente no depende de que los radios sean iguales, por lo que la solución se generaliza a círculos de diferentes radios. Las líneas MN , NO y OM son tangentes a los círculos y tocan los círculos en los puntos I , H y G respectivamente. Los últimos puntos forman el triángulo interior IHG que es el triángulo cuyo tamaño queremos maximizar.

También hay un triángulo exterior MNO que es hometético al triángulo interior, lo que significa que sus lados son paralelos a los de IHG .

@Federico observó que IHG tiene un área máxima porque mover cualquiera de sus vértices a lo largo del círculo correspondiente resultará en un triángulo que tiene la misma base pero menos altura, por lo tanto, menos área. Para ponerlo en términos ligeramente más técnicos, si el triángulo está parametrizado por los ángulos t1 , t2 , t3 en los tres círculos (como lo señaló @Charles Stewart, y como se usa en mi aplicación de lienzo de pendiente más pronunciada), el gradiente de el área wrt to (t1,t2,t3) es (0,0,0) , y el área es extremal (máximo en el diagrama).

Entonces, ¿cómo se calcula este diagrama? Admito de antemano que no tengo la historia completa, pero he aquí un comienzo. Dados los tres círculos, seleccione un punto M Dibuje tangentes a los círculos centrados en E y C , y designe los puntos tangentes como G e I Dibuje una OHN tangente al círculo centrado en A que es paralelo a GI . Estas son operaciones bastante simples tanto algebraicamente como geométricamente.

Pero no hemos terminado. Hasta ahora solo tenemos la condición de que OHN es paralelo a GI . No tenemos garantía de que MGO sea ​​paralelo a IH o que MIN sea ​​paralelo a GH . Así que tenemos que volver y refinar M En un programa de geometría interactiva no es gran cosa configurar esto y luego mover M hasta que se cumplan las últimas condiciones paralelas (de todos modos). Geometry Expressions creó el diagrama, pero utilicé un poco de trampa para hacerlo, porque su solucionador de restricciones aparentemente no era lo suficientemente poderoso como para hacer el trabajo. Las expresiones algebraicas para G , I y H son razonablemente directas, por lo que debería ser posible resolver para M basado en el hecho de que MIHG es un paralelogramo, ya sea explícita o numéricamente.

Debo señalar que, en general, si sigue la construcción a partir de M , tiene dos opciones de tangente para cada círculo y, por lo tanto, ocho soluciones posibles. Al igual que en el otro intento de respuestas a la pregunta, a menos que tenga una buena heurística para ayudarlo a elegir de antemano cuál de las tangentes debe calcular, probablemente debería calcular los ocho triángulos posibles y encontrar el que tenga el área máxima. Los otros siete serán extremos en el sentido de ser un área mínima o puntos de silla de montar.

Eso es. Esta respuesta no es del todo completa, ya que deja el cálculo final de M algo abierto. Pero se reduce a un espacio de búsqueda 2D o a la solución de una ecuación intrincada pero no gigantesca.

Finalmente, no estoy de acuerdo con la conclusión de @Federico de que esto confirma que la solución propuesta por el OP es óptima. Es cierto que si dibuja perpendiculares desde los centros del círculo hasta el borde opuesto del triángulo interior, esos perpendiculares se intersecan con el círculo para darle el vértice del triángulo. Por ejemplo, H encuentra en la línea a través de A perpendicular a GI ), pero esto no es lo mismo que en la solución original propuesta (que era tomar la línea a través de A y perpendicular a EC , en general EC no es paralela a GI ).