Dual-Point Smoothing Algorithm

The dual-point algorithm was developed to investigate an interesting variant of the mid-point algorithm. Instead of keeping the mid-point of an edge as a vertex of the output polygon (as in mid-point smoothing), we keep two points. That is, the dual-point algorithm creates a new polygon by successively joining two points from each edge to corresponding points from other edges in the order encountered. This is illustrated more clearly in the following figure. On the left is an illustration of the treatment of an edge in the input polygon, and on the right is an example of the application of such an algorithm. As you can see, this algorithm preserves more of the original shape of the polygon than does its mid-point counterpart.

Here is a more specific definition of this algorithm:

Let P be a polygon given by

P={ (x₁,y₁), (x₂,y₂),...., (x_n,y_n) } where n is the number of vertices in P.

The descendant M of P is defined as

M={ ((x₁+x₂)1/4, (y₁+y₂)1/4), ((x₁+x₂)3/4, (y₁+y₂)3/4), ..., ((x_n+x₁)1/4, (y_n+y₁)1/4), ((x_n+x₁)3/4, (y_n+y₁)3/4) }

Properties:

Advantage:

Simple
Fast
Complexity: O(kn) for k iterations

Disadvantage

Increases number of vertices
Space complexity: O(2^kn) for k iterations

*So, from the point of view of data reduction, this algorithm is not very useful: every time we apply it, we multiply the number of vertices by 2. However, this algorithm constitutes a nice and simple way of curve interpolation from polygons. Check out the Java demo for a nice example! This example (under Attneave) illustrates how this algorithm greatly facilitates inferring the shape of an object described originally by sparse data points.