algorithm - pseint - Algoritmo de burbuja de rebote para la esfera de encierro más pequeña

ordenamiento por intercambio

Question

Estoy interesado en el Algoritmo de burbuja de rebote para encontrar la esfera de aproximación más pequeña para un conjunto de puntos.

Entiendo el concepto básico: " cada vez que se encuentra un punto fuera de la pelota, la bola se moverá hacia ella y aumentará el radio al mismo tiempo. El crecimiento en cada paso está diseñado para que no exceda el radio óptimo, por lo tanto, el radio se acerca cada vez más al óptimo " .

Sin embargo, no he podido encontrar nada más específico en línea en ningún lugar. ¿Cómo se calcula el crecimiento? ¿Qué tan lejos está el cambio hacia el nuevo punto?

Estoy buscando ya sea una implementación de ejemplo o suficiente información para implementar mi propia solución.

Answer 1

Aquí está la implementación que solicitó. Para la parte de análisis, puede obtener la idea leyendo lo siguiente.

Estos anaylsis son para círculo (2d) pero la extensión a esfera (3d) debería ser fácil. Estoy seguro de que el análisis ayudará.

Un algoritmo O (n2) -time

• Dibuja un círculo en el centro, c, tal que los puntos del conjunto dado se encuentren dentro del círculo. Claramente, este círculo puede hacerse más pequeño (o si no, tenemos la solución).
• Haz un círculo más pequeño encontrando el punto A más alejado del centro del círculo, y dibujando un nuevo círculo con el mismo centro y pasando por el punto A. Estos dos pasos producen un círculo circundante más pequeño. La razón por la cual el nuevo círculo es más pequeño es que este nuevo círculo todavía contiene todos los puntos del conjunto dado, excepto que ahora pasa a través del punto más lejano, x, en lugar de encerrarlo.
• Si el círculo pasa por 2 o más puntos, continúe con el paso 4. De lo contrario, haga que el círculo sea más pequeño moviendo el centro hacia el punto A, hasta que el círculo haga contacto con otro punto B del conjunto.
• En esta etapa, tenemos un círculo, C, que pasa por dos o más puntos de un conjunto dado. Si el círculo contiene un intervalo (intervalo sin puntos) de arco mayor que la mitad de la circunferencia del círculo en el que no hay puntos, el círculo puede hacerse más pequeño. Deje que D y E sean los puntos al final de este intervalo sin puntos. Mientras mantiene D y E en el límite del círculo, reduzca el diámetro del círculo hasta que tengamos el caso (a) o el caso (b).
  • Caso (a) El diámetro es la distancia DE.
    ¡Hemos terminado!
  • Caso (b) El círculo C toca otro punto del conjunto, F.
    Verifique si hay intervalos de arco sin puntos de longitud de más de la mitad de la circunferencia de C.
    SI
    no salen tales intervalos de arco sin punto ENTONCES ¡Hemos terminado!
    Más
    Vaya al paso 4. En este caso, tres puntos deben estar en un arco de menos de la mitad de la circunferencia de longitud. Repetimos el paso 4 en los dos puntos externos del arco.

Análisis

Este algoritmo es directo, pero costoso de implementar. Los pasos 1, 2 y 3 requieren tiempo lineal en la cantidad de puntos en el conjunto dado. En el paso 4 anterior, se necesita tiempo lineal para encontrar cada nuevo punto F. Sin embargo, encontrar el punto F no garantiza la terminación del algoritmo. El paso 4 debe repetirse hasta que el círculo no contenga ningún intervalo sin puntos más largo que la mitad de su circunferencia. En el peor de los casos, esto requiere (n-2) iteraciones del paso 4, lo que implica que el tiempo total gastado en el paso 4 podría ser del orden del cuadrado del tamaño del conjunto de puntos.

Por lo tanto, este algoritmo es O (n2).

O (n) Algoritmo

Nimrod Megiddo propone el algoritmo y utiliza las técnicas de poda y búsqueda para la programación lineal para encontrar el círculo delimitador mínimo en el tiempo O (n).

Podar y buscar

La esencia del algoritmo de Megiddo es podar y buscar. En un algoritmo de poda y búsqueda, se realiza una cantidad lineal de trabajo en cada paso para reducir el tamaño de entrada en una fracción constante f. Si esto se puede lograr, entonces la cantidad total de trabajo realizado se reducirá a O (n) * (1 + (1-f) + (1-f) 2 + ...). En esta fórmula, la serie infinita es geométrica y se suma a un valor constante, por lo que el tiempo total de ejecución es O (n).

Por ejemplo, supongamos que al inspeccionar nuestro conjunto de n elementos de entrada podemos descartar 1/4 de ellos como irrelevantes para la solución. Al aplicar repetidamente esta inspección a los elementos restantes, podemos reducir la entrada a un tamaño que es trivial de resolver, digamos n≤3. El tiempo total necesario para lograr esta reducción será proporcional a (n + 3n / 4 + 9n / 16 + ...). Es fácil mostrar que esta serie se acerca, y nunca excede, a un límite de 4n. Por lo tanto, el tiempo de ejecución total es proporcional a n, según sea necesario.

