Nota: yo soy un programador, no un matemático - por favor, sea amable. No estoy realmente seguro de cómo etiquetar a esta pregunta, no dude en volver a etiquetar como corresponda.Yo estoy usando el de Douglas-Peucker algoritmo para reducir el número de puntos en polígonos (en una aplicación de mapas). El algoritmo toma una tolerancia parámetro que indica cuán lejos estoy dispuesto a desviarse de la original polígono.
Por razones prácticas, a veces siento necesidad de garantizar que la reducción del polígono no exceda de un número predeterminado de puntos. Hay una manera de predecir de antemano el valor de la tolerancia que va a reducir un polígono con N puntos a uno de los N puntos?
Respuesta
¿Demasiados anuncios?
Aquí es un poco no tradicionales variación de Douglas-Peucker algoritmo.
Vamos a dividir una determinada curva en trozos que se aproxima bien por segmentos de línea (dentro de la tolerancia $\varepsilon$). Inicialmente, sólo hay una pieza, que es toda la curva.
- Encontrar la pieza $C$ con la más alta "desviación" $d$, donde la desviación de la curva es la distancia máxima de cualquier punto del segmento de recta que une sus puntos finales.
- Si $d < \varepsilon$, a continuación, todas las piezas tienen suficientemente baja desviación. La parada.
- Deje $p_0$ e $p_1$ ser el punto final de los $C$, e $q$ ser el punto en $C$ que alcanza la desviación $d$. Reemplace $C$ con la pieza entre el $p_0$ e $q$, y la pieza entre el $q$ e $p_1$.
- Repita.
Es fácil ver cómo modificar el paso 2, de modo que el algoritmo produce exactamente $n-1$ piezas, es decir, $n$ puntos, para todas las $n$.
Ejercicios de Cosas soy demasiado perezoso para hacer yo:
- Mostrar que para (casi) cualquier resultado de la modificación del algoritmo, hay una tolerancia correspondiente en el que Douglas-Peucker produciría el mismo resultado.
- El uso de colas de prioridad para la aplicación eficaz del paso 1.
