¿Qué método (o algoritmo) puedo usar para ajustar un círculo desde muchos puntos tridimensionales en los que hay algunos puntos de ruido para que pueda obtener su centro (x, y, z) y su radio?

Answer 1

Descargo de responsabilidad: nunca he intentado esto, pero espero que funcione. También puede haber estrategias más eficientes / precisas por ahí.

Aproximar el punto central:
Calcule el @Centroid de todos los puntos. Por ejemplo, el valor [matemático] x [/ matemático] del centroide será el promedio de todos los valores de los puntos [matemático] x [/ matemático]. Sin ningún ruido, el centroide será el punto central; de lo contrario, solo será una aproximación.

Aproximar el radio:
Elija varios puntos y calcule su distancia al centroide. Promedia esas distancias y úsala como el radio inicial.

Sintonia FINA:
Si necesita una mayor precisión, puede hacer pequeños cambios de forma iterativa para obtener mejores resultados cada vez. Suponga que observa que aproximadamente la mitad de los puntos están dentro de la esfera y la otra mitad está afuera, pero todos los puntos internos están agrupados en un lado de la esfera. En ese caso, puede alejar el punto central del clúster hasta que todo esté más equilibrado. Del mismo modo, si la mayoría de los puntos estuvieran fuera de la esfera, podría intentar aumentar el radio.

El proceso de ajuste fino recuerda al algoritmo de escalada @Hill, excepto que las ideas geométricas ayudan a sesgar el próximo movimiento para obtener resultados más rápidos. Probablemente sea seguro asumir que hay un mejor punto central, un mejor radio, y las mejoras en la esfera a través de pequeños ajustes a cualquiera de las variables siempre lo acercan al óptimo. Por supuesto, demasiados puntos ruidosos con suficiente estructura podrían cambiar eso. Normalmente, sin embargo, habrá un máximo local y será el mismo que el máximo global, que es la situación ideal para la optimización iterativa.

Answer 2

En primer lugar, método y algoritmo son lo mismo. Además, si sus puntos están en 3 dimensiones, está buscando una esfera, no un círculo.

Ahora hablemos de tu problema. Tienes puntos en 3 dimensiones y quieres encontrar la esfera que los incluye a todos. O tal vez no todo, ya que menciona el ruido, por lo tanto, algunos puntos podrían estar fuera de la esfera. Por lo tanto, deberá definir un margen de error usted mismo. Eso sintoniza la solución. Tenga en cuenta que esta variable también puede afectar la complejidad del problema, haciendo que el cálculo sea muy rápido o muy lento.

Por lo tanto, debe encontrar el punto a la misma distancia de todos (o la mayoría) de los otros puntos. Con ese fin:

1. Deberá calcular el área que cubre todos los puntos
2. Encuentra el punto central de esa área
3. Decida un radio que conforma su esfera, teniendo en cuenta el margen de error

Para la primera parte, hay algunos algoritmos disponibles en el campo de la geometría algorítmica; El problema general se llama casco convexo o cubierta convexa y es un área de investigación activa.

Solo he tratado este problema durante un semestre como estudiante, por lo que solo puedo aconsejar dónde buscar más. Aquí hay algunos enlaces:

• Casco convexo
• Algoritmos de casco convexo
• Triangulación de Delaunay

Entonces necesitarás encontrar el centro de ese objeto 3D. Echa un vistazo a:
Centroide

Una vez que tenga ese centro, solo necesita calcular un radio satisfactorio que cubra la cantidad de puntos que desea.

Finalmente, si los puntos de ruido son realmente valores atípicos, es decir, demasiado lejos de la concentración principal de puntos, puede usar el análisis de regresión para calcularlos y excluirlos:
Parte aislada

Answer 3

Puede plantear esto como un problema de optimización.

Primero veamos cómo estimar el centro. El centro de un círculo tiene la propiedad de estar a la misma distancia de todos los puntos del círculo. Sin embargo, debido a que tiene puntos ruidosos, no puede encontrar un punto central que esté exactamente a la misma distancia de todos los puntos. Sin embargo, puede relajar ese requisito estricto y encontrar el punto lo más cerca posible de todos los demás puntos del círculo. Concretamente, definamos el centro de un círculo (ruidoso) como el punto [matemático] c [/ matemático] con una distancia promedio mínima a todos los demás puntos. La distancia promedio (al cuadrado) de un conjunto de puntos ruidosos a un centro candidato [matemática] c [/ matemática] viene dada por

avgDistCenter [math] (c) = \ dfrac {1} {n} \ sum_ {i = 1} ^ n \ left (p_i – c \ right) ^ 2 [/ math]

donde [math] n [/ math] es el número de puntos ruidosos en su conjunto [math] P = \ {p_1, \ ldots, p_n \} [/ math] de puntos. Tenga en cuenta que esta ecuación en realidad mide distancias cuadradas promedio, en lugar de distancias medias. Esta es una forma más conveniente porque nos permite eliminar una operación de raíz cuadrada, lo que habría complicado el problema de optimización. Esto está bien porque el centro con una distancia cuadrática promedio mínima a todos los puntos es también el que tiene una distancia promedio mínima.

