18 Feb

Ramer–Douglas–Peucker algorithm

Generally speaking, for low-speed flow around an aerofoil, the largest gradients in the flow-properties coincide with the greatest curvature of the aerofoil, and thus are the region that requires the greatest concentration of cells (or nodes) in the computational domain.

Many of the simplified treatments for spacing points along an aerofoil use a logarithmic spacing biased towards the leading edge. This of course can create issues if spaced in the chord-wise direction (x/c). The surface-normal at the leading edge of a symmetric aerofoil is perpendicular to the stream-wise direction, and thus can become under-resolved, and even faceted, with a simple linear or logarithmic chord-wise spacing.

One of the more significant issues with linear or logarithmic spacing is that it simply does not discriminate on the basis of curvature, thus the growth factor becomes a qualitative parameter controlled by the aerodynamicist. Any other curvature, for example the upper-surface curvature caused by the s-shaped chord of a DHTMU aerofoil, is neglected.

S-shaped chord of the DHMTU aerofoils. Source: JavaFoil Manual

Some computational treatments, though able to nicely capture curvature, are a little too complex for this simplified tool intended for 2D aerofoil analyses. I believe that the Ramer-Douglas-Peucker (RDP) algorithm is a simple yet powerful tool ideally suited to be applied to spacing points/nodes along a computational grid for for 2D aerofoil analyses.

RDP is a a decimation (down-sampling) algorithm, which although cannot increase resolution (create points) in areas of high-curvature, it can remove remove points in areas where curvature is low. This approach is quite simple and elegant. The algorithm works by creating a line between the start and end points, then recursively divides this line whilst each time finding the furthest point, marking these points to be kept if they are greater than a user-specified distance (epsilon).

Ramer-Douglas-Peucker Animation. Source: Mysid

As this requires a set of points, rather than a spline or other analytical curve, there are upsides and downsides. In the case of of analytic aerofoils, such as the DHTMU, or the NACA 4 that I originally scripted into GEVgoil, these need to be discretised before being down-sampled. However, for aerofoils that are already being supplied as a set of points, for example using the CSV method that is now also in GEVfoil, RDP can be applied directly.

To simplify matters further, RDP is available as a Python module via PIP: https://pypi.org/project/rdp/ Using this excellent ready-made library, I have constructed perhaps the simplest Python class, implementing this RDP module into GEVfoil:

from rdp import rdp
import numpy as np

class RDP(object):
    """A class to decimate aerofoil points"""
    def __init__(self, x, y, e=0.0001):
        xy = np.vstack((x, y)).T
        self.reducedXY = rdp(xy, epsilon=e)
        self.reducedX = self.reducedXY[:,0]
        self.reducedY = self.reducedXY[:,1]

And of course, the proof is in the pudding. Some examples of the RDP module in action in GEVfoil with varying epsilon:

Original NACA 2412 as generated by GEVfoil with 800 points each on the upper and lower surfaces
Decimated with RDP using an epsilon of 1e-05
Decimated with RDP using an epsilon of 1e-04
Decimated with RDP using an epsilon of 1e-03