I need a Free (i.e. Open Source) implementation of the Polynomial Approximation with Exponential Kernel (PAEK) algorithm, preferably in C, C++, Python, Julia or R.

The algorithm is one of the methods ArcGIS offers for line smoothing and described in Bodansky, Eugene; Gribov, Alexander; and Pilouk, Morakot, "Smoothing and Compression of Lines Obtained by Raster-to-Vector Conversion", LNCS 2390, Springer, p. 256-265, 2002.

If I can't find a ready to use implementation, I will have a go at it myself.


I came across a thread Smoothing a 2-D figure. The answers make reference to this paper Chaikin's algorithm for curves

For a given polygon with vertices as P0, P1, ...P(N-1), the corner cutting algorithm will generate 2 new vertices for each line segment defined by P(i) and P(i+1) as

Q(i) = (3/4)P(i) + (1/4)P(i+1) R(i) = (1/4)P(i) + (3/4)P(i+1)

So, your new polygon will have 2N vertices. You can then apply the corner cutting on the new polygon again and repeatedly until the desired resolution is reached. The result will be a polygon with many vertices but they will look smooth when displayed. It can be proved that the resulting curve produced from this corner cutting approach will converge into a quadratic B-spline curve. The advantage of this approach is that the resulting curve will never over-shoot.

Original Polygon

enter image description here

Apply corner cutting once

enter image description here

Apply corner cutting one more time

enter image description here


Also, another example you could view Corner Cutting the Cube which is a variant of Chaikin's corner-cutting algorithm.

It is similar in spirit to a number of subdivision schemes for producing smooth surfaces from an original set of control vertices, including the Doo-Sabin algorithm and the Catmull-Clark(?) algorithm, which pick distances and weights so as to produce B-spline surfaces, and the Loop scheme, which is the grandfather of much of today's work on subdivision surfaces in graphics.

It's an interesting variant because it's singular in some sense: normally corner cutting algorithms cut off a little section 'w' at either end of each edge in the original model (w = 1/4 in the original chaikin algorithm), leaving some of the original edge. This variant results in the original edge vanishing.

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here

enter image description here

To implement either option you might want to look into TP4 : Subdivision curves

goes over how to implement three subdivision schemes for closed curves: Chaikin, corner cutting and four-point.Subdivision curves

|improve this answer|||||
  • I found it aswell and thought i had it, but it seems the second one is not the PAEK implementation, as Joe Kington says : "I've never tried to implement PAEK, so I'm not sure how involved it is. If you need to do this more robustly, you might try looking into PAEK or another similar method." The first approach from chaikin seems interesting though and looks quite close to the PAEK implementation. How would you implement it ? – gisnside Oct 2 '17 at 14:49
  • I've updated my answer with another source that provides a python script to achieve that corner cutting results. – whyzar Oct 2 '17 at 15:09
  • Interesting links ! Thanks for taking the challenge anyway :) – gisnside Oct 2 '17 at 15:22
  • 1
    I followed the link to have a look at the python code but there's nothing useful, alas. The exercice seems to be about implementing the chaikin algorithm but i didn't find any solution to the exercice (github.com/GeoNumTP/GeoNum2017/blob/master/TP4/tp4.py) so the interesting function is empty :/ def Chaikin( X0 ) : ## TODO Implement Chaikin's subdivision scheme. return X1 – gisnside Oct 2 '17 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.