Click here to Skip to main content
15,031,368 members
Articles / General Programming / Algorithms
Posted 30 Apr 2021


4 bookmarked

HotPoints - A New Method for 2D Polyline Vertex Smoothing

Rate me:
Please Sign up or sign in to vote.
5.00/5 (8 votes)
30 Apr 2021BSD2 min read
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.



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.

Step 1 Step 2
Step 3 Step 4
Step 5 Step 6, result

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:

Image 8

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

Let's lead with code!

// HotPoints approximation

// Calculating hotpoints

for i:=0 to nItera-1 do
  k := 0;
  for j:=0 to nPoints-1 do
    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
  X := trunc(pout[k].X + 0.5);
  Y := trunc(pout[k].Y + 0.5);
  if (k = 0) then
    imgDraw.Canvas.MoveTo(X, Y)
    imgDraw.Canvas.LineTo(X, Y);

Here is an intermediate running state of described steps:



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

Chaikin HotPoints

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.


  1. Subdivision Curves and Surfaces
  2. "2D Polyline Vertex Smoothing"


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


This article, along with any associated source code and files, is licensed under The BSD License


About the Author

Software Developer (Senior)
Turkey Turkey
a nice person Smile | :)

KISS (keep it simple and smart)

Comments and Discussions

Questionany use case for this kind of smoothing methods? Pin
Southmountain17-Jun-21 13:24
MemberSouthmountain17-Jun-21 13:24 
AnswerRe: any use case for this kind of smoothing methods? Pin
ADMGNS27-Jun-21 3:44
professionalADMGNS27-Jun-21 3:44 
GeneralRe: any use case for this kind of smoothing methods? Pin
Southmountain28-Jun-21 7:17
MemberSouthmountain28-Jun-21 7:17 
AnswerRe: any use case for this kind of smoothing methods? Pin
Chris Maunder28-Jun-21 4:49
cofounderChris Maunder28-Jun-21 4:49 
I would say it's not even the plotting that makes this interesting, but the data analysis. In 2D it could be a case where you need to find the area of a region, and the error introduced by smoothing could well and truly be offset by the massive reduction in computational time achieved by reducing the number of points. For 1-D (time series) it's the same thing: often you smooth data to remove noise before performing analysis, and something like this could provide a smoothing / data reduction method that maintains enough of the "flavour" of the data.

For some of my work I need to smooth time series data because I'm looking for trends in systems where changes occur over 10s of seconds, yet the data is 1-second data. Smoothing by rolling average, or bucketing the data into 10 second chunks sort of works, but you can often lose some points of interest.

Another algorithm I've used is the Largest-Triangle-3-Buckets which is great at keeping this 'flavour' (The author even did a random sample to gauge how people felt about the algorithm!)
Chris Maunder

GeneralRe: any use case for this kind of smoothing methods? Pin
Southmountain28-Jun-21 7:14
MemberSouthmountain28-Jun-21 7:14 
GeneralRe: any use case for this kind of smoothing methods? Pin
ADMGNS28-Jun-21 21:50
professionalADMGNS28-Jun-21 21:50 
QuestionNice! Pin
Chris Maunder16-Jun-21 4:14
cofounderChris Maunder16-Jun-21 4:14 
AnswerRe: Nice! Pin
ADMGNS27-Jun-21 3:52
professionalADMGNS27-Jun-21 3:52 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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