Visvalingam-Whyatt polyline simplification algorit

问题:

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?

回答1:

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.

回答2:

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

回答3:

I was confused by this too, went back and read the article again, and afaict it's not needed if you're removing points as you go - aka if you're doing a one-off simplification with a fixed area threshold. afaict the javascript implementation works this way, so it actually doesn't need the 'if' statement (but it has it anyway, oh well).

The 'if' statement is needed if you're keeping all the points around. In that case, you're storing the 'effective area' with each point so that later you can filter them, perhaps using an interactive slider that controls the # of output points. By storing that larger effective area, you preserve the proper ordering.