Esfera que seguramente abarca una lista dada de puntos [los puntos están con coordenadas x, y y z] - matemáticas, geometría, geometría computacional

Estoy tratando de encontrar esfera que maleducado abarca Dada lista de puntos. Los puntos tendrán coordenadas x, y, z [Los puntos están en 3D].

En realidad, estoy tratando de encontrar tres nuevos puntos basados ​​en la lista de puntos dada por algunos cálculos como encontrar MinX, MaxX, MinY, MaxY y MinZ y MaxZ y hacer algunas operaciones y encontrar nuevos tres puntos

Y dibujaré esfera de estos tres puntos.

Y también tomaré todo esto. Tres puntos en el diámetro de la esfera, así que tengo una esfera única.

¿Hay alguna forma estándar para encontrar una esfera abarcadora de una lista de puntos dada?

Respuestas

Sí, el algoritmo estándar es Algoritmo de Welzl (asumiendo que usted quiere el mínimo esfera alrededor de tus puntos). Particularmente la versión mejorada de Gaertner Es muy útil, robusto y numéricamente estable. Maneja todos los casos degenerados también.

En su núcleo, el algoritmo permuta los puntos.(aleatoriamente) para encontrar los 1-4 puntos que se encuentran en el límite de la esfera. Es básicamente un algoritmo inteligente de prueba y error. Desde estos puntos, puede encontrar el centro encontrando un punto que tenga la misma distancia que todos esos puntos. La versión de Gärtner utiliza un dispositivo numérico mejorado para encontrar el centro. Además, emplea un paso de giro adicional que presumiblemente hace que el algoritmo funcione mejor para una gran cantidad de puntos de entrada.

Si todo lo que quieres es una esfera alrededor de tres puntos,Le sugiero que siga utilizando el "dispositivo" de Gärtners para calcular la circumsfera del triángulo. De lo contrario, el método probablemente degenerará fácilmente (es decir, cuando el triángulo es muy plano).

¿Necesita 3 puntos, o cualquier número de puntos?

Si solo necesitas la respuesta por 3 puntos, cada unopar de puntos define un segmento de línea. Tome el segmento de línea más largo. Tome una esfera centrada en el centro de ese segmento de línea, cuyo radio es la mitad de la longitud del segmento de línea. Hay dos casos.

1. El tercer punto está dentro de esa esfera inicial. Si es así, entonces tienes la esfera más pequeña.
2. El tercer punto está fuera de esa esfera inicial. Entonces la solución en Encuentra el centro del circo de tres puntos del triángulo [No se usa la brújula] Te dará el centro de la esfera más pequeña que contiene esos 3 puntos.

Si necesita un número arbitrario de puntos, haría algún tipo de algoritmo de aproximación iterativa. Dado que no parece que necesite eso, no resolveré los detalles.