Para encontrar el centro óptimo de un círculo, entonces, necesitamos identificar el punto [matemática] c [/ matemática] con una distancia cuadrática promedio mínima a todos los puntos ruidosos:

[matemáticas] \ min_c [/ matemáticas] avgDistCenter [matemáticas] (c) [/ matemáticas]

Este problema de optimización se puede resolver mediante la técnica estándar de establecer el gradiente de la función avgDistCenter (con respecto a su parámetro [math] c [/ math]) a cero:

[math] \ dfrac {d} {dc} [/ math] avgDistCenter [math] (c) = \ dfrac {-2} {n} \ sum_ {i = 1} ^ n (p_i – c) = 0 [/ matemáticas]
[math] \ Rightarrow \ sum_ {i = 1} ^ n p_i – \ sum_ {i = 1} ^ nc = 0 [/ math]

Entonces,

[math] \ sum_ {i = 1} ^ n p_i = cn \ Rightarrow c = \ dfrac {1} {n} \ sum_ {i = 1} ^ n p_i = [/ math] Avg [math] [P] [ /matemáticas]

El centro óptimo, entonces, es solo el promedio de todos sus puntos ruidosos.

El radio [matemática] r [/ matemática] del círculo se puede encontrar de manera similar. Tenga en cuenta que, dado que sus puntos son ruidosos, cada uno de ellos estará a una distancia ligeramente diferente (al cuadrado) del centro [matemáticas] c [/ matemáticas] estimado anteriormente. Definamos [math] \ epsilon_i [/ ​​math] como la distancia al cuadrado de un punto dado [math] p_i [/ ​​math] al centro [math] c [/ math] de un círculo:

[matemáticas] \ epsilon_i = (p_i – c) ^ 2 [/ matemáticas]

El radio óptimo [matemática] r [/ matemática] es el que es lo más similar posible a la distancia promedio de sus puntos ruidosos al verdadero centro [matemática] c [/ matemática] del círculo:

[matemáticas] \ min_r \ dfrac {1} {n} \ sum_ {i = 1} ^ n \ left (\ epsilon_i – r ^ 2 \ right) ^ 2 [/ math]

Aquí usamos [math] r ^ 2 [/ math] (radio al cuadrado), en lugar de [math] r [/ math], porque [math] \ epsilon_i [/ ​​math] es una distancia al cuadrado. Este problema de minimización puede resolverse nuevamente estableciendo el gradiente de la función de optimización (con respecto a su parámetro [math] r [/ math]) a cero:

[matemáticas] \ dfrac {d} {dr} \ dfrac {1} {n} \ sum_ {i = 1} ^ n (\ epsilon_i-r ^ 2) ^ 2 = 0 [/ matemáticas]

[matemáticas] \ Rightarrow \ dfrac {2} {n} \ sum_ {i = 1} ^ n (\ epsilon_i-r ^ 2) \ dfrac {d} {dr} (\ epsilon_i-r ^ 2) = 0 [/ matemáticas]

Entonces,

[matemáticas] \ sum_ {i = 1} ^ n (\ epsilon_i – r ^ 2) (-2r) = 0 [/ matemáticas]
[math] \ Rightarrow -2r \ times \ sum_ {i = 1} ^ n (\ epsilon_i – r ^ 2) = 0 [/ math]

Esto tiene una solución trivial en [math] r = 0 [/ math], que ignoramos; la solución no trivial viene dada por

[matemática] \ sum_ {i = 1} ^ n (\ epsilon_i – r ^ 2) = 0 \ Rightarrow nr ^ 2 = \ sum_ {i = 1} ^ n \ epsilon_i [/ ​​math]

Sustituyendo la definición de [math] \ epsilon_i [/ ​​math] y del centro óptimo [math] c [/ math] da

[matemática] \ Rightarrow r ^ 2 = \ dfrac {1} {n} \ sum_ {i = 1} ^ n (p_i – c) ^ 2 = \ dfrac {1} {n} \ sum_ {i = 1} ^ n (p_i – [/ math] Avg [math] [P]) ^ 2 [/ math]
[matemática] \ Rightarrow r ^ 2 = [/ math] Var [matemática] [P] \ Rightarrow r = [/ math] Std [matemática] [P] [/ math]

En otras palabras, dado un conjunto P de puntos extraídos de un círculo ruidoso:

• la mejor estimación para el verdadero centro del círculo es la media de los puntos;
• La mejor estimación del radio del círculo es la desviación estándar de los puntos.

Answer 4

Para conjuntos de datos ruidosos, los métodos de mínimos cuadrados representan un buen enfoque.

Se puede encontrar una tupla (xc, yc, zc, R) que representa una esfera que minimiza la distancia cuadrática media entre puntos y esferas. Busque el método Pratt (círculo específico) y Nelder-Mead (un método de optimización más general).