J'ai créé un algorithme qui convertit toute courbe, c'est-à-dire le chemin, en un nombre minimum de points afin de pouvoir l'enregistrer dans un fichier ou une base de données.

La méthode est simple: elle déplace trois points par étapes égales et mesure l'angle entre les lignes que forment ces points. Si l'angle est supérieur à la tolérance, il crée une nouvelle courbe cubique à ce point. Il fait ensuite avancer les lignes et mesure à nouveau l'angle…

Pour ceux qui connaissent Android Path Class - Notez que le dstPath est une classe personnalisée, qui enregistre les points dans un tableau afin que je puisse enregistrer les points plus tard, tandis que le srcPath est le résultat d'une union de régions et n'a donc pas de points clés pour moi sauver.

Le problème est que le cercle n'est pas lisse comme vous pouvez le voir sur cette image, produite par le code ci-dessous, où le chemin source se compose d'un cercle et d'un rectangle parfaits. J'ai essayé de changer l'angle de tolérance et la longueur des pas, mais rien n'y fait. Je me demande si vous pouvez suggérer une amélioration à cet algorithme ou une approche différente.

EDIT: J'ai maintenant publié le code complet pour ceux qui utilisent Android java, afin qu'ils puissent facilement essayer et expérimenter.

public class CurveSavePointsActivity extends Activity{

    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);

        setContentView(new CurveView(this));
    }

    class CurveView extends View{

        Path srcPath, dstPath;
        Paint srcPaint = new Paint(Paint.ANTI_ALIAS_FLAG);
        Paint dstPaint = new Paint(Paint.ANTI_ALIAS_FLAG);

        public CurveView(Context context) {
            super(context);

            srcPaint.setColor(Color.BLACK);
            srcPaint.setStyle(Style.STROKE);
            srcPaint.setStrokeWidth(2);
            srcPaint.setTextSize(20);

            dstPaint.setColor(Color.BLUE);
            dstPaint.setStyle(Style.STROKE);
            dstPaint.setStrokeWidth(2);
            dstPaint.setTextSize(20);

            srcPath = new Path();
            dstPath = new Path();

        }

        @Override
        protected void onSizeChanged(int w, int h, int oldw, int oldh) {
            super.onSizeChanged(w, h, oldw, oldh);

            //make a circle path
            srcPath.addCircle(w/4, h/2, w/6 - 30, Direction.CW);

            //make a rectangle path
            Path rectPath = new Path();
            rectPath.addRect(new RectF(w/4, h/2 - w/16, w*0.5f, h/2 + w/16), Direction.CW);


            //create a path union of circle and rectangle paths
            RectF bounds = new RectF();
            srcPath.computeBounds(bounds, true);
            Region destReg = new Region();
            Region clip = new Region();
            clip.set(new Rect(0,0, w, h));
            destReg.setPath(srcPath, clip);
            Region srcReg = new Region();
            srcReg.setPath(rectPath, clip); 
            Region resultReg = new Region();
            resultReg.op(destReg, srcReg, Region.Op.UNION);
            if(!resultReg.isEmpty()){
                srcPath.reset();
                srcPath.addPath(resultReg.getBoundaryPath());
            }

            //extract a new path from the region boundary path
            extractOutlinePath();

            //shift the resulting path bottom left, so they can be compared
            Matrix matrix = new Matrix();
            matrix.postTranslate(10, 30);
            dstPath.transform(matrix);

        }

         @Override 
            public void onDraw(Canvas canvas) { 
                super.onDraw(canvas);    
                canvas.drawColor(Color.WHITE);
                canvas.drawPath(srcPath, srcPaint);
                canvas.drawPath(dstPath, dstPaint);

                canvas.drawText("Source path", 40, 50, srcPaint);
                canvas.drawText("Destination path", 40, 100, dstPaint);
         }


         public void extractOutlinePath() {

             PathMeasure pm = new PathMeasure(srcPath, false); //get access to curve points

             float p0[] = {0f, 0f}; //current position of the new polygon
             float p1[] = {0f, 0f}; //beginning of the first line
             float p2[] = {0f, 0f}; //end of the first & the beginning of the second line
             float p3[] = {0f, 0f}; //end of the second line

             float pxStep = 5; //sampling step for extracting points
             float pxPlace  = 0; //current place on the curve for taking x,y coordinates
             float angleT = 5; //angle of tolerance

             double a1 = 0; //angle of the first line
             double a2 = 0; //angle of the second line

             pm.getPosTan(0, p0, null); //get the beginning x,y of the original curve into p0
             dstPath.moveTo(p0[0], p0[1]); //start new path from the beginning of the curve
             p1 = p0.clone(); //set start of the first line

             pm.getPosTan(pxStep, p2, null); //set end of the first line & the beginning of the second

             pxPlace = pxStep * 2;
             pm.getPosTan(pxPlace, p3, null); //set end of the second line


             while(pxPlace < pm.getLength()){
             a1 = 180 - Math.toDegrees(Math.atan2(p1[1] - p2[1], p1[0] - p2[0])); //angle of the first line
             a2 = 180 - Math.toDegrees(Math.atan2(p2[1] - p3[1], p2[0] - p3[0])); //angle of the second line

             //check the angle between the lines
             if (Math.abs(a1-a2) > angleT){

               //draw a straight line to the first point if the current p0 is not already there
               if(p0[0] != p1[0] && p0[1] != p1[1]) dstPath.quadTo((p0[0] + p1[0])/2, (p0[1] + p1[1])/2, p1[0], p1[1]);

               dstPath.quadTo(p2[0] , p2[1], p3[0], p3[1]); //create a curve to the third point through the second

               //shift the three points by two steps forward
               p0 = p3.clone();
               p1 = p3.clone();
               pxPlace += pxStep;
               pm.getPosTan(pxPlace, p2, null); 
               pxPlace += pxStep;
               pm.getPosTan(pxPlace, p3, null);
               if (pxPlace > pm.getLength()) break;
             }else{
               //shift three points by one step towards the end of the curve
               p1 = p2.clone(); 
               p2 = p3.clone();
               pxPlace += pxStep;
               pm.getPosTan(pxPlace, p3, null); 
             }
             }
             dstPath.close();
         }
    }

}

