Circunferencia que se ajusta a una serie de puntos
Tengo un problema con el que espero que puedas ayudarme, porque he buscado en internet por bastantes sitios, pero no encuentro la solución (de hecho, no sé bien ya ni cómo buscarlo xD ).
Verás, tengo una serie de puntos (que no siempre van a ser los mismos ni la misma cantidad, es para un programa de ordenador) y necesito calcular la circunferencia (en realidad, la hemicircunferencia) que mejor se ajuste a estos puntos.
Los puntos marcan una nube de puntos en unos casos (que me delimita la zona donde tengo que dibujar la circunferencia), y el contorno de esta zona en otros casos.
Yo creo que serían, por lo tanto, dos problemas distintos:
- Caso de que tenga la nube de puntos: calculo de la ecuación de la circunferencia que mejor se ajuste a los mismos, que no sé cómo calcularla. A partir de esa fórmula, calcular la hemicircunferencia.
- Caso de que tenga la delimitación del contorno: calculo de la ecuación de la circunferencia que mejor se ajuste a la zona que delimitan estos puntos, que tampoco se me ocurre cómo calcularla. A partir de esa fórmula, calcular la hemicircunferencia.
No sé si me he explicado bien. Si necesitas más información, dímelo. Espero que puedas darme alguna idea, porque no se me ocurre cómo plantear el problema y llevo ya bastante tiempo dándole vueltas.
Verás, tengo una serie de puntos (que no siempre van a ser los mismos ni la misma cantidad, es para un programa de ordenador) y necesito calcular la circunferencia (en realidad, la hemicircunferencia) que mejor se ajuste a estos puntos.
Los puntos marcan una nube de puntos en unos casos (que me delimita la zona donde tengo que dibujar la circunferencia), y el contorno de esta zona en otros casos.
Yo creo que serían, por lo tanto, dos problemas distintos:
- Caso de que tenga la nube de puntos: calculo de la ecuación de la circunferencia que mejor se ajuste a los mismos, que no sé cómo calcularla. A partir de esa fórmula, calcular la hemicircunferencia.
- Caso de que tenga la delimitación del contorno: calculo de la ecuación de la circunferencia que mejor se ajuste a la zona que delimitan estos puntos, que tampoco se me ocurre cómo calcularla. A partir de esa fórmula, calcular la hemicircunferencia.
No sé si me he explicado bien. Si necesitas más información, dímelo. Espero que puedas darme alguna idea, porque no se me ocurre cómo plantear el problema y llevo ya bastante tiempo dándole vueltas.
2 Respuestas
Respuesta de Fran José García
1
La verdad es que he estado esta mañana dándole vueltas y va a estar la cosa difícil. El método de los mínimos cuadrados no se puede aplicar ya que la ecuación de la circunferencia no es lineal. Así que ese descartado. Esto va a estar difícil.
Una solución que se me ocurre es la siguiente, tenemos que averiguar que parámetros de la siguiente función se ajustan mejor.
y = raiz(r^2 - (x - a)^2)+b
Ahora a y b, representan el centro de la circunferencia (a, b).
Estos los podemos estimar por el centro de gravedad de nuestra nube de puntos, imaginate que tenemos una muestra de datos de dos variables (X, Y), pues el punto estimado (a, b) lo calculamos como (Media(A), Media(Y)), ahora debemos calcular la distancia de todos los puntos a ese centro de gravedad y entonces la distancia media será el radio de la circunferencia, también se puede comprobar con la mediana a ver si el ajuste es mejor, esto lo puedes comprobar viendo el residuo del ajuste y tus datos reales. Puedes hacer una simulación de unos datos a ver si te sale.
Bueno he hecho una comprobación y el problema del centro de gravedad seleccionado es que el punto a lo calcula bien, sin problema, pero el punto b no se calcula bien, entonces a estimación final puede quedar como
est(a) = media(X)
est(b) = media(y) - est(r)
Donde est(·), significa estimación., así realiza un ajuste bueno, lo he probado para datos que describen perfectamente una circunferencia y ha funcionado bien, pero no se si es el ajuste con menor error. De todas formas echale un vistazo al link siguiente a ver que te sale, si sabes matlab te servirá para hacerlo
http://webdiis.unizar.es/~jdtardos/cdocSPR/P4.pdf
Una solución que se me ocurre es la siguiente, tenemos que averiguar que parámetros de la siguiente función se ajustan mejor.
y = raiz(r^2 - (x - a)^2)+b
Ahora a y b, representan el centro de la circunferencia (a, b).
Estos los podemos estimar por el centro de gravedad de nuestra nube de puntos, imaginate que tenemos una muestra de datos de dos variables (X, Y), pues el punto estimado (a, b) lo calculamos como (Media(A), Media(Y)), ahora debemos calcular la distancia de todos los puntos a ese centro de gravedad y entonces la distancia media será el radio de la circunferencia, también se puede comprobar con la mediana a ver si el ajuste es mejor, esto lo puedes comprobar viendo el residuo del ajuste y tus datos reales. Puedes hacer una simulación de unos datos a ver si te sale.
Bueno he hecho una comprobación y el problema del centro de gravedad seleccionado es que el punto a lo calcula bien, sin problema, pero el punto b no se calcula bien, entonces a estimación final puede quedar como
est(a) = media(X)
est(b) = media(y) - est(r)
Donde est(·), significa estimación., así realiza un ajuste bueno, lo he probado para datos que describen perfectamente una circunferencia y ha funcionado bien, pero no se si es el ajuste con menor error. De todas formas echale un vistazo al link siguiente a ver que te sale, si sabes matlab te servirá para hacerlo
http://webdiis.unizar.es/~jdtardos/cdocSPR/P4.pdf
Hola:
Muchísimas gracias por tu solución. No he conseguido que me salga totalmente bien, pero, al menos, se parece a una circunferencia.
Te cuento: obtengo la ecuación de la circunferencia como me dices (ahora mismo estoy probando con la media, cuando lo consiga, probaré con la mediana como me comentas), pero hay algo que no va. El resultado que obtengo son dos hemicircunferencias ligeramente separadas (una un poco por encima del centro y otra un poco por debajo).
Creo que he seguido bien los pasos que me indicabas, pero puedo estar confundiéndome en algún sitio. Te pongo aquí paso a paso lo que estoy haciendo, a ver si ves tú dónde estoy metiendo la pata:
1- Calculo el centro de la circunferencia. Para ello, a=media de las coordenadas POR de todos los puntos, y b=media de las coordenadas Y de todos los puntos.
- La media la calculo (a ver si me voy a estar equivocando en alguna de estas cosas básicas) como la suma de todas las POR dividido por el número de puntos (igual para las Y).
2- Calculo la distancia de cada punto de la nube al centro de la circunferencia.
- La distancia de cada punto la calculo como: raíz((a-coordenada_x_del_punto)^2+(b-coordenada_y_del_punto)^2)
3- El radio de la circunferencia lo calculo como la distancia media de todos los puntos al centro de la circunferencia.
- Para calcular la distancia media, sumo todas las distancias calculadas en el paso previo, y divido el resultado de la suma por el número de puntos.
¿4?- A este punto le pongo una interrogación porque sí que tengo serias dudas sobre lo que estoy haciendo. Tú me comentabas que la coordenada b del centro se calculaba con un error, y que para que fuera la adecuada debía restarle el radio que había calculado. Pero si hago eso, la circunferencia se me desplaza demasiado con respecto a la nube de puntos que uso. Entonces, cuando hago lo que me decías, lo que hago es coger la coordenada b calculada en el paso 1 y le resto el radio calculado en el punto 3. ¿Es a esto a lo que te referías cuando me explicabas el desajuste que aparecía en b o te he entendido mal?
5- Calculo puntos de la circunferencia para dibujarla. Para ello, cojo la por mayor y menor del área donde voy a dibujar la circunferencia calculada (es decir, la mayor y menor POR de la nube de puntos), y para cada una de esas POR intermedias (entre la mínima y la máxima), calculo la Y correspondiente, según la ecuación de la circunferencia que tú me indicabas más arriba: Y=raíz (r^2-((x-a)^2))+b. Con esto calculo sólo la mitad de la circunferencia. Para dibujarla entera, marco ese punto y otro con la misma x pero con la y=y_calculada-2*valor_absoluto(b-y_calculada), siendo y_calculada la que he usado en el punto con la misma X de la otra hemicircunferencia.
Nota: Como nube de puntos, ahora mismo y para simplificar, uso un contorno cerrado que yo marco con el pincel en el programa con la forma aproximada de una circunferencia (todo lo aproximada que me permite mi pulso :) ).
Sobre Matlab, lo traté ligeramente hace mucho tiempo, pero ahora ni lo tengo instalado ni me acuerdo de él. Yo estoy usando Visual Studio 2005, programo en C++, pero no te preocupes por eso. En cuanto logre resolver el problema matemático, la programación será pan comido :)
Necesito un par de aclaraciones adicionales sobre tu contestación:
- Cuando hablas del residuo del ajuste, ¿a qué te refieres? ¿A la diferencia o error entre la circunferencia calculada y la nube de puntos?
- Cuando hablas de la estimación de r, te refieres al r calculado de la forma que me explicas, ¿no? Lo que no entiendo exactamente es, ¿r y est(r) es lo mismo?
Eso es todo. Perdona por escribirte tanto, pero es que soy incapaz de resolverlo sin ayuda.
Muchísimas gracias por tu ayuda y tu interés. Un saludo.
Muchísimas gracias por tu solución. No he conseguido que me salga totalmente bien, pero, al menos, se parece a una circunferencia.
Te cuento: obtengo la ecuación de la circunferencia como me dices (ahora mismo estoy probando con la media, cuando lo consiga, probaré con la mediana como me comentas), pero hay algo que no va. El resultado que obtengo son dos hemicircunferencias ligeramente separadas (una un poco por encima del centro y otra un poco por debajo).
Creo que he seguido bien los pasos que me indicabas, pero puedo estar confundiéndome en algún sitio. Te pongo aquí paso a paso lo que estoy haciendo, a ver si ves tú dónde estoy metiendo la pata:
1- Calculo el centro de la circunferencia. Para ello, a=media de las coordenadas POR de todos los puntos, y b=media de las coordenadas Y de todos los puntos.
- La media la calculo (a ver si me voy a estar equivocando en alguna de estas cosas básicas) como la suma de todas las POR dividido por el número de puntos (igual para las Y).
2- Calculo la distancia de cada punto de la nube al centro de la circunferencia.
- La distancia de cada punto la calculo como: raíz((a-coordenada_x_del_punto)^2+(b-coordenada_y_del_punto)^2)
3- El radio de la circunferencia lo calculo como la distancia media de todos los puntos al centro de la circunferencia.
- Para calcular la distancia media, sumo todas las distancias calculadas en el paso previo, y divido el resultado de la suma por el número de puntos.
¿4?- A este punto le pongo una interrogación porque sí que tengo serias dudas sobre lo que estoy haciendo. Tú me comentabas que la coordenada b del centro se calculaba con un error, y que para que fuera la adecuada debía restarle el radio que había calculado. Pero si hago eso, la circunferencia se me desplaza demasiado con respecto a la nube de puntos que uso. Entonces, cuando hago lo que me decías, lo que hago es coger la coordenada b calculada en el paso 1 y le resto el radio calculado en el punto 3. ¿Es a esto a lo que te referías cuando me explicabas el desajuste que aparecía en b o te he entendido mal?
5- Calculo puntos de la circunferencia para dibujarla. Para ello, cojo la por mayor y menor del área donde voy a dibujar la circunferencia calculada (es decir, la mayor y menor POR de la nube de puntos), y para cada una de esas POR intermedias (entre la mínima y la máxima), calculo la Y correspondiente, según la ecuación de la circunferencia que tú me indicabas más arriba: Y=raíz (r^2-((x-a)^2))+b. Con esto calculo sólo la mitad de la circunferencia. Para dibujarla entera, marco ese punto y otro con la misma x pero con la y=y_calculada-2*valor_absoluto(b-y_calculada), siendo y_calculada la que he usado en el punto con la misma X de la otra hemicircunferencia.
Nota: Como nube de puntos, ahora mismo y para simplificar, uso un contorno cerrado que yo marco con el pincel en el programa con la forma aproximada de una circunferencia (todo lo aproximada que me permite mi pulso :) ).
Sobre Matlab, lo traté ligeramente hace mucho tiempo, pero ahora ni lo tengo instalado ni me acuerdo de él. Yo estoy usando Visual Studio 2005, programo en C++, pero no te preocupes por eso. En cuanto logre resolver el problema matemático, la programación será pan comido :)
Necesito un par de aclaraciones adicionales sobre tu contestación:
- Cuando hablas del residuo del ajuste, ¿a qué te refieres? ¿A la diferencia o error entre la circunferencia calculada y la nube de puntos?
- Cuando hablas de la estimación de r, te refieres al r calculado de la forma que me explicas, ¿no? Lo que no entiendo exactamente es, ¿r y est(r) es lo mismo?
Eso es todo. Perdona por escribirte tanto, pero es que soy incapaz de resolverlo sin ayuda.
Muchísimas gracias por tu ayuda y tu interés. Un saludo.
El residuo es lo que dices la diferencia del ajuste con los valores reales observados.
R es el valor real (que desconocemos) y est(r) o r estimado es la estimación que tu has realizado
R es el valor real (que desconocemos) y est(r) o r estimado es la estimación que tu has realizado
Respuesta de pollux_troy
1
Sin datos no puedo sacar ecuaciones...
Es que los puntos exactos no los tengo a priori, como es un programa, serían los que el usuario marque. Por eso no necesito una ecuación en particular, sino la forma de calcular la ecuación, no sé si me estoy explicando... Me refiero a si hay algún método para calcular la circunferencia que mejor se ajusta a una serie de puntos cualquiera. Es que yo tengo que programar una función que tenga como entrada los puntos que me marque quien use el programa y yo dibujo en pantalla la circunferencia, para lo que necesito la ecuación de la misma.
Lo único que sé a priori de los datos es que son valores enteros y positivos, no sé si eso puede simplificar de algún modo la solución del problema...
Si no, si conoces cómo hacerlo teniendo los puntos, pues supongamos que tenemos una serie de puntos, 20, por ejemplo, con dos coordenadas cada uno (es un problema en 2 dimensiones):
x=3, y=3; x=2, y=3; x=1, y=4; x=1, y=5; x=3, y=5; x=2, y=8; x=4, y=7; x=4, y=9; x=5, y=9; x=6, y=8; x=7, y=8; x=7, y=10; x=9, y=7; x=8, y=10; x=9, y=9; x=9, y=6; x=10, y=3; x=10, y=5; x=8, y=6; x=9, y=3;
Si me sabes explicar cómo resolver ese ejemplo, luego yo intento abstraerlo. Los datos que ahí te doy los he cogido yo más o menos al azar, podrían ser otros cualesquiera, y normalmente, serán muchos más de 20, pero como ejemplo, espero que sirva.
Si necesitas otros datos, no dudes en pedírmelos para que intente dártelos.
Muchísimas gracias por cualquier ayuda que puedas prestarme. Un saludo.
Lo único que sé a priori de los datos es que son valores enteros y positivos, no sé si eso puede simplificar de algún modo la solución del problema...
Si no, si conoces cómo hacerlo teniendo los puntos, pues supongamos que tenemos una serie de puntos, 20, por ejemplo, con dos coordenadas cada uno (es un problema en 2 dimensiones):
x=3, y=3; x=2, y=3; x=1, y=4; x=1, y=5; x=3, y=5; x=2, y=8; x=4, y=7; x=4, y=9; x=5, y=9; x=6, y=8; x=7, y=8; x=7, y=10; x=9, y=7; x=8, y=10; x=9, y=9; x=9, y=6; x=10, y=3; x=10, y=5; x=8, y=6; x=9, y=3;
Si me sabes explicar cómo resolver ese ejemplo, luego yo intento abstraerlo. Los datos que ahí te doy los he cogido yo más o menos al azar, podrían ser otros cualesquiera, y normalmente, serán muchos más de 20, pero como ejemplo, espero que sirva.
Si necesitas otros datos, no dudes en pedírmelos para que intente dártelos.
Muchísimas gracias por cualquier ayuda que puedas prestarme. Un saludo.
Ehm, con tal cantidad de puntos es muy, pero muy complicado resolverlo a mano y asemejarlo a la mejor circunsferencia, pues queda muy al criterio de quien lo resuelve... es poco objetivo lo que solicitas...
Ademas, es en extremo complejo por el gran numero de datos, pues para determinarlo es necesario colocar los datos en un plano cartesiano y elegir alguna circinsferencia que se asemeje...
En resumidas cuentas es complejo a cabalidad para un simple mortal...
Ademas, es en extremo complejo por el gran numero de datos, pues para determinarlo es necesario colocar los datos en un plano cartesiano y elegir alguna circinsferencia que se asemeje...
En resumidas cuentas es complejo a cabalidad para un simple mortal...
Claro, ya lo imaginaba, por eso es un problema para resolver con un ordenador, pero si no conozco el método, cómo se hace, no puedo programarlo. ¿Conoces alguna página o algo donde se explique un poco las operaciones o la forma para, partiendo de esos datos, obtener la circunferencia? ¿Algo qué me ayude un poco a guiarme? Es que, por lo que he estado viendo en internet, el problema de encontrar la línea recta que mejor se ajusta a una nube de puntos se denomina regresión lineal, pero el ajuste a una circunferencia no encuentro ni cómo se llama, por lo que no puedo buscar con exactitud por internet. ¿Sabes cómo se denomina exactamente el problema a ver si encuentro algo?
Muchas gracias por tu interés y un saludo.
Muchas gracias por tu interés y un saludo.
No compa... ni idea de como se llama el procedimiento ni de donde buscarlo... toda la información que respondo proviene casi unicamente de mis conocimientos... siento no poder ayudarte...