Algoritmul Ramer-Douglas-Peucker

Această intrare sau secțiune despre matematică nu citează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor . Urmați sfaturile de proiectare de referință .

Această intrare sau secțiune despre subiecte de geometrie și informatică nu este încă formatată conform standardelor . Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia . Urmați sfaturile din desenele de referință 1 , 2 .

Algoritmul Ramer - Douglas - Peucker (RDP) este un algoritm pentru reducerea numărului de puncte dintr-o linie întreruptă . Forma inițială a algoritmului a fost sugerată în 1972 de Urs Ramer și în 1973 de David Douglas și Thomas Peucker și mai mulți alții în deceniile următoare. Acest algoritm este, de asemenea, cunoscut sub numele de algoritm Douglas - Peucker, potrivirea iterativă a punctului final și divizarea și îmbinarea .

Idee

Având în vedere o aproximare liniară în bucăți a unei curbe, scopul algoritmului este de a găsi o aproximare de dimensiune redusă, adică cu mai puține segmente, care nu este diferită de aproximarea inițială. Algoritmul definește „diferențierea” ca distanța maximă dintre curba inițială și curba simplificată. Curba simplificată constă dintr-un subset de puncte ale curbei originale.

Algoritm

Simplificarea unei linii întrerupte cu algoritmul Douglas - Peucker. 0. Linia originală; 1. linia a este o primă aproximare a originalului, dar distanța b dintre a și punctul c depășește distanța maximă. 2. Următoarea aproximare include punctul c . 2. și 3. Continuați cu celelalte puncte până la linia simplificată (4.)

Un pseudocod pentru acest algoritm este prezentat mai jos; se presupune că intrarea este o matrice începând cu indexul 1.

 funcție DouglasPeucker (PointList [], epsilon)
    // găsiți punctul cu cea mai mare distanță
    dmax = 0
    index = 0
    end = length (PointList)
   // dacă are mai puțin de 3 puncte nu este nimic de simplificat și returnăm matricea (cu 1 sau 2 puncte)
    if (end <3) returnează PointList []
    pentru i = 2 până la (sfârșitul - 1) {
        d = shortestDistanceToSegment (PointList [i], Line (PointList [1], PointList [end])) 
        if (d> dmax) {
            index = i
            dmax = d
        }
    }
    // dacă distanța maximă este mai mare decât epsilon, simplificăm recursiv
    if (dmax> epsilon) {
        // Apeluri recursive
        recResults1 [] = DouglasPeucker (PointList [1 ... index], epsilon)
        recResults2 [] = DouglasPeucker (PointList [index ... end], epsilon)
 
        // Concatenăm listele rezultate
        ResultList [] = {recResults1 [1 ... end-1] recResults2 [1 ... end]}
    } altceva {
       // să luăm cele două puncte extreme
        ResultList [] = {PointList [1], PointList [end]}
    }
    // Returnează rezultatul
    returnează Lista de rezultate []
Sfârșit

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică