Visvalingam–Whyatt algorithm

<h2 id="idea">Idea</h2>
<p>Given a <a href="/facts/Polygonal_chain/GRQ6BMQS">polygonal chain</a> (often called a polyline), the algorithm attempts to find a similar chain composed of fewer points.
</p><p>Points are assigned an importance based on local conditions, and points are removed from the least important to most important.
</p><p>In Visvalingam's algorithm, the importance is related to the triangular area added by each point.
</p>
<h2 id="algorithm">Algorithm</h2>
<p>Given a chain of <a href="/facts/Two-dimensional_space/f4b397W8">2d</a> points 
  
    
      
        
          {
          
            p
            
              i
            
          
          }
        
        =
        
          {
          
            
              [
              
                
                  
                    
                      x
                      
                        i
                      
                    
                  
                
                
                  
                    
                      y
                      
                        i
                      
                    
                  
                
              
              ]
            
          
          }
        
      
    
    {\displaystyle \left\{p_{i}\right\}=\left\{{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}}\right\}}
  
, 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 <a href="/facts/Determinant/eGYqJ2TF">determinant</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> Alternatively, the equivalent formula below can be used<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>

A
          
            i
          
        
        =
        
          
            1
            2
          
        
        
          |
          
            
              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
              
            
          
          |
        
      
    
    {\displaystyle 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|}

<p>The minimum importance point 
  
    
      
        
          p
          
            i
          
        
      
    
    {\displaystyle p_{i}}
  
 is located and marked for removal (note that 
  
    
      
        
          A
          
            i
            −
            1
          
        
      
    
    {\displaystyle A_{i-1}}
  
 and 
  
    
      
        
          A
          
            i
            +
            1
          
        
      
    
    {\displaystyle A_{i+1}}
  
 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 large enough to not neglect.
</p>
<h3>Advantages</h3>
<ul><li>The algorithm is easy to understand and explain, but is often competitive with much more complex approaches.</li>
<li>With the use of a <a href="/facts/Priority_queue/1uXVo4Uf">priority queue</a>, the algorithm is performant on large inputs, since the importance of each point can be computed using only its neighbors, and removing a point only requires recomputing the importance of two other points.</li>
<li>It is simple to generalize to higher dimensions, since the area of the triangle between points has a consistent meaning.</li></ul>
<h3>Disadvantages</h3>
<ul><li>The algorithm does not differentiate between sharp spikes and shallow features, meaning that it will clean up sharp spikes that may be important.</li>
<li>The algorithm simplifies the entire length of the curve evenly, meaning that curves with high and low detail areas will likely have their fine details eroded.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Curve_fitting/zrLKw6Xj">Curve fitting</a></li></ul>
<p>Alternative algorithms for line simplification include:
</p>
<ul><li><a href="/facts/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm/VT31304N">Ramer–Douglas–Peucker</a></li>
<li>Reumann–Witkam</li>
<li>Opheim simplification</li>
<li>Lang simplification</li>
<li>Zhao–Saalfeld algorithm</li></ul>

Notes

Bibliography
<ul><li>Visvalingam, M.; Whyatt, J. D. (1993). <a href="https://hull-repository.worktribe.com/preview/376364/000870493786962263.pdf">"Line generalisation by repeated elimination of points"</a> (PDF). <i>The Cartographic Journal</i>. 30 (1): 46–51. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1179%2F000870493786962263">10.1179/000870493786962263</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0008-7041">0008-7041</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.jasondavies.com/simplify/">Interactive example of the algorithm</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>"6.5 – Applications of Matrices and Determinants". people.richland.edu. Retrieved 2020-07-07. <a href="https://people.richland.edu/james/lecture/m116/matrices/applications.html#:~:text=The%20legs%20of%20the%20three,/%202%20=%209/2." target="_blank">https://people.richland.edu/james/lecture/m116/matrices/applications.html#:~:text=The%20legs%20of%20the%20three,/%202%20=%209/2.</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>"Untitled Document". people.richland.edu. Retrieved 2020-07-07. <a href="https://people.richland.edu/james/lecture/m116/matrices/area.html" target="_blank">https://people.richland.edu/james/lecture/m116/matrices/area.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Visvalingam–Whyatt algorithm open-in-new

Visvalingam–Whyatt algorithm