Search code examples
algorithmpolylinesimplification

Visvalingam-Whyatt polyline simplification algorithm clarification

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?

Solution

  • The essence of the algorithm is ranking of points by their significance. Significance of the point is approximated by its effective area.

    Suppose you have eliminated Point A and then recalculated the effective area of Point B. The new area can be larger or smaller than the old one. It can be smaller than the effective area of A. However, the algorithm still views B as more significant than A.

    The purpose of the if clause is to ensure that Point B is more significant than A in the final list, that's all.