Voici une comparaison entre l'original et ce que mon algorithme produit:

Je pense que vous avez deux problèmes:

Points de contrôle non symétriques

Au départ, vous commencez avec des distances égales entre p0 à p1 et p1 à p2. Si l'angle de tolérance entre les segments de ligne n'est pas atteint, vous déplacez p1 et p2 vers l'avant, mais gardez p0 où il était. Cela augmente la distance entre p0 à p1 tout en maintenant la même distance entre p1 et p2. Lorsque vous créez une courbe en utilisant p1 comme points de contrôle, elle peut être fortement biaisée vers p2 selon le nombre d'itérations qui se sont écoulées depuis la dernière courbe. Si vous déplacez p2 deux fois plus que p1, vous obtiendrez des distances égales entre les points.

Courbes quadratiques

Comme mentionné dans d'autres réponses également, la courbe quadratique n'est pas très bonne dans ce cas. Les courbes adjacentes que vous créez doivent partager un point de contrôle et une tangente . Lorsque vos données d'entrée ne sont que des points, Catmull-Rom Spline est un bon choix à cet effet. Il s'agit d'une courbe hermite cubique, où les tangentes des points de contrôle sont calculées à partir des points précédent et suivant.

L'API Path d'Android prend en charge les courbes de Bézier, qui sont un peu différentes des courbes Hermite en ce qui concerne les paramètres. Heureusement, les courbes Hermite peuvent être converties en courbes de Bézier. Voici le premier exemple de code que j'ai trouvé lors de la recherche sur Google. Cette réponse Stackoverflow semble également donner la formule.

Vous avez également mentionné le problème des arêtes vives. Avec les données d'entrée dont vous disposez, il est impossible de détecter s'il y a un coin aigu réel ou juste une courbe très raide. Si cela devient un problème, vous pouvez rendre l'itération plus adaptative en augmentant / diminuant l'étape à la volée si nécessaire.

