Ramer–Douglas–Peucker-algoritm

Ramer –Douglas–Peucker-algoritmen , även känd som Douglas–Peucker-algoritmen och iterativ slutpunktsanpassningsalgoritm , är en algoritm som decimerar en kurva som består av linjesegment till en liknande kurva med färre punkter. Det var en av de tidigaste framgångsrika algoritmerna som utvecklats för kartografisk generalisering .

Aning

Syftet med algoritmen är, givet en kurva sammansatt av linjesegment (vilket också kallas en polylinje i vissa sammanhang), att hitta en liknande kurva med färre punkter. Algoritmen definierar "olik" baserat på det maximala avståndet mellan den ursprungliga kurvan och den förenklade kurvan (dvs. Hausdorff-avståndet mellan kurvorna). Den förenklade kurvan består av en delmängd av de punkter som definierade den ursprungliga kurvan.

Algoritm

Förenkla en bitvis linjär kurva med Douglas-Peucker-algoritmen.

Startkurvan är en ordnad uppsättning punkter eller linjer och avståndsdimensionen ε > 0 .

Algoritmen delar upp linjen rekursivt . Inledningsvis ges alla poäng mellan första och sista punkten. Den markerar automatiskt den första och sista punkten som ska behållas. Den hittar då den punkt som är längst bort från linjeavsnittet med den första och sista punkten som slutpunkter; denna punkt är uppenbarligen längst bort på kurvan från det approximerande linjesegmentet mellan ändpunkterna. Om punkten är närmare än ε till linjesegmentet kan alla punkter som för närvarande inte är markerade för att behållas kasseras utan att den förenklade kurvan är sämre än ε .

Om punkten längst bort från linjesegmentet är större än ε från approximationen måste den punkten behållas. Algoritmen kallar sig rekursivt med den första punkten och den längsta punkten och sedan med den längsta punkten och den sista punkten, vilket inkluderar att den längsta punkten markeras som hållen.

När rekursionen är avslutad kan en ny utgångskurva genereras bestående av alla och endast de punkter som har markerats som bevarade.

Effekten av att variera epsilon i en parametrisk implementering av RDP

Icke-parametrisk Ramer–Douglas–Peucker

Valet av ε är vanligtvis användardefinierat. Liksom de flesta metoder för linjeanpassning, polygonal approximation eller dominerande punktdetektering, kan den göras icke-parametrisk genom att använda felgränsen på grund av digitalisering och kvantisering som ett avslutningsvillkor.

Pseudokod

Förutsatt att ingången är en en-baserad array:

 
  
    
      0
      0
      
            
             
            
              
              
        
    

      

    
        
        
           
           

        
             
      
           
    
    
      # källa: https://karthaus.nl/rdp/  function  DouglasPeucker  (  PointList  [],  epsilon  )  # Hitta punkten med det maximala avståndet  dmax  =  index  =  end  =  length  (  PointList  )  för  i  =  2  till  (  end  -  1  )  {  d  =  perpendicularDistance  (  PointList  [  i  ],  Line  (  PointList  [  1  ],  PointList  [  end  ]))  if  (  d  >  dmax  )  {  index  =  i  dmax  =  d  }  }  ResultList  []  =  tom  ;  # Om maxavståndet är större än epsilon, förenkla rekursivt  if  (  dmax  >  epsilon  )  {  # Rekursivt anrop  recResults1  []  =  DouglasPeucker  (  PointList  [  1.  ..  index  ],  epsilon  )  recResults2  []  =  DouglasPeucker  (  PointList  [  index  ...  end  ],  epsilon  )  # Bygg resultatlistan  ResultList  []  =  {  recResults1  [  1.  ..  length  (  recResults1  )  -  1  ],  recResults2  [  1.  ..  length  (  recResults2  )]}  }  else  {  ResultList  []  =  {  PointList  [  1  ],  PointList  [  end  ]}  }  # Returnera resultatet  return  ResultList  []

Ansökan

Algoritmen används för bearbetning av vektorgrafik och kartografisk generalisering . Det bevarar inte alltid egenskapen icke-självskärning för kurvor, vilket har lett till utvecklingen av variantalgoritmer.

Algoritmen används i stor utsträckning inom robotteknik för att utföra förenkling och avbrutning av avståndsdata som förvärvats av en roterande avståndsskanner ; inom detta fält är den känd som split-and-merge-algoritmen och tillskrivs Duda och Hart .

Komplexitet

Löptiden för denna algoritm när den körs på en polylinje som består av n – 1 segment och n hörn ges av återkommande T ( n ) = T ( i + 1) + T ( n − i ) + O ( n ) där i = 1, 2,..., n − 2 är värdet på index i pseudokoden. I värsta fall är i = 1 eller i = n − 2 vid varje rekursiv anrop och denna algoritm har en körtid på Θ ( n 2 ) . I bästa fall är i = n / 2 eller i = n ± 1 / 2 vid varje rekursiv anrop, i vilket fall körtiden har den välkända lösningen (via mastersatsen för divide-and-ereg-repetitioner ) av O ( n log n ) .

Genom att använda (helt eller semi-) dynamiska konvexa skrovdatastrukturer kan den förenkling som utförs av algoritmen åstadkommas på O ( n log n ) tid.

Liknande algoritmer

Alternativa algoritmer för linjeförenkling inkluderar:

Se även

Vidare läsning

  • Ramer, Urs (1972). "En iterativ procedur för polygonal approximation av plana kurvor". Datorgrafik och bildbehandling . 1 (3): 244–256. doi : 10.1016/S0146-664X(72)80017-0 .
  • Douglas, David; Peucker, Thomas (1973). "Algoritmer för att minska antalet punkter som krävs för att representera en digitaliserad linje eller dess karikatyr". Den kanadensiske kartografen . 10 (2): 112–122. doi : 10.3138/FM57-6770-U75U-7727 .
  • Hershberger, John; Snoeyink, Jack (1992). Påskynda Douglas–Peucker Line-Simplification Algorithm . Handlingar från det 5:e symposiet om datahantering. sid. 134–143. UBC Tech Report TR-92-07 tillgänglig på http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07
  • Duda, RO; Hart, PE (1973). Mönsterklassificering och scenanalys . New York: Wiley. Arkiverad från originalet 2011-07-15.
  • Visvalingam, M.; Whyatt, JD (1992). Linjegeneralisering genom upprepad eliminering av det minsta området (Teknisk rapport). Diskussionspapper. Kartografiska informationssystemforskningsgrupp (CISRG), University of Hull. 10.

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Ramer–Douglas–Peucker_algorithm&oldid=1107863277 "