Wikipedia

Diferencia entre revisiones de «Algoritmo de Ramer–Douglas–Peucker»

Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Jespa (discusión · contribs.)
2132 ediciones
Línea 7:
== Algoritmo ==
[[Image:Douglas-Peucker animated.gif|thumb|right|Simplificando una curva definida a trozos con el algortmo de Douglas-Peucker.]]
La curva inicial es una lista ordenada de puntos o segmentos y laun dimensiónumbral distanciade error ''ε > 0.
 
El algoritmo construye una aproximación de la curva inicial mediante un proceso recursivo. Se toma como solución inicial el segmento que une los dos puntos extremos de la curva. Entonces, se busca el punto más alejado de dicho segmento (peor punto).
El algoritmo divide el segmento recursivamente. Inicialmente se dan todos los puntos entre los extremos de la curva. Automáticamente los extremos son marcados como solución final. Entonces, busca el punto más alejado del segmento definido por el punto inicial y final de la curva (obviamente este punto será el más alejado de la curva aproximada por los dos puntos iniciales). Si el punto está más cerca del segmento que la distancia ε entonces ningún punto será guardado ya que la nueva curva simplificada sería peor que ε.
* Si el peor punto está más cerca del segmento que el umbral de distancia ε, entonces se termina el proceso. Es seguro que el resto de puntos de la curva están a menor distancia que el umbral ε, y por lo tanto todos los puntos de la curva (salvo los extremos) pueden ser descartados.
 
* Si el peor punto está más alejado que ε, entonces ese punto debe permanecer en la simplificación. El algoritmo sehace llamados recursivamentellamadas recursivas a sí mismo, primeropara calcular la aproximación de dos curvas de menor longitud. Una con los puntos entre el primer y el peor punto y despuésotra con ellos últimopuntos yentre el peor punto y el punto final de la curva.
Cuando se completa la recursión la nueva curva puede ser generada a partir de solo los puntos que han permanecido tras haber aplicado el algoritmo.▼
 
▲Cuando se completa la recursión la nueva curva puede ser generada a partir de solo los puntos que han permanecido tras haber aplicado el algoritmo.
 
=== RDP no paramétrico ===
La elección de ''ε'' es normalmente una distancia elegida comopor 1-2...nel pixelsusuario. Como la mayoría de métodos de ajuste de línea, aproximación poligonal o detección del punto dominante, pueden seres posible realizar una versión no paramétricosparamétrica del algoritmo, calculando un valor para ''ε'' basándose en el uso del error vinculado debido a la digitalización o la cuantificación como condición final.
 
=== Pseudocódigo ===
Obtenido de «https://es.wikipedia.org/wiki/Algoritmo_de_Ramer–Douglas–Peucker»