Content deleted Content added
Gif explaining Ramer-Douglass-Peucker was a red herring on a page about a different algorithm. |
make larger |
||
| (5 intermediate revisions by 2 users not shown) | |||
Line 1:
{{Short description|Curve simplification algorithm}}
The '''Visvalingam–Whyatt algorithm''', also known as the '''Visvalingam's algorithm''', is an algorithm that [[Decimation (signal processing)|decimates]] a curve composed of line segments to a similar curve with fewer points.▼
[[File:Douglas–Peucker and Visvalingam–Whyatt simplification algorithms.svg|thumb|upright=1.3|Comparison with [[Douglas–Peucker algorithm]]]]
▲The '''Visvalingam–Whyatt algorithm''',
== Idea ==
Given a [[polygonal chain]] (often called a
Points are assigned an importance based on local conditions, and points are removed from the least important to most important.
Line 14 ⟶ 16:
: <math>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|</math>
The minimum importance point <math>p_i</math> is located and marked for removal (note that <math>A_{i-1}</math> and <math>A_{i+1}</math> will need to be recomputed). This process is repeated until either the desired number of points is reached, or the contribution of the least important point is
=== Advantages ===
Line 40 ⟶ 42:
== References ==
;Notes
<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->
{{reflist}}
;Bibliography
* {{Cite journal |last=Visvalingam |first=M. |last2=Whyatt |first2=J. D. |year=1993 |title=Line generalisation by repeated elimination of points |url=https://hull-repository.worktribe.com/preview/376364/000870493786962263.pdf |journal=The Cartographic Journal |language=en |volume=30 |issue=1 |pages=46–51 |doi=10.1179/000870493786962263 |issn=0008-7041}}
== External links ==
* [https://www.jasondavies.com/simplify/ Interactive example of the algorithm]
{{DEFAULTSORT:Visvalingam-Whyatt algorithm}}
| |||