Introducción al algoritmo de adelgazamiento

La clave para el refinamiento de la curva es definir el factor de refinamiento. Diferentes factores de refinamiento determinan la diversidad del algoritmo de refinamiento. En las teorías de adelgazamiento existentes, el factor de adelgazamiento se define por el tamaño del paso, la longitud del segmento de línea y la distancia vertical. El algoritmo de Douglas-Pook (algoritmo DP) generalmente considera una curva completa o un determinado segmento de línea desde una perspectiva global. Su idea básica es:

1) Conectar una línea entre el primer y el último punto de la curva. Línea recta, encuentre la distancia entre todos los puntos en la curva y la línea recta, encuentre el valor de distancia máxima dmax, compare dmax con el umbral predeterminado d:

2) Si dmax

.

Si dmax≥D, conserve el punto de coordenadas correspondiente a dmax, divida la curva en dos partes usando este punto como límite, repita el método anterior para estas dos partes, es decir, repita el paso 1) y el paso 2) hasta se alcanza todo dmax

Obviamente, la precisión del refinamiento de este algoritmo también está relacionada con el umbral. Cuanto mayor sea el umbral, mayor será el grado de simplificación y mayor será el número de puntos reducidos. Por el contrario, cuanto menor es el grado de simplificación, más puntos se retienen y la forma tiende a acercarse más a la curva original.

En comparación con los dos métodos anteriores, la precisión del refinamiento del algoritmo DP mejora significativamente. Primero, su umbral generalmente se toma del error máximo permitido del objeto terrestre correspondiente. En segundo lugar, el algoritmo puede lograr un buen equilibrio entre eliminación y retención, es decir, puede reducir completamente la cantidad de puntos y retener los puntos característicos tanto como sea posible. Sin embargo, debido al uso de bucles o recursiones en la programación, cuando hay muchos puntos, la eficiencia se verá afectada. El principio del método de restricción de distancia vertical es el mismo que el del algoritmo DP, pero en lugar de considerar una curva completa desde una perspectiva general, comienza desde el primer punto y filtra y elimina secuencialmente los puntos redundantes. Es decir, tomando el primer punto como punto de partida, calcule la distancia vertical desde el segundo punto hasta la línea que conecta el primer y tercer punto. Si la distancia es mayor que un cierto umbral, mantenga el segundo punto como nuevo punto de partida y calcule la distancia desde el tercer punto hasta la línea de conexión entre el segundo y el cuarto punto. De lo contrario, elimine el segundo punto, calcule la distancia de conexión desde el tercer punto hasta el primer y cuarto punto, y así sucesivamente hasta el último punto de la curva. El umbral suele ser el error máximo permitido o menos.

El método de restricción de distancia vertical tiene la misma precisión de refinamiento que el algoritmo DP, pero el bucle es simple y fácil de programar. Este es un algoritmo de refinamiento ideal.