setlayout - manejo de gridlayout en java

Determinar si una esfera está encerrada completamente por otras esferas colocadas a su alrededor (1)

Problema: dada una lista de esferas, encuentre todos los espacios vacíos que están completamente rodeados por esferas.

Detalle: Este es un problema en el que estoy trabajando para tratar de determinar las cavidades ubicadas en una proteína. Me dan una lista de los átomos que componen las coordenadas de la proteína ((x, y, z) y el radio). Luego ejecuto mi algoritmo para encontrar todos los espacios vacíos que se encuentran dentro de los límites de la proteína al verificar si una sonda (de radio determinado) se puede colocar en una ubicación sin colisionar con otras esferas. Hay dos tipos de espacios vacíos, espacios vacíos y cavidades. Los espacios vacíos son espacios que pueden conducir hacia o fuera de la proteína. Las caries son espacios vacíos que están completamente rodeados por átomos de proteínas. Aquí hay una imagen de la muestra "proteína" con la que estamos trabajando.

Se puede ver en tres dimensiones aquí .

Hay una cavidad situada cerca del centro de la proteína, el túnel que ve pasar a través de la proteína se consideraría un espacio vacío porque no está completamente encerrado por átomos.

Ejemplo: Dada una lista de 26 átomos, estos átomos están espaciados uniformemente de (0,0,0) a (1,1,1) en una cuadrícula tridimensional. Cada átomo tiene un radio de 0.25 y se coloca en 0, 0.5 o 1 en cualquier eje. No hay átomo en el punto (0.5, 0.5, 0.5). Si tuviéramos que dibujar una figura 3D de estos átomos, sería una forma de cubo con el centro faltante. Una cavidad se designaría en (0.5,0.5,0.5) con un radio de 0.25. Se puede suponer que esta cavidad está rodeada de proteínas en todos los lados.

Imagen de ejemplo:

Tenga en cuenta que lo anterior es solo una representación en 2D del cubo y la proteína. En realidad es 3D.

¿Cómo se podría determinar los espacios vacíos frente a las cavidades para un grupo de átomos mucho más grande e irregularmente formado?

Estaba pensando en implementar un algoritmo recursivo que verifique todas las direcciones para ver si puede alcanzar los límites máximo y mínimo del gráfico, pero no estoy seguro de si esta es la forma correcta de hacerlo.

Extra: ¿Hay un algoritmo diferente que diría que la cavidad en el ejemplo es en realidad un espacio vacío porque hay "caminos" muy pequeños para alcanzar el exterior de la proteína? Una cavidad tendría que estar completamente encerrada por átomos para existir. Cualquier espacio vacío que tenga una ruta (en cualquier dirección, no necesariamente recta) hacia el exterior de la proteína no se considerará cavidades.

Buena pregunta Aquí hay un algoritmo que debería hacer el truco:

Notación:

Llamemos a nuestra esfera móvil S
Escriba diam(X) para el diámetro de una esfera X
Escriba dist(X,Y) para la distancia de X a Y ; esto es lo mismo que la distancia desde el centro de X al centro de Y menos la suma de los radios.

El algoritmo:

Para dos esferas inamovibles A y B , compruebe si S puede pasar directamente entre los centros de A y B (es decir, ¿es diam(S) <= dist(A,B) ?).
Si es así, para cada otra esfera C , compruebe si S podría tocar simultáneamente las tres esferas A , B y C , si no hubiera otras esferas presentes. Si S puede tocar simultáneamente los 3, dibuje un triángulo entre los centros de A , B y C
- Esto se puede verificar de varias maneras. Una manera bastante fácil: las posibles posiciones del centro de S mientras tocan tanto A como B forman un círculo. Desea saber si este círculo tiene un punto que es menor que diam(S) + diam(C) lejos del centro de C Esto es geometría fácil.
El problema ahora se reduce a la pregunta: ¿los triángulos separan la posición inicial del centro de S del infinito? Puede responder a este componente conectado a la vez. De hecho, incluso puede responder a este componente "conectado por flanco" a la vez, donde un componente está conectado por flanco si dos puntos no-vértices pueden vincularse mediante una ruta que no atraviese ningún vértice. Puede calcular estos componentes a través de una simple búsqueda de gráficos.
Para un componente determinado conectado al borde, debe decidir si el componente separa el centro de S del infinito. Hay algunas maneras en que puede hacer esto:
- Calcule la 2- homología del componente, elija generadores efectivos y, para cada uno, pregunte si su punto e infinito están en el mismo lado del ciclo o no, lo cual puede verificarse utilizando la clase de orientación.
- O simplemente comienza a pintar el componente:
  - Comienza con un triángulo al que puedes ir desde S y pinta cada cara que se pueda alcanzar desde allí. Esto es un poco sutil, pero el algoritmo es simplemente "comenzar en cualquier lugar, poner los bordes en cola, cruzar cada borde en la cara formando el ángulo más pequeño con ese borde, y parar cuando no quedan bordes". Tenga en cuenta que el lado opuesto del mismo triángulo podría ser la cara que forma el ángulo más pequeño.
  - Haz lo mismo desde el infinito. ¿Cruzaste triángulos pintados? Si es así, tu esfera puede escapar. Si no, no puede.

Por qué funciona

El paso 3 es verdadero porque si no golpeas ninguna esfera C mientras "te mueves" por el borde entre A y B , entonces puedes alcanzar cualquier lado de ese borde. Dicho de otra manera, cualquier posición que impida que vayas al infinito debe implicar que S toque al menos 3 esferas.

Tenga en cuenta que hay algunas sutilezas que surgen de situaciones "excepcionales", como cuando S toca 4 esferas a la vez. Puede evitar estas sutilezas volviendo a triangular su forma antes de realizar los pasos 3 y 4.