Cómo realizar un particionamiento espacial en n-dimensiones?

Question

estoy tratando de diseñar una implementación de Cuantificación Vectorial como ++ clase de plantilla c que puede manejar diferentes tipos y dimensiones de los vectores (por ejemplo, 16 vectores de dimensión de bytes, o vectores 4d de dobles, etc.).

He estado leyendo sobre los algoritmos, y entiendo la mayor parte de él:

aquí y aquí

Quiero poner en práctica el Linde-Buzo-Gray (LBG) Algoritmo, pero estoy teniendo dificultades para averiguar el algoritmo general para dividir los grupos. Creo que necesito para definir un plano (hiperplano?) Que divide los vectores en un grupo por lo que hay un número igual en cada lado del plano.

[editar para agregar más información] Este es un proceso iterativo, pero creo que empezar por encontrar el centro de gravedad de todos los vectores, a continuación, utilizar ese centroide para definir el plano de división, obtener el centroide de cada uno de los lados del plano, continuando hasta que tenga el número de grupos necesaria para el algoritmo de VQ (iterando para optimizar menos distorsión en el camino). La animación en el primer enlace de arriba Nicely lo muestra.

Mis preguntas son:

¿Qué es un algoritmo para encontrar el avión una vez que tenga el centro de gravedad?

¿Cómo puedo probar un vector para ver si está en cualquier lado de ese plano?

Answer 1

Si usted comienza con un centro de gravedad, entonces tendrá que dividir, básicamente, con la duplicación y ligeramente moviendo los puntos de separación, en una dirección arbitraria. El avión es sólo el plano ortogonal a la dirección.

Sin embargo, no es necesario para calcular ese plano.

Más en general, la región (i) se define como el conjunto de puntos que están más cerca de la C_I centroide que a cualquier otro centroide. Cuando tiene dos centroides, cada región es un espacio de media, por lo tanto separadas por un plano (hiper).

Como prueba en un vector x para ver en qué lado del plano que es? (Que es con dos centroides)

Just calcular la distancia || x-c1 || y || x-c2 ||, el índice del valor mínimo (1 o 2) le dará qué región del punto x pertenece.

Más en general, si tiene n centroides, que sería calcular todas las distancias || x-C_I ||, y el x centroide es más cercana a (es decir, para los que la distancia es mínima) le dará la región x es perteneciente a.

Answer 2

Yo no entiendo muy bien el algoritmo, pero la segunda pregunta es fácil:

Vamos llamada V un vector que se extiende de cualquier punto en el plano a el punto en cuestión. Entonces las mentiras de punto en el pregunta en el mismo lado de la (hiper) plano que la normal de N si y sólo si V · N > 0