15,741,752 members
Articles / General Programming / Algorithms
Article
Posted 28 Jun 2021

8.9K views
17 bookmarked

# Smart Decimation: Polyline Simplification and Smoothing

Rate me:
6 Aug 2022BSD3 min read
A new method for 2D polyline simplification and also smoothing that alternative to Douglas-Peucker and curvature-based simplification algorithms
This method is a kind of resampling technique that can be used for upsampling (interpolation) and downsampling (decimation). In this post, I'll demonstrate for only decimation lateral (side?).

## Introduction

In this article, I'll present a new method for 2D polyline simplification and also smoothing, I named it Smart Decimation. It's clear that there are well-known methods to get simplified curves by using different methods. For example, in signal processing, multirate resampling using FFT by adding zeros or removing same samples.

As a summary, here are these:

• Douglas-Peucker algorithm
• Visvalingam-Whyatt algorithm
• Curvature-based simplification algorithm
• Maximum Squared Distance algorithm
• Reumann-Witkam algorithm
• Opheim algorithm
• Lang algorithm
• Nth point
• Distance between points
• Perpendicular distance

Before you go on, I recommend that you must first check out this CodeProject article "Polyline Simplification" by Elmar de Koning.

## The Method

Suppose we have 3 points and we want to get 5 points (i.e., interpolation). Or, we have 5 points and we want to get 3 points (i.e., decimation). This method can be used for both situations. Here, we use it for reduction.

This method is actually very similar to bilinear interpolation but it is significantly different at all. We know that, in image processing, there are well-known algortihms for image resizing:

• Nearest neighbor i.e., direct copy
• Bilinear interpolation
• Bicubic interpolation
• Sinc/Lanczos interpolation

Visually, the quality of algorithm is better than bilinear but worse than bicubic, for images. When upsizing, it has less or no artifacts (i.e., aliasing, blurring, edge halos) than others.

The best way to explain the underlying logic is to use step by step illustration graphics.

## Another Explanation (1D Data)

For example, think that we have 11 values: 41, 79, 9, 36, 11, 33, 23, 46, 36, 88, 89. Now, we want to get only 3 values without losing the main features of data set.

Steps are very simple and easy: Kronicker multiply, then regroup the data and finally calc the average of these data groups.

If we apply these steps, we'll get the result as 41.7273, 25.7273, 66.4545.

NOTE: To be clear, number of input values and number of output values are must pseudo-primes. Otherwise, it only repeats the input values and result will be same as (bi)linear method.

## Implementation

Here is the implementation code that adapted for 2D points arrays.

Delphi
```type
TPointArr = array of TPoint;
....

procedure SmartDecimation(source: TPointArr; mSource: integer;
var dest: TPointArr; nDest: integer);
// Not allowed to use for commercial apps without permissions.
var
m, n, k, p, q: integer;
t1, t2: double;
begin
if ( (mSource < 3) or (nDest < 3) ) then Exit;
t1 := 0;
t2 := 0;
for m:=0 to mSource-1 do
begin
for n:=0 to nDest-1 do
begin
k := m * nDest + n;
t1 := t1 + source[m].X;
t2 := t2 + source[m].Y;
p := k div mSource;
q := k mod mSource;
if (q = mSource-1) then
begin
dest[p].X := trunc(t1 / mSource + 0.5);
dest[p].Y := trunc(t2 / mSource + 0.5);
t1 := 0;
t2 := 0;
end;
end;
end;
end;```

## Using the Code

The algorithm has been implemented as a procedure `SmartDecimation`. It takes an input array of points and number of input points (M), and an output array of points and number of output points (N). So, it performs M/N resampling.

Before using the procedure, you have to initialize all parameters.

## Examples and Comparison

And, here are some examples and results:

 Original Smart Decimation (auto mode) Smart Decimation (manual mode) Douglas-Peucker

## Conclusion and Points of Interest

As we have seen above, this method can be used for both simplification and also smoothing of 2D polylines. I think this feature seems to have an advantage against Douglas-Peucker in some situations.

On the other hand, this method can be used for image resizing, but, this is out of scope for this article. So, I've put only an example/result here:

 Original image Resized image with SID

## History

• 28th June, 2021: Initial version

Written By
Software Developer (Senior)
Turkey
a nice person

KISS (keep it simple and smart)

## Comments and Discussions

 First Prev Next
 Source code missing Member 1334495925-May-22 4:30 Member 13344959 25-May-22 4:30
 Excellent article and application. The source code folder missing the code and library for easy implementation in other projects. Would be great if updated. Thanks!
 Re: Source code missing Member 1334495926-May-22 17:50 Member 13344959 26-May-22 17:50
 Re: Source code missing ADMGNS3-Jun-22 10:36 ADMGNS 3-Jun-22 10:36
 what about 3D polylines ? Member 1160459929-Jun-21 6:35 Member 11604599 29-Jun-21 6:35
 Re: what about 3D polylines ? ADMGNS30-Jun-21 5:30 ADMGNS 30-Jun-21 5:30
 KISS ! Member 1160459929-Jun-21 6:35 Member 11604599 29-Jun-21 6:35
 Re: KISS ! ADMGNS30-Jun-21 5:30 ADMGNS 30-Jun-21 5:30
 Re: KISS ! miktro5-Jul-21 0:16 miktro 5-Jul-21 0:16
 Re: KISS ! ADMGNS11-Jul-21 9:44 ADMGNS 11-Jul-21 9:44
 Re: KISS ! Member 147438877-Aug-22 20:53 Member 14743887 7-Aug-22 20:53
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Sep-23 15:46 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.