Menos cuadrado círculo a través de la iteración de punto fijo

Question

Tiene una colección de 2d puntos que desea para que se ajuste a un círculo. Formulario de la suma de los cuadrados de las distancias de los puntos a una genérica círculo. Las variables son las $x,y$ coordenadas del centro y el radio. Establecer el gradiente de 0, entonces una ecuación que da la radio como el promedio de la distancia desde el centro a los puntos. Para un punto dado,$C$, vamos a $r(C)$ el valor de la distancia promedio de $C$ a los puntos. El uso de las otras dos ecuaciones, encontramos el centro es un punto fijo de la asignación de $T(C)$, que se define de la siguiente manera:

A partir de cada punto, de viaje hacia la $C$ a pie $r(C)$, y luego el promedio de todos estos desplazado puntos para conseguir $T(C)$.

La asignación no está bien definida en los puntos. Es posible que en algunos arreglos de puntos y un punto de partida $C_0$ para la iteración de punto fijo $C_{n+1}=T(C_n)$ a tierra en uno de los puntos de ajuste. Con esto en mente, estoy tratando de encontrar un conjunto en el que $T$ es una contracción. Intuitivamente, podríamos tomar discos centrado en cada punto de ajuste, y hacerlos crecer de manera uniforme hasta que todos se cruzan en un conjunto no vacío, tal vez dejar que los discos de crecer un poco más, y suponiendo que la intersección no contiene cualquiera de los puntos de ajuste, esto debe servir como un buen candidato que probar $T$ es una contracción. De hecho, es fácil ver que el desplazado puntos permanecerán en sus respectivos discos sobre cada punto de ajuste, pero no es del todo claro que $T(C)$, el promedio de la cambió puntos, se encuentran en cada disco, pero tiene que estar cerca! Tenga en cuenta que la intersección de los discos es un compacto y convexo conjunto, y $T$ es continua, por lo que he Brouwer teorema de punto fijo en la mente.

Alguna idea de cómo elegir el Conjunto? Es la intersección he descrito bien? Simplemente no puedo imaginar una prueba. He probado el problema bastante bien en un equipo y la convergencia de la iteración de punto fijo parece que es bastante fiable de la elección de $C_0$ como promedio de los puntos.

En general, no creo que la unicidad, supongamos que sólo hay 1 o 2 puntos distintos, entonces hay infinitamente muchos círculos de ajustar los puntos exactamente. También tenga en cuenta que si los puntos están distribuidos en un pequeño arco del círculo, el promedio de los puntos es bastante lejos del centro, sin embargo, la convergencia se observa, aunque muy lentamente.

Editar Me pidieron fórmulas, así que le doy $T(C) = \frac{1}{n}\sum_{i=1}^n (P_i + r(C)\frac{C-P_i}{|C-P_i|})$ donde $r(C) = \frac{1}{n}\sum_{i=1}^n |C-P_i|$. Y queremos encontrar a $C$ tal que $T(C)=C$. Sólo necesito un set que $T$ de los mapas en sí mismo.

Answer 1

Hay una muy extenso cuerpo de literatura sobre este problema. Aparte del interés teórico, existe un importante problema práctico. Cuando las piezas son inspeccionadas por la calidad, tienes un montón de puntos a partir de una máquina de medición de coordenadas. A menudo se desea ajuste círculos a estos puntos, para estimar los tamaños de los agujeros, los diámetros de los ejes, etc.

Para numerosos artículos y un libro sobre el tema, mira aquí.

Answer 2

Probablemente no es una respuesta a la pregunta, pero demasiado largo para un comentario.

Suponiendo que usted ha $n$ puntos de datos $(x_i,y_i)$ y desea que el "mejor" círculo de radio $r$ centrada en $(a,b)$, es necesario minimizar $$SSQ(a,b,r)=\sum_{i=1}^n \left(r-\sqrt{(x_i-a)^2+(y_i-b)^2} \right)^2$ $ , que es un altamente no lineales del problema. Cualquier método de minimización de la haría siempre goo estimaciones.

Para obtener estas estimaciones, en un paso preliminar, se puede escribir $$f_i=(x_i-a)^2+(y_i-b)^2-r^2$$ and now consider all the $\frac {n(n-1)}2$ ecuaciones $$g_{ij}=f_j-f_i=2a(x_i-x_j)+2b(y_i-y_j)+\left((x_j^2-x_i^2)+(y_j^2-y_i^2)\right)$$ A linear regression (or matrix calculation) based on these $\frac {n(n-1)}2$ data points will provide $un$ and $b$. Using them would give as an estimate $$r=\frac 1n \sum_{i=1}^n \sqrt{(x_i-a)^2+(y_i-b)^2}\tag 1$$ Ahora, usted tiene todos los elementos para iniciar la optimización. Incluso se podría usar de Newton-Raphson método para resolver $$\frac{\partial SSQ}{\partial a}=\frac{\partial SSQ}{\partial b}=\frac{\partial SSQ}{\partial r}=0$ $ , que se reducen a $$\frac{\partial SSQ}{\partial a}=\sum_{i=1}^n \frac{(x_i-a) \left(r-\sqrt{(x_i-a)^2+(y_i-b)^2}\right)}{\sqrt{(x_i-a)^2+(y_i-b)^2}}=0\tag 2$$ $$\frac{\partial SSQ}{\partial b}=\sum_{i=1}^n \frac{(y_i-b) \left(r-\sqrt{(x_i-a)^2+(y_i-b)^2}\right)}{\sqrt{(x_i-a)^2+(y_i-b)^2}}=0\tag 3$$ $$\frac{\partial SSQ}{\partial r}=\sum_{i=1}^n \left(r-\sqrt{(x_i-a)^2+(y_i-b)^2}\right)=0\tag 4$$ The solution of $(4)$ is already given by $(1)$; so, you are left with two nonlinear equations in $(a,b)$.

Si eres tan perezoso como yo soy, el uso numéricos derivados.