La idea de usar la serie geométrica para reducir un algoritmo a tiempo lineal es anterior al trabajo de Megiddo; en particular, se había utilizado previamente para desarrollar algoritmos de búsqueda de O (n) mediana. Sin embargo, fue el primero en aplicarlo a una serie de problemas fundamentales en la geometría computacional.

Algoritmo de tiempo lineal de Megiddo

Para encontrar el círculo delimitador mínimo (MEC) de un conjunto de puntos, el algoritmo de Megiddo descarta al menos n / 16 puntos en cada iteración (tiempo lineal). Es decir, dado un conjunto S de n puntos, el algoritmo identifica n / 16 puntos que pueden eliminarse de S sin afectar el MEC de S. Este procedimiento puede aplicarse repetidamente hasta que se alcance algún caso base trivial (como n = 3 ), con el tiempo total de funcionamiento proporcional a (n + 15n / 16 + 225n / 256 + ...) = 16n.

Con el fin de encontrar n / 16 puntos para descartar, se requiere una gran cantidad de astucia. El algoritmo hace un uso intensivo de dos subrutinas:

• mediana (S,>): Toma un conjunto S de elementos y una métrica para compararlos por pares, y devuelve la mediana de los elementos.
• Centro MEC (S, L): toma un conjunto S de puntos y una línea L, y determina en qué lado de L se encuentra el centro del MEC de S.

Como se mencionó anteriormente, la mediana () es anterior al trabajo de Megiddo, mientras que el algoritmo descrito aquí como MEC-center () se presentó como parte de su artículo de 1983. Explorar estos procedimientos en detalle iría más allá del alcance de este esquema, pero cada uno usa la opción de podar y buscar para correr en tiempo lineal. El algoritmo utilizado por MEC-center () equivale a una versión simplificada del algoritmo como un todo.

Teniendo en cuenta estas primitivas, el algoritmo para descartar n / 16 puntos de entrada se ejecuta de la siguiente manera:

