Polígono autointerseccionado mediante valores extremos

Question

Tengo este polígono

POLYGON((1.2E-15 1.1E-15,1.31E-15 1.21E-15,-180 -90,180 90,1.2E-15 1.1E-15)) 

Utiliza unas coordenadas extremas como (1.2E-15 1.1E-15) y (180 90) Cuando llamo a ST_isValidReason, me dice que el polígono no es válido:

SELECT ST_isValidReason( ST_GeomFromText(
    'POLYGON((1.2E-15 1.1E-15,1.31E-15 1.21E-15,-180 -90,180 90,1.2E-15 1.1E-15))') );
st_isvalidreason       
Self-intersection[-180 -90] 

Pero cuando reduzco la precisión del número de E-15 a E-12 funciona bien:

SELECT ST_isValidReason( ST_GeomFromText(
    'POLYGON((1.2E-12 1.1E-12,1.31E-12 1.21E-12,-180 -90,180 90,1.2E-12 1.1E-12))') );
st_isvalidreason 
Valid Geometry

La pregunta es: ¿es un error de PostGis o no debería usar números como 1.1E-15 para las coordenadas?

Answer 1

Hay dos razones generales para evitar las coordenadas diminutas (o las diferencias diminutas de coordenadas). Como no puedo encontrar (fácilmente) ninguna documentación de PostGIS sobre su formato de almacenamiento interno para coordenadas, les daré ambos.

Representación entera

Muchos SIG convierten las coordenadas en índices en una cuadrícula extremadamente fina de puntos que cubren una región de estudio o "área de interés". Esto les permite realizar todos los cálculos geométricos utilizando integral coordenadas (sólo índices de fila y columna). Los algoritmos de los libros de texto pueden utilizarse casi sin cambios cuando se trata de coordenadas integrales; los requisitos de almacenamiento pueden reducirse a la mitad (un entero ocupa cuatro bytes, mientras que un doble ocupa ocho bytes); y posiblemente los cálculos serán más rápidos en algunos procesadores.

El uso de cuatro bytes (=32 bits) para los valores enteros limita estas cuadrículas a 2^32 filas y columnas. En el caso de las coordenadas geográficas, puede ser necesario almacenar valores de hasta 180. Para que la cuadrícula pueda cubrir tal extensión, el intervalo entre puntos de cuadrícula vecinos no puede ser inferior a 180 / 2^32, lo que equivale aproximadamente a 4,2E-8. Por tanto, los valores entre -2,1E-8 y +2,1E-8 coincidirían todos entre sí y con 0.

Por tanto, si existe la posibilidad de que sus datos sean procesados por un SIG que utilice números enteros para sus cálculos, no puede confiar en que distinga números como 1,2E-15 y 1,31E-15 entre sí.

Cuestiones de coma flotante de doble precisión

Sin embargo, sospecho que éste no es el problema. Aunque el mensaje de error es extraño, una interpretación es que PostGIS detectó una auto-intersección durante el procesamiento secuencial de las coordenadas del polígono y la detección se produjo cuando estaba procesando (-180, -90). Esto significa que piensa (de alguna manera) que hay un problema con las dos primeras aristas.

Las ecuaciones para calcular una autointersección se reducen a invertir una matriz. Los coeficientes de la matriz en este caso son

-180.     -90.
-1.1E-16   -1.1E-16

Esta matriz está extraordinariamente mal condicionada: su valores propios de -180. y -5,5E-17 cubren 18,5 órdenes de magnitud, lo que da un número de condición de 3,3E+18. Este enorme número de condición significa que los procedimientos numéricos para invertir la matriz serán inestables, incluso con aritmética de doble precisión. Es probable que esta inestabilidad condujera a una intersección espuria de las dos primeras aristas del polígono, dando lugar al error.

18,5 órdenes de magnitud es mayor que las 16 a 17 cifras significativas de precisión disponibles con los flotantes de doble precisión. De hecho, no hay ninguna posibilidad de que el software encuentre una solución.

Cuando se cambia E-15 por E-12, el número de condición cae tres órdenes de magnitud. Esta vez el programa puede encontrar una solución, pero probablemente sólo con una cifra significativa. Tal vez por accidente, esa solución no indica una auto-intersección. Pero aún no está fuera de peligro: una cifra significativa es una precisión terrible para el trabajo SIG (o casi cualquier otro trabajo numérico). Habrá preocupación por estos problemas de precisión hasta que se aumente la E-15 a alrededor de E-6 más o menos. Este último valor representa unos 0,11 metros (como máximo): véase https://gis.stackexchange.com/a/8674 para saber cómo se calculó esta distancia. Para casi cualquier aplicación, obtener una precisión de 0,1 metros al cartografiar a escala de toda la Tierra es más que suficiente.