computational geometry - Aproximación de un sólido por una unión de esferas.
computational-geometry mathematical-optimization (4)
El problema no es simple, pero ha sido estudiado previamente. El concepto central es el eje medial , que puede verse como una representación de un objeto por una unión infinita de bolas. Un documento clave que aborda su pregunta es:
"La corteza de poder, las uniones de bolas y el eje medial se transforman". Nina Amenta, Sunghee Choi, Ravi Krishna Kolluri. Geometría computacional . Volumen 19, números 2–3, julio de 2001, páginas 127–153. ( Enlace del diario ).
(Fuente de las imágenes: de nubes de puntos a cortezas de energía ).
Un segundo papel es
Cazals, Frédéric, et al. "Algoritmos geométricos codiciosos para la recolección de bolas, con aplicaciones para la aproximación geométrica y el grano grueso molecular". Foro de gráficos por ordenador . Vol. 33. No. 6. 2014. ( descarga de PDF .)
cuya primera oración es "Elegir bolas que mejor se aproximen a un objeto 3D es un problema no trivial". Su aplicación principal es a los modelos moleculares, que pueden estar lejos de sus intereses.
Tengo un sólido 3D, representado como la unión de un conjunto de cascos poliédricos convexos. (O un solo convexo, si eso facilita las cosas). Me gustaría aproximar ese sólido como la unión de un conjunto de esferas, de manera que minimice tanto el número de esferas en el conjunto como el error en la aproximación. (El último objetivo es deliberadamente vago: cualquier métrica de error razonable funcionará. Del mismo modo, la forma en que se combinan los objetivos está en el aire; ya sea el número de esferas o la métrica de error podrían restringirse, o alguna función de las dos podría minimizarse. No quiero especificarme en una esquina.)
No es necesario que la aproximación contenga por completo o esté completamente contenida por el conjunto original. Cada esfera puede tener un radio arbitrario.
Esto se siente como el tipo de problema que es NP-completo, y en cualquier caso es poco probable que sea práctico usando métodos exactos, así que supongo que la solución se encuentra en el ámbito de la optimización estocástica. Se siente como si una variante de k-means pudiera encajar (asignando ubicaciones no cubiertas a sus esferas más cercanas y refinando las esferas para cubrir algunas de ellas), pero no estoy seguro de cómo manejar ubicaciones con cobertura múltiple, o cómo encontrar la Local, no necesariamente todo lo que cubre todo lo óptimo incluso para una sola esfera. Además, para los métodos iterativos, la eficiencia es importante, y hacer operaciones booleanas en 3D no va a ser eficiente.
Esto es lo que se me ocurrió. Este enfoque es más una operación booleana iterativa en 3D, por lo que puede que no sea lo que está buscando. La superficie parece más difícil, así que me concentré en eso.
Visión general
Básicamente, agregue esferas dentro de la forma en posiciones que maximicen la cobertura de la superficie. Convertimos la esfera en una matriz 3D de valores de bytes firmados. Estos valores son puntos y serán engullidos con esferas. Agregamos una esfera a la vez dentro del objeto y luego lo aumentamos / encogemos en diferentes direcciones para "comer" tantos puntos como sea posible. El objetivo es acumular tantos puntos como sea posible por esfera. Los puntos se ganan sumando los puntos en el área de la esfera. Con la adición de cada esfera contamos, luego contamos esa área como se usa y establecemos los valores de Array en 0.
(A) (B) ZZZZZZ (C) ZZZZZZ (D) ZZZZZZ (E) ZZZZZZ (F) ZZZZZZ
// ZX33XZ ZX33XZ ZX33XZ ZX33XZ ZX33XZ
/ / ZX3223XZ ZX3223XZ ZX##23XZ ZX ##XZ ZX XZ
/ / ZX321123XZ ZX321123XZ ZX####23XZ ZX ####XZ ZX XZ
| | ZX32111123XZ ZX32111123XZ ZX######23XZ ZX ######XZ ZX XZ
| | ZX32111133XZ ZX32111133XZ ZX######23XZ ZX ######XZ ZX XZ
| | ZX32222223XZ ZX##222223XZ ZX3####223XZ ZX3 ####3XZ ZX3 ##XZ
|------| ZX33333333XZ ZX##333333XZ ZX33##3333XZ ZX33 ##33XZ ZX33 ##XZ
X= -1 ZXXXXXXXXXXZ ZXXXXXXXXXXZ ZXXXXXXXXXXZ ZXXXXXXXXXXZ ZXXXXXXXXXXZ
Y= -2 ZZZZZZZZZZZZ ZZZZZZZZZZZZ ZZZZZZZZZZZZ ZZZZZZZZZZZZ ZZZZZZZZZZZZ
(A) La forma que queremos rellenar. (2D utilizado aquí pero 3D sería similar)
(B) Convertir la forma en una cuadrícula 3D de puntos. La superficie obtiene el mayor número y al trabajar en el centro, los números se asientan en números positivos bajos (como 1); Fuera de la forma obtiene números negativos; interior profundo obtiene 1
(C) Agrega una pequeña esfera. (Lo creceremos)
(D) Expandir la esfera hasta que engullimos el número máximo de puntos
(E) Añade la siguiente esfera y crece.
(F) Agrega otra esfera. Este es pequeño.
Proceso
5) primero descomponer la forma en una resolución de bloque 3D.
10) Luego da la mayor cantidad de "puntos" a los bloques alrededor de la superficie. Los puntos altos con el bloque que realmente toca la superficie y los puntos inferiores cuando se mueve hacia adentro o hacia afuera. A medida que avanza hacia el exterior, los puntos deberían convertirse rápidamente en negativos, ya que esto evitará que sobresalgan las esferas. A medida que te mueves hacia adentro desde la superficie, los puntos deben establecerse en 1 para que el área central sea todos unos. Estos puntos se pueden configurar de diferentes maneras para producir resultados diferentes.
15) Encuentre una ubicación en el borde interior de la forma que está fuera de una esfera. Aunque no es necesario estar cerca del borde, minimiza el área de búsqueda. Si no se puede encontrar una ubicación, vaya a 80. Si no se puede encontrar una ubicación que esté cerca
20) Dibuja una esfera con un radio cero dentro de la forma que no está cubierta
25) Mueva la esfera arriba / abajo hasta que los puntos se maximicen (recocido simulado)
26) Mueve la esfera hacia adentro / afuera hasta que los puntos estén maximizados
27) Mueve la esfera a la izquierda / derecha hasta que los puntos estén maximizados
28) Mueva la parte superior de la esfera hacia arriba / abajo hasta que se maximicen los puntos (recocido simulado / ascenso de colinas)
29) Mueva la parte inferior de la esfera hacia arriba / abajo hasta que los puntos se maximicen
30) Mueve el lado izquierdo de la esfera hacia adentro / afuera hasta que los puntos estén maximizados
31) Mueve el lado derecho de la esfera hacia adentro / afuera hasta que se maximicen los puntos
32) Mueve el frente de la esfera hacia adentro / afuera hasta que los puntos estén maximizados
50) Si hay cambios en 25-32, repita (vaya a 25)
70) Resta los puntos de la última esfera añadida. Establezca todos los valores en cero para los valores internos (números positivos) y no ajuste los valores externos (números negativos). Goto 15.
80) (opcional) Rellena los huecos internos. Básicamente, visite cada elemento para asegurarse de que sea menor o igual a 0. Si es positivo, pase a 20 con ese elemento. De lo contrario, si no se encuentra ninguno, entonces goto 85. Nota: todos los valores externos deben ser negativos y todos los valores internos que están en una esfera deben ser 0.
85) Terminado
Notas
- Como habría una cuadrícula de valores, un espacio de trabajo de 1000x1000x1000 consumiría hasta 1 GB.
- No es una solución exacta
- Podría tomar un montón de cálculo para resoluciones más altas.
- Por eficiencia, las esferas más pequeñas pueden tener sus rangos de píxeles pregrabados, de modo que no es necesario calcular la esfera para cada iteración.
- Una versión de resolución más baja (es decir, 500x500x500) se podría completar primero y luego la ubicación y el tamaño de las esferas se podrían aplicar a un 1000x1000x1000 más grande. También para formas muy grandes se podrían resolver subsecciones.
Hm, mi mejor idea hasta ahora involucra máquinas de vectores de soporte. Convierta su objeto en un montón de puntos (probablemente espaciados) dentro y sobre la superficie del objeto. Entrene un modelo SVDD usando un kernel lineal (vea libsvm para una implementación SVDD). La función de decisión del modelo representa una superficie implícita definida por los vectores de soporte del modelo (y rho). Al reducir el costo obtendrá más vectores de soporte, al subirlo, obtendrá menos.
Desafortunadamente, la naturaleza de los SVM es tal que el área cubierta por los vectores de soporte cercanos se verá como "burbuja", algo así:
(Lo siento, mi intuición para SVMs es totalmente geométrica / visual).
Ahora, no tienes esferas bonitas y nítidas, pero ( ¡agitando las manos masivamente! ) Esperemos que el algoritmo haya elegido una distribución útil de centros para las esferas.
Finalmente, puede inventar una función que calcula el error como una función de los radios para los centros de esferas en todos esos puntos. Luego simplemente alimente eso a un optimizador no lineal y dígale que lo minimice. Bam.
Si está dispuesto a darle más potencia de CPU, podría ejecutar otra capa de minimización de errores por encima de esa, que repite todo el proceso anterior para diferentes costos de vectores de soporte, intentando minimizar alguna combinación de error y costo. (Quizás error/cost ).
Un buen comienzo sería desarrollar un algoritmo para:
1) Encuentra el radio más grande de una esfera inscrita.
2) Entonces considera el volumen de resta
3) Aproxima el volumen de resta por un poliédrico.
4) Subdividir el poliédrico en poliédricos más pequeños (más finos).
5) Rehacer el paso 1.
Puede haber algunas variaciones, pero parece responder a su pregunta. Como puede ver, la función de error disminuye a medida que aumenta el número de esferas, por lo que no puede minimizar ambas: eso es un compromiso. Pero puede corregir uno e intentar optimizar otro, por ejemplo, corregir la función de error para que sea una tolerancia aceptable y minimizar el número de esferas para hacerlo, o viceversa.