• Arbitrariamente empareja los n puntos en S para obtener n / 2 pares.
• Construya una línea de bisección para cada par de puntos, para obtener n / 2 bisectrices en total.
• Llame a la mediana () para encontrar la bisectriz con pendiente media. Llame a esta pendiente mmid.
• Empareje cada bisectriz de pendiente ≥ mmid con otra de pendiente <mmid, para obtener n / 4 puntos de intersección. Llamar al conjunto de estos puntos I.
• Llame a la mediana () para encontrar el punto en I con el valor promedio de y. Llame a este y-valor ymid.
• Llame al centro MEC () para encontrar en qué lado de la línea y = ymid se encuentra el centro C del MEC. (Sin pérdida de generalidad, supongamos que se encuentra arriba).
• Deje que yo sea el subconjunto de puntos de I cuyos valores y son menores que ymid. (I ''contiene n / 8 puntos)
• Encuentra una línea L con pendiente mmid de manera que la mitad de los puntos en I ''mientan a la izquierda de L, la mitad a su derecha.
• Llame a MEC-center () en L. Sin pérdida de generalidad, suponga que C está en la derecha de L.
• Deje que yo sea el subconjunto de I, cuyos puntos se encuentran a la izquierda de L. (I '''' contiene n / 16 puntos).

Ahora podemos descartar un punto en S para cada uno de los n / 16 puntos de intersección en I ''''. El razonamiento funciona de la siguiente manera. Después de dos llamadas al centro MEC (), hemos encontrado que el centro MEC C debe estar encima de ymid y a la derecha de L, mientras que cualquier punto en I '''' está debajo de ymid y a la izquierda de L.

Cada punto en I '''' está en el punto de encuentro de dos líneas de bisectriz. Una de estas bisectrices debe tener una pendiente ≥ mmid y, por lo tanto, nunca debe atravesar el cuadrante donde sabemos que C yace. Llame a esta bisectriz B. Ahora, sabemos de qué lado de BC se encuentra, así que de los dos puntos cuya bisectriz es B, deje que PC sea la que se encuentre en el mismo lado que C, y que la otra sea PX.

Es fácil mostrar que la PC debe estar más cerca de C que de PX. Se deduce que la PC no puede estar en el círculo delimitador mínimo, y por lo tanto podemos descartar de forma segura una PC de punto para cada uno de los n / 16 puntos de intersección en I ''''.

No hemos discutido aquí cómo este algoritmo puede hacerse para tratar con entradas degeneradas (bisectrices paralelas, puntos colineales, etc.), pero resulta que obtenemos las mismas garantías de rendimiento para tales casos. El hecho es que para una entrada degenerada, el algoritmo puede descartar más de n / 16 puntos. En resumen, el algoritmo de Megiddo garantiza podar al menos n / 16 puntos en cada iteración, independientemente de la entrada.

Por lo tanto, según el argumento basado en la serie geométrica, el algoritmo de Megiddo calcula el círculo delimitador mínimo en tiempo lineal.

Consulte este documento para obtener más información sobre el algoritmo O (n)

Answer 2

Me doy cuenta de que esta publicación tiene un año de antigüedad, pero implementé el algoritmo de burbujas de rebote en C ++ y pensé que tal vez algunas personas lo encontrarían útil. Esto se basa en el documento de Tian Bo, que compré por $ 18.

BoundSphere calculateBoundSphere(vector<Vertex> vertices){
    Vector3D center = vertices[0].position;
    float radius = 0.0001f;
    Vector3D pos, diff;
    float len, alpha, alphaSq;
    vector<Vertex>::iterator it;

    for (int i = 0; i < 2; i++){
        for (it = vertices.begin(); it != vertices.end(); it++){
            pos = it->position;
            diff = pos - center;
            len = diff.length();
            if (len > radius){
                alpha = len / radius;
                alphaSq = alpha * alpha;
                radius = 0.5f * (alpha + 1 / alpha) * radius;
                center = 0.5f * ((1 + 1 / alphaSq) * center + (1 - 1 / alphaSq) * pos);
            }
        }
    }

    for (it = vertices.begin(); it != vertices.end(); it++){
        pos = it->position;
        diff = pos - center;
        len = diff.length();
        if (len > radius){
            radius = (radius + len) / 2.0f;
            center = center + ((len - radius) / len * diff);
        }
    }

    return BoundSphere(center, radius);
}

Answer 3

ACTUALIZACIÓN : Tras una revisión más detallada de la animación y el artículo de Wikipedia, he decidido que mi algoritmo no es Bouncing Bubble. A partir de la animación, está claro que Bouncing Bubble mueve la esfera delimitadora, mientras que mi algoritmo solo crece en una dirección a la vez. Además, tengo entendido que Bouncing Bubble utiliza una aproximación y puede que no contenga todos los puntos; sin embargo, parece que hay un parámetro de tolerancia que puede controlar.

Creo que mi algoritmo todavía tiene algunas buenas propiedades:

1. Esta encendido).
2. Es incremental.
3. Está garantizado que contiene todos los puntos.
4. Es muy simple. Lo único más simple sería encontrar el cuadro delimitador alineado con el eje, y luego poner una esfera alrededor de eso, pero seguramente ese será un volumen mayor al que produce este algoritmo.

Se me ocurrió un algoritmo incremental de O (n), que a partir de la descripción en Wikipedia creo que debe ser el algoritmo de Bouncing Bubble. No tengo idea de lo cerca que está del círculo mínimamente delimitador. Primero intentaré explicar mi razonamiento detrás del algoritmo. Puede ser útil dibujar esto en papel.

Imagine que tiene un círculo delimitador con algún centro C y radio r . Desea extender el círculo para contener un nuevo punto P. Calcula la distancia d de C a P y encuentra que es mayor que r , por lo que debe estar fuera del círculo. Ahora si lanzas un rayo de P a C , sale de la parte posterior del círculo en A.

Ahora imagine que fija el círculo en A y luego lo expande a lo largo del rayo hacia P. Continuará conteniendo todos los puntos anteriores, y ahora contiene P. El diámetro de este nuevo círculo es r + d , por lo que su radio es r ''= (r + d) / 2 . Camina a lo largo del rayo de P a A por la distancia del nuevo radio, y estás en el centro del nuevo círculo.

Aquí hay un boceto del algoritmo:

1. Inicialice la esfera delimitadora para centrarse en el primer punto C con un radio r de 0.
2. Para cada punto restante P :
   1. Si la distancia d de P a C es <= r , sáltelo.
   2. Si d> r :
      1. El nuevo radio r ''= (r + d) / 2 .
      2. El nuevo centro C ''= P + r'' (C - P) / d .

Y aquí hay un código de Objective-C que escribí hoy:

- (void)updateBoundingVolume {
    self.boundingSphereCenter = GLKVector3Make(0, 0, 0);
    self.boundingSphereRadius = 0;

    GLfloat* vertex = self.vertices;
    GLfloat* endV = vertex + 3 * self.vertNum;

    if (vertex < endV) {
        // initialize to zero radius sphere centered on the first point
        self.boundingSphereCenter = GLKVector3Make(vertex[0], vertex[1], vertex[2]);
        vertex += 3;
    }

    while (vertex < endV) {
        GLKVector3 p = GLKVector3Make(vertex[0], vertex[1], vertex[2]);
        vertex += 3;

        float d = GLKVector3Distance(self.boundingSphereCenter, p);
        if (d <= self.boundingSphereRadius) {
            // already inside the sphere
            continue;
        }

        // length of line from other side of sphere through the center to the new point
        // divide by 2 for radius
        self.boundingSphereRadius = (self.boundingSphereRadius + d) / 2;

        // unit vector from new point to old center
        GLKVector3 u = GLKVector3DivideScalar(GLKVector3Subtract(self.boundingSphereCenter, p), d);
        // step back from the new point by the new radius to get the new center
        self.boundingSphereCenter = GLKVector3Add(p, GLKVector3MultiplyScalar(u, self.boundingSphereRadius));
    }
}