opengl - resumen - futbol americano reglas

Matemáticas en 3D: solo manteniendo las posiciones dentro de una cierta cantidad de yardas

Question

Estoy tratando de determinar a partir de un gran conjunto de posiciones cómo reducir mi lista significativamente.

En este momento tengo alrededor de 3000 posiciones (x, y, z) y básicamente quiero mantener las posiciones más alejadas entre sí (no necesito mantener 100 posiciones que estén todas dentro de un radio de 2 yardas una de la otra )

Además de hacer un método de fuerza bruta y, literalmente, hacer comparaciones de 3000 ^ 2, ¿alguien tiene alguna idea de cómo puedo reducir aún más esta lista?

Estoy un poco confundido sobre cómo abordar esto desde una perspectiva matemática.

Answer 1

Bueno, no recuerdo el nombre de este algoritmo, pero te contaré una técnica divertida para manejarlo. Asumiré que hay una dispersión semi-aleatoria de puntos en un entorno 3D.

Versión simple: Divide y conquista

1. Divide tu espacio en una grilla 3D de cubos. Cada cubo será X yardas en cada lado.
2. Declare una matriz multidimensional [x, y, z] tal que tenga un elemento para cada cubo en su cuadrícula.
3. Cada elemento de la matriz debe ser un vértice o una referencia a una estructura de vértice (x, y, z), y cada uno debe ser NULO
4. Itere a través de cada vértice en su conjunto de datos, determine en qué cubo se encuentra el vértice.
   • ¿Cómo? Bueno, puedes suponer que el vértice (5.5, 8.2, 9.1) pertenece a MyCubes [5,8,9], suponiendo que X (cubo-lado-longitud) es de tamaño 1. Nota: Acabo de truncar los decimales / flotantes para determinar qué cubo
5. Verifique si ese cubo relevante ya está ocupado por un vértice. Verifique: si MyCubes [5,8,9] == NULL, entonces (inyecte mi vértice) else (¡no haga nada, tírelo! Punto tomado, amigo)

Ahorremos algo de memoria

Esto le dará un conjunto de datos muy simplificado en una sola pasada, pero a costa de una gran cantidad de memoria.

Entonces, ¿cómo lo haces sin usar demasiada memoria?

Usaría una tabla hash tal que mi clave es la coordenada Grid-Cube (5,8,9) en mi muestra anterior.

 If MyHashTable.contains({5,8,9}) then DoNothing else InsertCurrentVertex(...)

Ahora, tendrá una solución de una sola pasada con un uso mínimo de memoria (no una matriz gigantesca con una gran cantidad de cubos vacíos. ¿Cuánto cuesta? Bueno, el tiempo de programación para configurar su estructura / clase para que pueda realizar el. contiene acción en una tabla Hash (o su equivalente de idioma)

¡Oye, mis resultados son gruesos!

Así es, porque tomamos el primer resultado que cabe en cualquier cubo. En promedio, habremos logrado la separación X entre vértices, pero como puedes imaginar ahora, algunos vértices seguirán cerca uno del otro (en los bordes de los cubos).

Entonces, ¿cómo lo manejamos? Bueno, volvamos al método de matriz en la parte superior (¡que requiere mucha memoria!).

En lugar de SOLO verificar para ver si un vértice ya está en el cubo en cuestión, también realice esta otra comprobación:

 If Not ThisCubeIsTaken()
    For each SurroundingCube
      If not Is_Your_Vertex_Sufficiently_Far_Away_From_Me()
         exit_loop_and_outer_if_statement()
      end if
    Next
    //Ok, we got here, we can add the vertex to the current cube because the cube is not only available, but the neighbors are far enough away from me
 End If

Creo que probablemente puedas ver la belleza de esto, ya que es muy fácil obtener cubos vecinos si tienes una matriz 3D.

Si haces un suavizado como este, probablemente puedas aplicar una política de ''no agregar si está con 0.25X'' o algo así. No tendrá que ser demasiado estricto para lograr un efecto de suavizado notable.

Todavía demasiado grueso, quiero que sea suave

En esta variación, cambiaremos la acción de calificación para si se permite que un vértice tome residencia en un cubo.

 If TheCube is empty OR if ThisVertex is closer to the center of TheCube than the Cube''s current vertex
    InsertVertex (overwrite any existing vertex in the cube
 End If

Tenga en cuenta que no es necesario realizar la detección de vecinos para este. Simplemente optimizamos hacia el centro de cada cubo.

Si lo desea, puede fusionar esta variación con la variación anterior.

Modo trampa

Para algunas personas en esta situación, simplemente puede tomar una selección aleatoria del 10% de su conjunto de datos y eso será una simplificación lo suficientemente buena. Sin embargo, será muy fornido con algunos puntos muy juntos. En el lado positivo, lleva unos minutos como máximo. No lo recomiendo a menos que esté haciendo prototipos.