Algoritmo Ramer-Douglas-Peucker
![Niente fonti!](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Question_book-4.svg/45px-Question_book-4.svg.png)
![Questa voce è da wikificare](http://upload.wikimedia.org/wikipedia/commons/thumb/c/ce/Wikitext.svg/50px-Wikitext.svg.png)
L'algoritmo Ramer–Douglas–Peucker (RDP) è un algoritmo per la riduzione del numero di punti in una linea spezzata. La forma iniziale dell'algoritmo fu suggerita nel 1972 da Urs Ramer e nel 1973 da David Douglas e Thomas Peucker e diverse altre nei successivi decenni. Questo algoritmo è anche conosciuto sotto il nome di algoritmo Douglas–Peucker, iterative end-point fit e split-and-merge.
Idea
Assegnata un'approssimazione lineare a tratti di una curva, lo scopo dell'algoritmo è trovare un'approssimazione di dimensione ridotta, ovvero con meno segmenti, che non sia dissimile dall'approssimazione originale. L'algoritmo definisce la "dissimilarità" come massima distanza tra la curva originale e la curva semplificata. La curva semplificata consiste di un sottoinsieme dei punti della curva originale.
Algoritmo
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Douglas_Peucker.png/220px-Douglas_Peucker.png)
Uno pseudocodice per questo algoritmo è riportato di seguito; si assume che l'input sia un array che parte dall'indice 1.
function DouglasPeucker(PointList[], epsilon) // troviamo il punto con la massima distanza dmax = 0 index = 0 end = length(PointList) //se ha meno di 3 punti non vi è nulla da semplificare e torniamo l'array (di 1 o 2 punti) if (end < 3 ) return PointList[] for i = 2 to ( end - 1) { d = shortestDistanceToSegment(PointList[i], Line(PointList[1], PointList[end])) if ( d > dmax ) { index = i dmax = d } } // se la massima distanza è maggiore di epsilon, semplifichiamo ricorsivamente if ( dmax > epsilon ) { // Chiamate ricorsiva recResults1[] = DouglasPeucker(PointList[1...index], epsilon) recResults2[] = DouglasPeucker(PointList[index...end], epsilon) // Concateniamo le liste risultanti ResultList[] = {recResults1[1...end-1] recResults2[1...end]} } else { //prendiamo i due punti estremi ResultList[] = {PointList[1], PointList[end]} } // Ritorna il risultato return ResultList[] end
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)