Rappel :

La simplification d'un polygone consiste à réduire le nombre de points (sommets) dont il est composé, tout en essayant de garder une "forme" proche de l'originale.

On s'en sert beaucoup en cartographie, le cas du KML étant un parfait exemple, mais aussi dans le domaine du jeu vidéo (le vaisseau au loin qui graphiquement n’apparaît plus que sur quelques pixels n'a plus besoin d'être défini par 2000 points !)

Méthode 1 : la simplification par "radius"

Une méthode simple, très rapide,et qui dans certains cas donne de très bons résultats. Le principe est très simple: On part du point 0, on définit un cercle dont le rayon correspond à la tolérance souhaitée, et on élimine tous les points du polygone original qui sont inscrits dans ce cercle. Puis on passe au point suivant, à savoir le point le plus proche du cercle. Et on recommence...L'image suivante montre parfaitement ce principe

source: http://www.softsurfer.com/Archive/algorithm_0205/algorithm_0205.htm

Et voici donc une implémentation rapide en AS3 :

/**
* Radius method
* We keep points outside a defined radius
* Simple, fast but approximative with complex shapes
*/
public function RadiusSimplify(points:Vector.<Point>, rad:Number):Vector.<Point>
{
    var newPoints:Vector.<Point>=new Vector.<Point>();
    var q:Point=points[0];
    var p:Point;
    var maxdist:Number=rad*rad;
    var len:int=points.length;
    for(var i:int=0; i<len; i++)
    {
        p=points[i];
        if((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)>=maxdist)
        {
            newPoints[newPoints.length] = p;
            q=p;
        }
    }
    return newPoints;
}

Rien de bien compliqué, non ?

Méthode 2 : Ramer-Douglas-Peucker

Passons maintenant à la méthode Ramer-Douglas-Peucker, que l'on trouve plus souvent sous le nom de Douglas-Peucker, ce qui est injuste car Urs Ramer fut le premier à imaginer ce principe, et ce n'est qu'un an plus tard que David Douglas et Thomas Peucker ont affiné la méthode.

Son principe n'est pas très compliqué, mais un peu plus difficile à expliquer en une phrase. Voici donc un schéma plus parlant :

source: http://www.codeproject.com/KB/recipes/dphull.aspx

Et voici donc mon implémentation rapide en AS3, basée sur une implémentation C# :

/**
* Ramer-Doulas-Peucker method
* A well known algorythm
* Not very simple, a little slow ()
* O(nm) worst case time, and O(n log m) expected time
* where m is the size of the simplified polyline.  
* but works fine with complex shapes
*/
 
public var points:Vector.<Point>;
 
public function RDPsimplify(Tolerance:Number):Vector.<Point>
{
    if(points==null||points.length<3||Tolerance==0)
        return points;
    var firstPoint:int=0;
    var lastPoint:int=points.length-1;
    var pointIndexsToKeep:Vector.<int>=new Vector.<int>;
    pointIndexsToKeep[0]=firstPoint
    pointIndexsToKeep[1]=lastPoint
//p1.x==p2.x && p1.y==p2.y is 4x faster than p1.equals(p2)    
while(points[firstPoint].x==points[lastPoint].x && points[firstPoint].y==points[lastPoint].y)
    {
        lastPoint--;
    }
    RamerDouglasPeuckerReduction(points, firstPoint, lastPoint, Tolerance, pointIndexsToKeep);
    var newPoints:Vector.<Point>=new Vector.<Point>();
    pointIndexsToKeep.sort(Array.NUMERIC)
    var len:int=pointIndexsToKeep.length-1;
    for(var i:int=0; i<len; i++)
    {
        newPoints[i]=points[pointIndexsToKeep[i]];
    }
    return newPoints;
}
 