Edit: Après réflexion, les courbes quadratiques pourraient être utilisées après tout. Au lieu de tracer une courbe quadratique de p0 à p2 en utilisant p1 comme point de contrôle, tracez-la de p0 à p1 en utilisant un nouveau point p0_1 comme points de contrôle. Voir l'image ci-dessous.

Si p0_1 est à l'intersection des tangentes de p0 et p1, le résultat doit être lisse. Encore mieux, puisque PathMeasure.getPosTan()renvoie également la tangente comme troisième paramètre, vous pouvez utiliser des tangentes précises réelles au lieu d'approximations à partir de points adjacents. Avec cette approche, vous avez besoin de moins de changements à votre solution existante.

Sur la base de cette réponse , le point d'intersection peut être calculé avec la formule suivante:

getPosTan(pxPlace0, p0, t0); // Also get the tangent
getPosTan(pxPlace1, p1, t1);
t1 = -t1; // Reverse direction of second tangent
vec2 d = p1 - p0;
float det = t1.x * t0.y - t1.y * t0.x;
float u = (d.y * t1.x - d.x * t1.y) / det;
float v = (d.y * t0.x - d.x * t0.y) / det; // Not needed ... yet
p0_1 = p0 + u * t0;

Cette solution ne fonctionne cependant que si u et v ne sont pas tous deux négatifs. Voir la deuxième photo:

Ici, les rayons ne se coupent pas, contrairement aux lignes, car u est négatif. Dans ce cas, il n'est pas possible de tracer une courbe quadratique qui se connecterait en douceur à la précédente. Ici, vous avez besoin des courbes de Bézier. Vous pouvez calculer les points de contrôle pour cela soit avec la méthode donnée plus haut dans cette réponse, soit les dériver directement des tangentes. La projection de p0 sur le rayon tangent p0 + u * t0 et vice versa pour l'autre rayon donne les deux points de contrôle c0 et c1. Vous pouvez également ajuster la courbe en utilisant n'importe quel point entre p0 et c0 au lieu de c0 tant qu'il se trouve sur le rayon tangent.

Edit2: Si votre position de dessin est en p1, vous pouvez calculer les points de contrôle de Bézier à p2 avec le pseudo-code suivant:

vec2 p0, p1, p2, p3; // These are calculated with PathMeasure
vec2 cp1 = p1 + (p2 - p0) / 6;
vec2 cp2 = p2 - (p3 - p1) / 6;

Avec ceux-ci, vous pouvez ajouter un chemin de p1 à p2:

path.cubicTo(cp1.x, cp1.y, cp2.x, cp2.y, p2.x, p2.y);

Remplacez les opérations vectorielles par des opérations par composant sur les tableaux float [ 2 ] pour correspondre à votre code. Vous commencez par initialiser p1 = start;et p2 et p3 sont les points suivants. p0 est initialement indéfini. Pour le premier segment où vous n'avez pas encore p0, vous pouvez utiliser une courbe quadratique de p1 à p2 avec cp2 comme point de contrôle. De même pour la fin du chemin où vous n'avez pas p3, vous pouvez tracer une courbe quadratique de p1 à p2 avec cp1 comme point de contrôle. Alternativement, vous pouvez initialiser p0 = p1 pour le premier segment et p3 = p2 pour le dernier segment. Après chaque segment, vous changez les valeurs p0 = p1; p1 = p2; and p2 = p3;lorsque vous avancez.

Lorsque vous enregistrez le chemin, vous enregistrez simplement tous les points p0 ... pN. Pas besoin de sauvegarder les points de contrôle cp1 et cp2, car ils peuvent être calculés selon les besoins.

