Visvalingam's algorithm

On each iteration, the algorithm eliminates the least important triangular area subtended by a point and its neighbours. This demonstration program displays the points in reverse order, starting with the more important shape defining points. Note :

  • the tendency to include the larger features before smaller ones.
  • the scope for faster recognition of the emerging form.
  • the scope for staged transmission of vector data to support Internet browsing.
  • the scope for segmenting and structuirng even convoluted lines into their constituent parts for automatic recognition.

This demo only cycles through the first 60 points. The impact of the remaining points cannot be seen at this scale of display.

The input line is shown in grey. The RIGHT and LEFT arrow keys are used to add and remove points respectively. Click within the applet panel to gain focus before using these keys.

The red lines are those which were already on display. The blue line is the line which is being added or removed.

© Dr Mahes Visvalingam, 1999
... Department of Computer Science, University of Hull, HULL, HU6 7RX, UK.
... M.Visvalingam@dcs.hull.ac.uk