private function RamerDouglasPeuckerReduction(points:Vector.<Point>, firstPoint:int, lastPoint:int, tolerance:Number, pointIndexsToKeep:Vector.<int>):void
{
    var maxDistance:Number=0;
    var indexFarthest:int=0;
    for(var index:int=firstPoint; index<lastPoint; index++)
    {
        var distance:Number=PerpendicularDistance(points[firstPoint], points[lastPoint], points[index]);
        if(distance>maxDistance)
        {
            maxDistance=distance;
            indexFarthest=index;
        }
    }
    if(maxDistance>tolerance&&indexFarthest!=0)
    {
        pointIndexsToKeep.push(indexFarthest);
        RamerDouglasPeuckerReduction(points, firstPoint, indexFarthest, tolerance, pointIndexsToKeep);
        RamerDouglasPeuckerReduction(points, indexFarthest, lastPoint, tolerance, pointIndexsToKeep);
    }
}
 
public function PerpendicularDistance(point1:Point, point2:Point, point:Point):Number
{
    var area:Number=abs((point1.x*point2.y+point2.x*point.y+point.x*point1.y-point2.x*point1.y-point.x*point2.y-point1.x*point.y)>>1);
    var bottom:Number=Math.sqrt(((point1.x-point2.x)*(point1.x-point2.x))+((point1.y-point2.y)*(point1.y-point2.y)));
    return (area/bottom)<<1;
}
 
//Very fast abs comparing to Math.abs using bitwise operators
private function abs(value:Number):Number
{
    return ((value^(value>>31))-(value>>31));
}

N'oublions pas un cas particulier : la réduction "n points". Dans certains cas, quand les points sont régulièrement "répartis", ne garder qu'un point sur n peut donner un résultat intéressant, surtout si on considère que cette méthode est extrêmement simple et donc très rapide.

Cela donnerait quelque chose comme ça :

/**
* n points method
* We keep one point on each n points
* Very simple, very fast but very approximative
* However can be usefull in certain situations
*/
public function NPsimplify(points:Vector.<Point>, n:int):Vector.<Point>
{
    if(points==null||points.length<3||n<2)
        return points;
    var newPoints:Vector.<Point>=new Vector.<Point>();
    var len:int=points.length-1;
    for(var i:int=0; i<len; i=i+n)
    {
        newPoints.push(points[i]);
    }
    return newPoints;
}

Enfin, ici on donne une bonne idée : combiner l’algorithme "radius" et l’algorithme de Ramer-Douglas-Peucker. Le principe : on effectue d'abord une réduction par radius, avec une petite tolérance (~8 pixels par exemple), ce qui va permettre de déjà réduire le nombre de points sans perdre trop d'informations. L’algorithme de Ramer-Douglas-Peucker étant rapide avec peu de points, on a tout intérêt à lui en fournir le moins possible. Cela nous donnera donc une solution à la fois rapide et efficace.

Testons un peu tout ça avec un cas pratique : un polygone représentant les frontières de la France, dérivé d'un KML de 498 points.

Vous pouvez jouer avec les contrôles afin de voir l'impact de chaque méthode, soit en définissant une tolérance ou bien un nombre cible de points de sortie. On peut voir que pour obtenir une France acceptable pour un cartographe, l’algorithme de Ramer-Douglas-Peucker y arrive avec 80 points, là où il faut 158 points avec l’algorithme "radius" pour une "qualité" équivalente.

Le mode BENCH permet de tester rapidement la "vitesse" d'un l’algorithme. Sur mon poste de test (portable Toshiba A300 - Core2Duo P8400 - 4Go RAM - Vista SP2 - Chrome 11.0.677.0 (Build 75464) - Flash Player WIN 10,2,152,26 RELEASE), pour 80 points en Ramer-Douglas-Peucker, il faut environ 3,2ms pour "calculer" le polygone simplifié, là où il ne faut qu'environ 0.35ms avec l’algorithme "radius" en 158 points.

;

De nombreuses variantes existent et des travaux sont menés pour améliorer soit la complexité soit la qualité de ces algorithmes : voici donc quelques ressources pour aller plus loin:

Voilà, en espérant que ça vous servira dans vos développements...