Edit3: Comme il semble difficile d'obtenir de bonnes valeurs d'entrée pour la génération de courbe, je propose une autre approche: utiliser la sérialisation. Android Path ne semble pas le prendre en charge, mais heureusement, la classe Region le fait. Voir cette réponse pour le code. Cela devrait vous donner le résultat exact. Cela peut prendre un peu d'espace sous la forme sérialisée s'il n'est pas optimisé, mais dans ce cas, il devrait très bien se compresser. La compression est facile dans Android Java en utilisant GZIPOutputStream .

Que ferait le W3C?

Internet a eu ce problème. Le World Wide Web Consortium l'a remarqué. Il a une solution standard recommandée depuis 1999: les graphiques vectoriels évolutifs (SVG) . Il s'agit d'un format de fichier basé sur XML spécialement conçu pour stocker des formes 2D.

" Évolutif, quoi? "

Graphiques vectoriels évolutifs !

• Évolutif : il est conçu pour évoluer en douceur vers n'importe quelle taille.
• Vecteur : il est basé sur la notion mathématique de vecteurs .
• Graphiques . Il est destiné à faire des photos.

Voici les spécifications techniques de SVG version 1.1.
^{(Ne soyez pas effrayé par le nom; c'est en fait agréable à lire.)}

Ils ont écrit exactement comment les formes de base comme les cercles ou les rectangles doivent être stockées. Par exemple, les rectangles ont ces propriétés: x, y, width, height, rx, ry. (Le rxet rypeut être utilisé pour les coins arrondis.)

Voici leur exemple de rectangle en SVG: (Eh bien, deux vraiment - un pour le contour du canevas.)

<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" 
  "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="12cm" height="4cm" viewBox="0 0 1200 400"
     xmlns="http://www.w3.org/2000/svg" version="1.1">
  <desc>Example rect01 - rectangle with sharp corners</desc>

  <!-- Show outline of canvas using 'rect' element -->
  <rect x="1" y="1" width="1198" height="398"
        fill="none" stroke="blue" stroke-width="2"/>

  <rect x="400" y="100" width="400" height="200"
        fill="yellow" stroke="navy" stroke-width="10"  />
</svg>

Voici ce que cela représente:

Comme le dit la spécification, vous êtes libre de laisser de côté certaines propriétés si vous n'en avez pas besoin. (Par exemple, rxet les ryattributs n'ont pas été utilisés ici.) Oui, il y a une tonne de cruches au sommet DOCTYPEdont vous n'aurez pas besoin uniquement pour votre jeu. Ils sont également facultatifs.

Chemins

Les chemins SVG sont des "chemins" dans le sens où si vous posez un crayon sur un papier, le déplacez et finalement le relancez , vous avez un chemin. Ils ne doivent être fermés , mais ils pourraient être.

Chaque chemin a un dattribut (j'aime penser qu'il signifie "dessiner"), contenant des données de chemin , une séquence de commandes pour simplement mettre un stylo sur un papier et le déplacer .

Ils donnent l'exemple d'un triangle:

<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" 
  "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="4cm" height="4cm" viewBox="0 0 400 400"
     xmlns="http://www.w3.org/2000/svg" version="1.1">
  <title>Example triangle01- simple example of a 'path'</title>
  <desc>A path that draws a triangle</desc>
  <rect x="1" y="1" width="398" height="398"
        fill="none" stroke="blue" />
  <path d="M 100 100 L 300 100 L 200 300 z"
        fill="red" stroke="blue" stroke-width="3" />
</svg>

Voir l' dattribut dans le path?

d="M 100 100 L 300 100 L 200 300 z"

Il Ms'agit d'une commande pour Déplacer vers (suivie de coordonnées), les Ls pour Ligne vers (avec coordonnées) et zest une commande pour fermer le chemin (c'est-à-dire tracer une ligne vers le premier emplacement; qui n'a pas besoin de coordonnées).

Les lignes droites sont ennuyeuses? Utilisez les commandes cubiques ou quadratiques de Bézier!

La théorie derrière les courbes de Bézier est bien couverte ailleurs (comme sur Wikipédia ), mais voici le résumé: Béziers a un point de départ et un point de fin, avec peut-être de nombreux points de contrôle qui influencent où va la courbe entre les deux.

La spécification donne également des instructions pour convertir la plupart des formes de base en chemins si vous le souhaitez.

Pourquoi et quand utiliser SVG

Décidez soigneusement si vous voulez emprunter ce chemin (jeu de mots voulu), car il est vraiment assez compliqué de représenter n'importe quelle forme 2D arbitraire dans du texte! Vous pouvez vous simplifier la vie si vous vous limitez, par exemple, à de simples chemins composés (potentiellement très nombreux) de lignes droites.

Mais si vous décidez que vous voulez des formes arbitraires, SVG est le chemin à parcourir: il a un excellent support d'outil: vous pouvez trouver de nombreuses bibliothèques pour l'analyse XML au bas niveau et des outils d'édition SVG au niveau élevé.

Quoi qu'il en soit, la norme SVG donne un bon exemple.

Votre code contient un commentaire trompeur:

dstPath.quadTo(p2[0] , p2[1], p3[0], p3[1]); //create a curve to the third point through the second

Une courbe de Bézier ne pas passer par le second point. Si vous voulez passer par le deuxième point, vous avez besoin d'un type de courbe différent, comme une courbe hermite . Vous pourrez peut-être convertir les courbes d'hermite en beziers afin d'utiliser la classe Path.

Une autre suggestion est qu'au lieu d'échantillonner les points, utilisez la moyenne des points que vous sautez.

Une autre suggestion est qu'au lieu d'utiliser un angle comme seuil, utilisez la différence entre la courbe réelle et la courbe approximative. Les angles ne sont pas le vrai problème; le vrai problème est lorsque l'ensemble de points ne correspond pas à une courbe de Bézier.

Une autre suggestion est d'utiliser des béziers cubiques, la tangente de l'un correspondant à la tangente de la suivante. Sinon (avec quadratique), je pense que vos courbes ne correspondent pas bien.

Pour obtenir une intersection plus fluide de deux chemins, vous pouvez les augmenter avant l'intersection et les réduire après.

Je ne sais pas si c'est une bonne solution, mais cela a bien fonctionné pour moi. C'est aussi rapide. Dans mon exemple, je coupe un chemin arrondi avec un motif que j'ai créé (rayures). Il semble bon même à l'échelle.

Voici mon code:

    Path mypath=new Path(<desiredpath to fill with a pattern>);
    String sPatternType=cpath.getsPattern();

    Path pathtempforbounds=new Path(cpath.getPath());
    RectF rectF = new RectF();
     if (sPatternType.equals("1")){
         turnPath(pathtempforbounds, -45);
     }
     pathtempforbounds.computeBounds(rectF, true);

     float ftop=rectF.top;
     float fbottom=rectF.bottom;
     float fleft=rectF.left;
     float fright=rectF.right;
     float xlength=fright-fleft;

     Path pathpattern=new Path();

     float ypos=ftop;
     float xpos=fleft;

     float fStreifenbreite=4f;

     while(ypos<fbottom){
         pathpattern.moveTo(xpos,ypos);
         xpos=xpos+xlength;
         pathpattern.lineTo(xpos, ypos);
         ypos=ypos+fStreifenbreite;
         pathpattern.lineTo(xpos, ypos);
         xpos=xpos-xlength;
         pathpattern.lineTo(xpos, ypos);
         ypos=ypos-fStreifenbreite;
         pathpattern.lineTo(xpos, ypos);
         pathpattern.close();
         ypos=ypos+2*fStreifenbreite;

     }

     // Original vergrössern

     scalepath(pathpattern,10);
     scalepath(mypath,10);

     if (sPatternType.equals("1")){
         Matrix mdrehen=new Matrix();
         RectF bounds=new RectF();
         pathpattern.computeBounds(bounds, true);
         mdrehen.postRotate(45, (bounds.right + bounds.left)/2,(bounds.bottom + bounds.top)/2);
         pathpattern.transform(mdrehen);
     }

     RectF rectF2 = new RectF();
     mypath.computeBounds(rectF2, true);

     Region clip = new Region();
     clip.set((int)(rectF2.left-100f),(int)(rectF2.top -100f), (int)(rectF2.right+100f),(int)( rectF2.bottom+100f));
     Region region1 = new Region();
     region1.setPath(pathpattern, clip);

     Region region2 = new Region();
     region2.setPath(mypath, clip);

     region1.op(region2, Region.Op.INTERSECT);


     Path pnew=region1.getBoundaryPath();


     scalepath(pnew, 0.1f);
     cpath.setPathpattern(pnew);




public void turnPath(Path p,int idegree){
     Matrix mdrehen=new Matrix();
     RectF bounds=new RectF();
     p.computeBounds(bounds, true);
     mdrehen.postRotate(idegree, (bounds.right + bounds.left)/2,(bounds.bottom + bounds.top)/2);
     p.transform(mdrehen);
}

public void scalepath(Path p,float fscale){
     Matrix mverkleinern=new Matrix();
     mverkleinern.preScale(fscale,fscale);
     p.transform(mverkleinern);
}

Semble encore lisse lors du zoom avec canvas.scale ():

Regardez l'interpolation de polygone ( http://en.wikipedia.org/wiki/Polynomial_interpolation )

Fondamentalement, vous prenez n nœuds espacés (l'interpolation optimale n'est pas équidistante, mais pour votre cas, elle devrait être assez bonne et facile à implémenter)

Vous vous retrouvez avec un polygone d'ordre n qui diminue l'erreur entre votre courbe si (<- grand si) votre ligne est assez lisse .

Dans votre cas, vous faites une interpolation linéaire (ordre 1).

L'autre cas (comme GriffinHeart l'a recommandé) était d'utiliser Splines ( http://en.wikipedia.org/wiki/Spline_interpolation )

