15,558,279 members
Articles / General Programming / Algorithms
Article
Posted 30 Apr 2021

4.2K views
6 bookmarked

# HotPoints - A New Method for 2D Polyline Vertex Smoothing

Rate me:
An alternative method to Catmull-Rom, Chaikin or Bezier curve smoothing methods
This method is based on using ellipses' focus points projected on its diagonal.

## Introduction

In this article, I'll present a new method for 2D polyline vertex smoothing, I named it HotPoints. It's clear that there are well-known methods to get smooth curves by using interpolation or approximation, such as NURBS, splines, Cattmull-Rom, Chaikin or Bezier curves or some filtering techniques. This method is an approximation, and aspect of output results, it is very similar to Chaikin but based-on totally different logic.

Before you go on, I recommend you check this CodeProject article, "2D Polyline Vertex Smoothing" by veen_rp(*).

## The Method

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

If we repeat these steps in an iteration loop, at least 3 times, we will get a nice smooth curve. Certainly! The quality of algorithm is very satisfied.

As you've seen noticed, the main issue or interesting point is to find green points' coordinates. How can we calculate them??

Now, for a short time, we will go back to college years and remember a few geometry topics, such as lines, circles, ellipses, etc. See the below picture:

Actually, the Q points can move over diagonal line, but the best results get while F points and Q points are perpendicular.

So, after some mathematical operations have some eliminations, finally we can calculate the Cartesian coordinates of Q points using these formulas:

```F := 1.0; // F: 0.0 .. 2.0

dx := p2.X - p1.X;
dy := p2.Y - p1.Y;

// a: major axis, b: minor axis
a := dx / 2.82843; // 2*2^0.5 = 2.82843
b := dy / 2.82843;

// O: mid/center point
Ox := (P1.X + P2.X) / 2.0;
Oy := (P1.Y + P2.Y) / 2.0;

Q1.X := Ox - F * a / 1.41421; // sqrt(2) = 1.41421
Q1.y := Oy - F * b / 1.41421;

Q2.X := Ox + F * a / 1.41421;
Q2.y := Oy + F * b / 1.41421;
```

### Using the Code

```////////////////////////////////////////////
// HotPoints approximation
////////////////////////////////////////////

// Calculating hotpoints

for i:=0 to nItera-1 do
begin
k := 0;
for j:=0 to nPoints-1 do
begin
j0 := (j+0 + nPoints) mod nPoints; // circular form
j1 := (j+1 + nPoints) mod nPoints;

p1.X := trunc(pinn[j0].X + 0.5);
p1.Y := trunc(pinn[j0].Y + 0.5);

p2.X := trunc(pinn[j1].X + 0.5);
p2.Y := trunc(pinn[j1].Y + 0.5);

dx := p2.X - p1.X;
dy := p2.Y - p1.Y;

radiX := dx / 2.82843; // 2 * 2^0.5 = 2.82843
radiY := dy / 2.82843; //

Ox := (P1.X + P2.X) / 2.0;
Oy := (P1.Y + P2.Y) / 2.0;

Q1.X := Ox - F * radiX / 1.41421; // sqrt(2) = 1.41421
Q1.y := Oy - F * radiY / 1.41421;
pout[k] := Q1; k := k + 1;

Q2.X := Ox + F * radiX / 1.41421;
Q2.y := Oy + F * radiY / 1.41421;
pout[k] := Q2; k := k + 1;
end; // j

nPoints := k;
for k:=0 to nPoints-1 do pinn[k] := pout[k]; // !!!
end; // iteration, i

// Plotting the curve

for k:=0 to nPoints-1 do
begin
X := trunc(pout[k].X + 0.5);
Y := trunc(pout[k].Y + 0.5);
if (k = 0) then
imgDraw.Canvas.MoveTo(X, Y)
else
imgDraw.Canvas.LineTo(X, Y);
end;
```

Here is an intermediate running state of described steps:

### Comparison

For comparision, see below the results of Chaikin and HotPoints. It seems that they are almost the same.

P.S.: The original test points are borrowed from the above(*) article.

## Conclusion and Points of Interest

In this version, at every iteration, the number of points are doubled. So, be careful about iterations higher than 7/8.

On the other hands, maybe the implementation of the algorithm can be optimized accross the floating point numbers, i.e., implementing integer versions.

## History

• 30th April, 2021: Initial version
• 3rd May, 2021: Update - Version 2

Written By
Software Developer (Senior)
Turkey
a nice person

KISS (keep it simple and smart)

 First Prev Next
 any use case for this kind of smoothing methods? Southmountain17-Jun-21 14:24 Southmountain 17-Jun-21 14:24
 Re: any use case for this kind of smoothing methods? ADMGNS27-Jun-21 4:44 ADMGNS 27-Jun-21 4:44
 Re: any use case for this kind of smoothing methods? Southmountain28-Jun-21 8:17 Southmountain 28-Jun-21 8:17
 looking forward to your new article! diligent hands rule....
 Re: any use case for this kind of smoothing methods? Chris Maunder28-Jun-21 5:49 Chris Maunder 28-Jun-21 5:49
 Re: any use case for this kind of smoothing methods? Southmountain28-Jun-21 8:14 Southmountain 28-Jun-21 8:14
 Re: any use case for this kind of smoothing methods? ADMGNS28-Jun-21 22:50 ADMGNS 28-Jun-21 22:50
 Nice! Chris Maunder16-Jun-21 5:14 Chris Maunder 16-Jun-21 5:14