Visvalingam–Whyatt-algoritm

Visvalingam –Whyatt-algoritmen , även känd som Visvalingams algoritm , är en algoritm som decimerar en kurva som består av linjesegment till en liknande kurva med färre punkter.

Aning

Med tanke på en polygonal kedja (ofta kallad en polylinje), försöker algoritmen hitta en liknande kedja som består av färre punkter.

Poäng tilldelas en betydelse utifrån lokala förhållanden och poäng tas bort från det minst viktiga till det viktigaste.

I Visvalingams algoritm är betydelsen relaterad till det triangulära området som adderas av varje punkt.

Algoritm

Givet en kedja av 2d punkter $\left\{p_{i}\right\}=\left\{{\begin{bmatrix}x_{i}\ \y_{i}\end{bmatrix}}\right\}$ , vikten av varje inre punkt beräknas genom att hitta arean av triangeln som bildas av den och dess omedelbara grannar. Detta kan göras snabbt med hjälp av en matrisdeterminant . Alternativt kan motsvarande formel nedan användas

$A_{i}={\frac {1}{2}}\left|x_{i-1}y_{i}+x_{i}y_{i+1}+x_{i+1}y_ {i-1}-x_{i-1}y_{i+1}-x_{i}y_{i-1}-x_{i+1}y_{i}\right|$

Minimiviktspunkten $p_{i}$ är lokaliserad och markerad för borttagning (observera att $A_{i-1}$ och $A_{i+1 }$ måste beräknas om). Denna process upprepas tills antingen det önskade antalet poäng har uppnåtts, eller så är bidraget från den minst viktiga punkten tillräckligt stort för att inte försumma.

Fördelar

• Algoritmen är lätt att förstå och förklara, men är ofta konkurrenskraftig med mycket mer komplexa tillvägagångssätt.
• Med användning av en prioritetskö fungerar algoritmen på stora ingångar, eftersom vikten av varje punkt kan beräknas med endast dess grannar, och att ta bort en punkt endast kräver omräkning av betydelsen av två andra punkter.
• Det är enkelt att generalisera till högre dimensioner, eftersom arean av triangeln mellan punkter har en konsekvent betydelse.

Nackdelar

• Algoritmen skiljer inte på skarpa spikar och grunda egenskaper, vilket innebär att den kommer att rensa upp skarpa spikar som kan vara viktiga.
• Algoritmen förenklar hela kurvans längd jämnt, vilket innebär att kurvor med höga och låga detaljområden sannolikt kommer att få sina fina detaljer eroderade.

Se även

• Kurvanpassning

Alternativa algoritmer för linjeförenkling inkluderar:

• Ramer–Douglas–Peucker
• Reumann–Witkam
• Opheim förenkling
• Lång förenkling
• Zhao–Saalfeld-algoritm

externa länkar

• 1992 Artikel som föreslår metoden.