Dans les deux cas, vous obtiendrez une forme d' ajustement polynomial pour votre courbe.

Si le point de la conversion est uniquement pour le stockage, et lorsque vous le restituez à l'écran, vous avez besoin qu'il soit fluide, alors le stockage le plus fidèle que vous pouvez obtenir, tout en minimisant le stockage total requis pour persister, une courbe donnée peut être pour stocker réellement les attributs du cercle (ou d'un arc, plutôt) et le redessiner à la demande.

Origine. Rayon. Angles de début / fin pour dessiner l'arc.

Si vous avez quand même besoin de convertir le cercle / arc en points pour le rendu, vous pouvez éventuellement le faire lors du chargement à partir du stockage, tout en stockant uniquement les attributs.

Y a-t-il une raison pour opter pour des courbes par opposition aux lignes droites? Les lignes droites sont plus simples à utiliser et peuvent être rendues efficacement dans le matériel.

L'autre approche qui mérite d'être envisagée est de stocker quelques bits par pixel, en indiquant si c'est à l'intérieur, à l'extérieur ou sur le contour de la forme. Cela devrait bien compresser et pourrait être plus efficace que les lignes pour les sélections complexes.

Vous pourriez également trouver ces articles intéressants / utiles:

• http://blog.getpaint.net/2008/06/02/whats-coming-in-paintnet-v335/ (moitié inférieure)
• http://blog.getpaint.net/2009/02/25/introducing-paintnet-v35%E2%80%99s-new-selection-renderer/
• http://blog.getpaint.net/2011/12/04/responsive-selection-rendering-for-paint-net-4-0/

Jetez un oeil à l'interpolation de courbe - il existe plusieurs types différents que vous pouvez implémenter qui aideront à lisser votre courbe. Plus vous obtiendrez de points sur ce cercle, mieux ce sera. Le stockage est assez bon marché - donc si l'extraction de 360 ​​nœuds proches est assez bon marché (même à 8 octets pour la position; 360 nœuds ne sont guère chers à stocker).

Vous pouvez placer avec quelques échantillons d'interpolation ici avec seulement quatre points; et les résultats sont assez bons (mon préféré est le Bézier pour ce cas, bien que d'autres puissent sonner à propos d'autres solutions efficaces).

Vous pouvez aussi jouer ici .