Visvalingam-Whyatt polyline simplification algorithm clarification

Question

I'm trying to implement a polyline simplification algorithm. The original article can be found here: http://archive.is/Tzq2. It seems straightforward in concept but I don't understand the sample algorithm (I think it's poorly worded) pseudocode supplied and was hoping someone could provide some insight. From the article, I gathered that the basic idea is to

1. Calculate the effective area (formed by the triangle between three consecutive points on a line) for each point and delete those with 0 area
2. Starting with the smallest area, compare the point's area with a threshold, and if the area is below that threshold, delete it from the polyline.
3. Move to the two adjacent points and recalculate their areas as they've changed
4. Go back to 2 until all point areas under the threshold have been removed

The algorithm is as follows (copied verbatim from the article):

• Compute the effective area of each point Delete all points with zero area and store them in a separate list with this area
• REPEAT
  • Find the point with the least effective area and call it the current point. If its calculated area is less than that of the last point to be eliminated, use the latter's area instead. (This ensures that the current point cannot be eliminated without eliminating previously eliminated points.)
  • Delete the current point from the original list and add this to the new list together with its associated area so that the line may be filtered at run time.
  • Recompute the effective area of the two adjoining points (see Figure 1b).
• UNTIL
  • The original line consists of only 2 points, namely the start and end points.

I'm confused with the 'if' clause in the first step under 'REPEAT'... could anyone clarify?

Answer 1

FWIW Mike Bostock, the creator of d3.js, wrote a tight javascript implementation of this algorithm (Visvalingam's Algorithm).

• Source code
• Demo
• Discussion on Hacker News