Topojson: cuantificación VS simplificación

d3.js

Question

¿Cuál es la diferencia entre la quantization y la simplification ? ¿Es la cuantificación otra forma de simplificación? ¿Es mejor usar la cuantificación en ciertas situaciones? ¿O debería usar una combinación de ambos?

Answer 1

El tamaño total de su geometría está controlado por dos factores: el número de puntos y el número de dígitos (la precisión) de cada coordenada .

Digamos que tiene una geometría grande con 1,000,000 puntos, donde cada punto bidimensional se representa como longitud en ± 180 ° y latitud en ± 90 °:

[-90.07231180399987,29.501753271000098],[-90.06635619599979,29.499494248000133],…

Los números reales pueden tener una precisión arbitraria (en JSON, en JavaScript están limitados por la precisión de IEEE 754 ) y, por lo tanto, un número infinito de dígitos. Pero en la práctica, lo anterior es bastante típico, por lo que cada coordenada tiene 18 dígitos. Incluyendo símbolos adicionales ( [ , ] y , ), cada punto toma como máximo 1 + 18 + 1 + 18 + 1 = 39 bytes para codificar en JSON, y toda la geometría es de aproximadamente 39 * 1,000,000 ≈ 39MB.

Ahora digamos que convertimos estos números reales en enteros: tanto la longitud como la latitud se reducen a los enteros x e y donde 0 ≤ x ≤ 99 y 0 ≤ y ≤ 99. Un mapeo simple entre los puntos de números reales ⟨λ, φ⟩ y las coordenadas de enteros ⟨X, y⟩ es:

x = floor((λ + 180) / 360 * 100);
y = floor((φ + 90) / 180 * 100);

Dado que cada coordenada ahora toma como máximo 2 dígitos para codificar, cada punto toma como máximo 1 + 2 + 1 + 2 + 1 = 7 bytes para codificar en JSON, y toda la geometría es de aproximadamente 7 MB; reducimos el tamaño total en un 82%.

Por supuesto, nada es gratis: si elimina demasiada información, ya no podrá mostrar la geometría con precisión. La regla general es que el tamaño de su cuadrícula debe ser al menos dos veces más grande que el tamaño de pantalla más grande esperado para todo el mapa. Por ejemplo, si está visualizando un mapa del mundo en un espacio de 960 × 500 píxeles, el valor predeterminado de 10,000 × 10,000 ( -q 1e4 ) es una opción razonable.

Por lo tanto, la cuantificación elimina información al reducir la precisión de cada coordenada , ajustando efectivamente cada punto a una cuadrícula regular. Esto reduce el tamaño del archivo TopoJSON generado porque cada coordenada se representa como un entero (como entre 0 y 9.999) con menos dígitos.

Por el contrario, la simplificación elimina la información eliminando puntos , aplicando una heurística que intenta medir la relevancia visual de cada punto y eliminar los puntos menos perceptibles. Existen muchos métodos diferentes de simplificación, pero el método de Visvalingam utilizado por la implementación de referencia de TopoJSON se describe en mi artículo de Simplificación de líneas, por lo que no me repetiré aquí.

Si bien la cuantificación y la simplificación abordan estos dos tipos de información de manera más o menos independiente, existe una complicación adicional: la cuantificación se aplica antes de que se construya la topología , mientras que la simplificación se aplica necesariamente después para preservar la topología . Dado que la cuantificación introduce con frecuencia puntos coincidentes ( [24,62],[24,62],[24,62]… ), y se eliminan puntos coincidentes, la cuantificación también puede eliminar puntos.

La razón por la que se aplica la cuantificación antes de que se construya la topología es que las entradas geométricas a menudo no son topológicamente válidas. Por ejemplo, si toma un shapefile de los condados de Nevada y lo combina con un shapefile del límite de estado de Nevada, las coordenadas en un shapefile pueden no coincidir exactamente con las coordenadas en el otro shapefile. Al cuantificar las coordenadas antes de construir la topología, ajusta las coordenadas a una cuadrícula normal y puede obtener una topología más limpia con menos arcos, con la esperanza de identificar correctamente todos los arcos compartidos. (Por supuesto, si sobre cuantificas, puedes causar demasiados puntos coincidentes y obtener arcos que se intersectan a ti mismo, lo que causa otros problemas).

En una versión futura, quizás 1.5.0, TopoJSON le permitirá controlar la cuantificación antes de que la topología se construya independientemente de la cuantización del archivo TopoJSON de salida. Por lo tanto, podría usar una cuadrícula más fina (¡o ninguna red en absoluto!) Para calcular la topología, luego simplificar, y luego usar una cuadrícula más gruesa apropiada para una pantalla de baja resolución. Por ahora, estos están vinculados, por lo que recomiendo utilizar una cuadrícula más fina (por ejemplo, -q 1e6 ) que produce una topología limpia, a expensas de un archivo ligeramente más grande. Dado que TopoJSON también utiliza coordenadas codificadas en delta, ¡rara vez paga el precio completo de todos los dígitos de todos modos!

Answer 2

Los dos están relacionados, pero tienen diferentes propósitos y resultados.

Creo que la cuantificación colapsa los puntos cercanos en función del parámetro (que sintoniza con la resolución esperada de la vista); no tiene sentido tener una resolución más alta que los píxeles que dibujarán el mapa. Pero no se quita del camino para analizar el camino para determinar la cantidad óptima de puntos necesarios para representar la forma.

La simplificación es un algoritmo que analizará el polígono y reducirá el número de puntos de manera óptima, de modo que se minimice la deformación general del polígono. Básicamente, se puede usar para reducir dramáticamente el número de puntos (y, por lo tanto, el tamaño del archivo) sin un impacto notable en la calidad de la ruta.

Como estudio de caso paralelo, considere una línea recta compuesta de 10 puntos. La cuantificación reducirá el número de puntos (colapsando puntos cercanos o coincidentes) según el valor que use. La simplificación analizará la línea y se dará cuenta de que 8 de los diez puntos se pueden quitar sin cambiar significativamente la forma general del polígono, y reducir la línea a dos puntos (porque no hay deformación de la ruta al eliminar puntos en una línea).

Ver también:

• Referencia de Topojson: https://github.com/mbostock/topojson/wiki/Command-Line-Reference
• Artículo de Simplificación del Sr. Bostock: http://bost.ocks.org/mike/simplify/

Ambos deben usarse en combinación: quatización para reducir el mapa a una cuadrícula de tamaño adecuado, simplificación para optimizar los caminos.