Visvalingam–Whyatt algorithm: Difference between revisions

Revision as of 13:36, 21 October 2020

Latest revision as of 13:42, 31 May 2024

(19 intermediate revisions by 12 users not shown)

Line 1:

{{Short description|Curve simplification algorithm}}

<!-- Important, do not remove this line before article has been created. -->

[[File:Douglas–Peucker and Visvalingam–Whyatt simplification algorithms.svg|thumb|upright=1.3|Comparison with [[Douglas–Peucker algorithm]]]]

{{AFC submission|t||ts=20200707204845|u=Phoritual|ns=118|demo=}}

The '''Visvalingam-WhyattVisvalingam–Whyatt algorithm''', alsoor known assimply 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, primarily for usage in [[cartographic generalisation]].

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.

== Idea ==

Given a [[Polygonalpolygonal chain|Polygonal Chain]] (often called a Polylinepolyline), the algorithm attempts to find a similar chain composed of fewer points.

Points are assigned an importance based on local conditions, and points are removed from the least important to most important.

In '''Visvalingam's algorithm''', the importance is related to the triangular area added by each point.

== Algorithm ==

Given a chain of [[Two-dimensional space|2d]] points <math>\left\{ p_i \right\} = \left\{ \begin{bmatrix} x_i \\ y_i \end{bmatrix} \right\}</math>, the importance of each interior point is computed by finding the area of the triangle formed by it and its immediate neighbors. This can be done quickly using a matrix [[determinant]].<ref>{{Cite web|title=6.5 -– Applications of Matrices and Determinants|url=https://people.richland.edu/james/lecture/m116/matrices/applications.html#:~:text=The%20legs%20of%20the%20three,/%202%20=%209/2.|access-date=2020-07-07|website=people.richland.edu}}</ref>. Alternatively, the equivalent formula below can be used<ref>{{Cite web|title=Untitled Document|url=https://people.richland.edu/james/lecture/m116/matrices/area.html|access-date=2020-07-07|website=people.richland.edu}}</ref>.

: <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 too large enough to not neglect.

=== Pseudocode ===

TODO(Phoritual)

'''

'''function''' TriangularArea(Point p1, Point p2, Point p3)

// Return the area enclosed by the triangle p1-p2-p3

'''return''' abs(

p1.x * p2.y + p2.x * p3.y + p3.x * p1.y

- p1.x * p3.y - p2.x * p1.y - p3.x * p2.y

) / 2

'''end'''

'''function''' VisvalingamWhyatt(List[Point] ps)

// TODO(woursler): Write pseudocode

// Return the result

'''return''' ResultList[]

'''end'''

=== Advantages ===

Line 43 ⟶ 25:

=== Disadvantages ===

[[Image:Douglas-Peucker animated.gif|thumb|right|Points with equivalent "importance" may be of different topological importance.]]

* The algorithm does not differentiate between sharp spikes and shallow features, meaning that it will clean up sharp spikes that may be important.

Line 59 ⟶ 39:

* [[Opheim simplification algorithm|Opheim simplification]]

* [[Lang simplification algorithm|Lang simplification]]

* [[Zhao SaalfeldZhao–Saalfeld algorithm|Zhao-Saalfeld]]

== 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}}

== References ==

{{reflist}}

== External links ==

* [https://www.jasondavies.com/simplify/ Interactive example of the algorithm]

{{DEFAULTSORT:Visvalingam–WhyattVisvalingam-Whyatt algorithm}}

* [https://hull-repository.worktribe.com/output/459275 1995 Paper proposing the method.]

[[:Category:Geometric algorithms]]

{{DEFAULTSORT:Visvalingam–Whyatt algorithm}}

[[:Category:ComputerDigital graphicssignal algorithmsprocessing]]

[[:Category:Geometric algorithms]]

[[:Category:Digital signal processing]]

[[:Category:Articles with example pseudocode]]

[[Category:Computer graphics algorithms]]

{{Drafts moved from mainspace|date=March 2019}}

[[:Category:Articles with example pseudocode]]