Algoritmo eficiente para encontrar las esferas más alejadas en la gran colección

Tengo una colección de 10000 - 100000 esferas, y necesito encontrar las más alejadas.Algoritmo eficiente para encontrar las esferas más alejadas en la gran colección

Una forma simple de hacerlo es simplemente comparar todas las esferas entre sí y almacenar la mayor distancia, pero esto se siente como un verdadero recurso de un algoritmo.

las esferas se almacenan en la siguiente forma:

Sphere (float x, float y, float z, float radius);

El método de la esfera :: distanceTo (Esfera & s) devuelve la distancia entre los dos puntos centrales de las esferas.

Ejemplo:

Sphere *spheres; 
float biggestDistance; 

for (int i = 0; i < nOfSpheres; i++) { 
    for (int j = 0; j < nOfSpheres; j++) { 
     if (spheres[i].distanceTo(spheres[j]) > biggestDistance) { 
      biggestDistance = spheres[i].distanceTo(spheres[j]) > biggestDistance; 
     } 
    } 
}

Lo que estoy buscando es un algoritmo que de alguna manera bucle a través de todas las posibles combinaciones de una manera más inteligente, si hay alguna.

El proyecto está escrito en C++ (que tiene que ser), por lo que las soluciones que solo funcionan en idiomas distintos de C/C++ son de menor interés.

Fuente

2010-02-16 illuzive

¿Es la tarea? –

Solo para aclarar, quieres algo mejor que O (n^2) (que es malo). Hmmm ..... – Craig

¿DistanceTo() obedece la desigualdad del triángulo? ¿distanceTo() se centra al centro o de la superficie a la superficie? ¿Las esferas tienen coordenadas en un espacio vectorial? ¿Está en un espacio euclidiano o hay agujeros negros curvando la métrica? ¿De dónde sacaste todas esas esferas, de todos modos? ¿Hay algo interesante dentro de las esferas que se pueda vender en eBay, porque parece que tienes muchas? – Paul

La distancia más grande entre dos puntos cualquiera en un conjunto S de puntos se llama diameter. Encontrar el diámetro de un conjunto de puntos es un problema bien conocido en la geometría computacional. En general, hay dos pasos aquí:

encontrar el casco convexo tridimensional compuesto por el centro de cada esfera - por ejemplo, utilizando la aplicación quickhull en CGAL.
Encuentra los puntos del casco más alejados. (Dos puntos en el interior del casco no pueden ser parte del diámetro, o de otra manera estarían en el casco, lo cual es una contradicción.)

Con quickhull, que puede hacer el primer paso en O (n log n) en el caso promedio y O (n) en el peor de los casos. (En la práctica, quickhull supera significativamente a todos los demás algoritmos conocidos). Es posible garantizar un mejor límite de caso peor si puede garantizar ciertas propiedades sobre el orden de las esferas, pero ese es un tema diferente.

El segundo paso se puede hacer de Ω (h log h), donde h es el número de puntos en el casco. En el peor de los casos, h = n (cada punto está en el casco), pero eso es bastante improbable si tienes miles de esferas aleatorias. En general, h será mucho más pequeño que n. Aquí está an overview of this method.

Fuente

2010-02-16 21:45:26

+1: borré mi publicación después de ver esta, ya que este es un superconjunto y una mejor respuesta. –

Hubiera sido más descriptivo sobre los pasos, pero esta es la tarea. Sin embargo, CGAL proporciona el código fuente, por lo que mirar eso es un buen comienzo para entender lo que está sucediendo aquí. –

Después de una breve búsqueda en Google, pensé en agregar este enlace también: http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/quickHull.htm –

¿Podría guardar estas esferas en un BSP Tree? Si eso es aceptable, entonces puedes comenzar buscando los nodos del árbol que contienen las esferas más alejadas. Luego puedes continuar descendiendo por el árbol hasta llegar a las esferas individuales.

Fuente

2010-02-16 21:34:26

También he pensado en la estructura de un árbol, pero todavía no he investigado el BSP Tree, gracias por su respuesta. =) – illuzive

Su problema parece algo que podría resolverse mediante gráficos. Como la distancia entre la Esfera A y la Esfera B es la misma que entre la Esfera B y la Esfera A, puede minimizar el número de comparaciones que tiene que realizar.

Creo que lo que estás viendo aquí se conoce como Adjacency List. Puede construir uno y luego recorrerlo para encontrar la distancia más larga.

Otro enfoque que puede utilizar le dará una O (n^2) pero puede minimizar el número de comparaciones que tiene que hacer. Puede almacenar el resultado de su cálculo en una tabla hash donde la clave es el nombre del borde (para que AB mantenga la longitud de A a B). Antes de realizar su cálculo de distancia, verifique si AB o BA existe en la tabla hash.

EDITAR

Utilizando el método de adyacencia lista (que es básicamente una Breadth-First Search) se obtiene O (b^d) o en el peor de los casos O (| E | + | V |) la complejidad.

Fuente

2010-02-16 21:38:01

-1: Esto realmente no es más eficiente que la fuerza bruta. –

Realmente, no tenía idea de que un BFS era un algoritmo tan ineficiente. Mis ojos se han abierto. –

Crear la lista de adyacencia requiere tanto tiempo como la solución de fuerza bruta. – IVlad

Paul tiene mi pensamiento del cerebro y se puede optimizar un poco cambiando

for (int j=0; j < nOfSpheres; j++)

for (int j=i+1; j < nOfSpheres; j++)

No es necesario comparar la esfera A a B Y B a A. Esto hará que la búsqueda sea O (n log n).

--- ------- adición

Otra cosa que hace este cálculo es caro que los cálculos DistanceTo.

distance = sqrt((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2)

Eso es mucha matemática. Puede recortarlo comprobando si

((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2 > maxdist^2

Elimina el sqrt hasta el final.

Fuente

2010-02-16 21:42:03 Craig

No, esto sigue siendo O (n^2), pero reduce el número de cheques a la mitad (estaba a punto de publicarlo también). –

Bah, tienes razón. Aún así, ayuda. ;) – Craig

Sí, lo sé. sqrt es caro – illuzive

Algoritmo eficiente para encontrar las esferas más alejadas en la gran colección

Respuesta

Cuestiones relacionadas