He creado un algoritmo que convierte cualquier curva, es decir, la ruta en un número mínimo de puntos para poder guardarla en un archivo o base de datos.

El método es simple: mueve tres puntos en pasos iguales y mide el ángulo entre las líneas que forman estos puntos. Si el ángulo es mayor que la tolerancia, entonces crea una nueva curva cúbica para ese punto. Luego mueve las líneas hacia adelante y mide el ángulo nuevamente ...

Para aquellos que conocen Android Path Class: tenga en cuenta que dstPath es una clase personalizada, que registra los puntos en una matriz para que pueda guardarlos más tarde, mientras que srcPath es el resultado de una unión de Regions y, por lo tanto, no tiene puntos clave para mí ahorrar.

El problema es que el círculo no se ve suave como se puede ver en esta imagen, producida por el siguiente código, donde la ruta de origen consiste en un círculo y un rectángulo perfectos. Traté de cambiar el ángulo de tolerancia y la longitud de los pasos, pero nada ayuda. Me pregunto si puede sugerir alguna mejora a este algoritmo, o un enfoque diferente.

EDITAR: ahora he publicado el código completo para aquellos que usan Android Java, para que puedan probar y experimentar fácilmente.

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();
         }
    }

}

Aquí hay una comparación entre el original y lo que produce mi algoritmo:

Creo que tienes dos problemas:

Puntos de control no simétricos

Inicialmente comienzas con distancias iguales entre p0 a p1 y p1 a p2. Si no se cumple el ángulo de tolerancia entre los segmentos de línea, mueve p1 y p2 hacia adelante, pero mantiene p0 donde estaba. Esto aumenta la distancia entre p0 a p1 mientras mantiene la distancia entre p1 a p2 igual. Cuando crea una curva usando p1 como puntos de control, puede estar fuertemente sesgada hacia p2 dependiendo de cuántas iteraciones hayan pasado desde la última curva. Si moviera p2 dos veces la cantidad que p1, obtendría distancias iguales entre los puntos.

Curvas cuadráticas

Como también se menciona en otras respuestas, la curva cuadrática no es muy buena para este caso. Las curvas adyacentes que cree deben compartir un punto de control y una tangente . Cuando sus datos de entrada son solo puntos, Catmull-Rom Spline es una buena opción para ese propósito. Es una curva cúbica de Hermite, donde las tangentes para los puntos de control se calculan a partir de los puntos anteriores y siguientes.

La API Path en Android admite curvas Bézier, que son un poco diferentes a las curvas de Hermite con respecto a los parámetros. Afortunadamente, las curvas de Hermite se pueden convertir en curvas de Bézier. Aquí está el primer código de ejemplo que encontré cuando busqué en Google. Esta respuesta de Stackoverflow también parece dar la fórmula.

También mencionaste el problema de los bordes afilados. Con los datos de entrada que tiene, es imposible detectar si hay una esquina real o una curva muy empinada. Si esto se convierte en un problema, puede hacer que la iteración sea más adaptativa aumentando / disminuyendo el paso sobre la marcha según sea necesario.

Editar: después de pensarlo más, las curvas cuadráticas podrían usarse después de todo. En lugar de dibujar una curva cuadrática de p0 a p2 usando p1 como punto de control, dibuje de p0 a p1 usando un nuevo punto p0_1 como puntos de control. Ver la imagen de abajo.

Si p0_1 está en la intersección de las tangentes en p0 y p1, el resultado debería ser suave. Aún mejor, dado que los PathMeasure.getPosTan()retornos también son tangentes como el tercer parámetro, puede usar tangentes reales precisas en lugar de aproximaciones desde puntos adyacentes. Con este enfoque, necesita menos cambios en su solución existente.

En base a esta respuesta , el punto de intersección se puede calcular con la siguiente fórmula:

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;

Sin embargo, esta solución solo funciona si tanto u como v no son negativos. Ver la segunda imagen:

Aquí los rayos no se cruzan aunque las líneas lo harían, ya que u es negativo. En este caso, no es posible dibujar una curva cuadrática que se conecte sin problemas a la anterior. Aquí necesitas las curvas bézier. Puede calcular los puntos de control para ello con el método proporcionado anteriormente en esta respuesta o derivarlos directamente de las tangentes. Proyectar p0 al rayo tangente p0 + u * t0 y viceversa para el otro rayo da ambos puntos de control c0 y c1. También puede ajustar la curva utilizando cualquier punto entre p0 y c0 en lugar de c0 siempre que se encuentre en el rayo tangente.

Edit2: si su posición de dibujo está en p1, puede calcular los puntos de control bezier a p2 con el siguiente pseudocódigo:

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

Con estos puede agregar una ruta de p1 a p2:

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

Reemplace las operaciones de vector con operaciones por componente en matrices float [ 2 ] para que coincida con su código. Comienza por inicializar p1 = start;y p2 y p3 son los siguientes puntos. p0 está inicialmente indefinido. Para el primer segmento donde aún no tiene p0, puede usar una curva cuadrática de p1 a p2 con cp2 como punto de control. Lo mismo para el final del camino donde no tiene p3, puede dibujar una curva cuadrática de p1 a p2 con cp1 como punto de control. Alternativamente, puede inicializar p0 = p1 para el primer segmento y p3 = p2 para el último segmento. Después de cada segmento, cambia los valores p0 = p1; p1 = p2; and p2 = p3;al avanzar.

Cuando está guardando la ruta, simplemente guarda todos los puntos p0 ... pN. No es necesario guardar los puntos de control cp1 y cp2, ya que pueden calcularse según sea necesario.

Edit3: como parece difícil obtener buenos valores de entrada para la generación de curvas, propongo otro enfoque: usar serialización. Android Path no parece admitirlo, pero afortunadamente la clase Región sí. Vea esta respuesta para el código. Esto debería darte el resultado exacto. Podría tomar algo de espacio en la forma serializada si no está optimizado, pero en ese caso debería comprimirse muy bien. La compresión es fácil en Android Java usando GZIPOutputStream .

¿Qué haría el W3C?

Internet ha tenido este problema. El Consorcio World Wide Web lo notó. Tiene una solución estándar recomendada desde 1999: Gráficos vectoriales escalables (SVG) . Es un formato de archivo basado en XML diseñado específicamente para almacenar formas 2D.

" Escalable, ¿qué? "

Gráficos vectoriales escalables !

• Escalable : está destinado a escalar sin problemas a cualquier tamaño.
• Vector : se basa en la noción matemática de vectores .
• Gráficos . Está destinado a hacer fotos.

Aquí está la especificación técnica para SVG versión 1.1.
^{(No se asuste por el nombre; en realidad es agradable de leer).}

Han escrito exactamente cómo se deben almacenar las formas básicas como círculos o rectángulos . Por ejemplo, rectángulos tienen estas propiedades: x, y, width, height, rx, ry. (El rxy ryse puede usar para esquinas redondeadas).

Aquí está su rectángulo de ejemplo en SVG: (Bueno, dos realmente, uno para el contorno del lienzo).

<?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>

Esto es lo que representa:

Como dice la especificación, puede dejar de lado algunas de las propiedades si no las necesita. (Por ejemplo, rxy los ryatributos no se usaron aquí). Sí, hay una tonelada de cruft en la parte superior sobre la DOCTYPEque no necesitarás solo para tu juego. Son opcionales también.

Rutas

Las rutas SVG son "rutas" en el sentido de que si pones un lápiz en un papel, lo mueves y eventualmente lo vuelves a levantar , tienes una ruta. No tienen que estar cerrados , pero podrían estarlo.

Cada ruta tiene un datributo (me gusta pensar que significa "dibujar"), que contiene datos de ruta , una secuencia de comandos para básicamente poner un bolígrafo en un papel y moverlo .

Dan el ejemplo de un triángulo:

<?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>

Ver el datributo en el path?

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

El Mes un comando para Mover a (seguido de coordenadas), los Ls son para Línea a (con coordenadas) y zes un comando para cerrar la ruta (es decir, dibujar una línea de regreso a la primera ubicación; eso no necesita coordenadas).

¿Las líneas rectas son aburridas? ¡Usa los comandos Bézier cúbicos o cuadráticos !

La teoría detrás de las curvas de Bézier está bien cubierta en otros lugares (como en Wikipedia ), pero aquí está el resumen ejecutivo: Béziers tiene un punto de inicio y finalización, posiblemente con muchos puntos de control que influyen hacia dónde va la curva intermedia.

La especificación también proporciona instrucciones para convertir la mayoría de las formas básicas en rutas en caso de que lo desee.

Por qué y cuándo usar SVG

Decida con cuidado si quiere seguir este camino (juego de palabras), ¡porque es realmente complicado representar cualquier forma 2D arbitraria en el texto! Puedes hacer tu vida mucho más fácil si, por ejemplo, te limitas a solo caminos hechos de (potencialmente muchas) líneas rectas.

Pero si decide que desea formas arbitrarias, SVG es el camino a seguir: tiene un gran soporte de herramientas: puede encontrar muchas bibliotecas para el análisis XML en el nivel bajo y herramientas de editor SVG en el nivel alto.

En cualquier caso, el estándar SVG es un buen ejemplo.

Su código contiene un comentario engañoso:

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

Una curva bezier cuadrática no pasa por el segundo punto. Si desea pasar por el segundo punto, necesita un tipo diferente de curva, como una curva de hermita . Es posible que pueda convertir las curvas de hermita en beziers para que pueda usar la clase Path.

Otra sugerencia es que, en lugar de muestrear los puntos, utilice la media de los puntos que está omitiendo.

Otra sugerencia es que en lugar de usar un ángulo como umbral, use la diferencia entre la curva real y la curva aproximada. Los ángulos no son el verdadero problema; El verdadero problema es cuando el conjunto de puntos no se ajusta a una curva bezier.

Otra sugerencia es usar beziers cúbicos, con la tangente de uno que coincida con la tangente de la siguiente. De lo contrario (con cuadráticos), creo que sus curvas no coincidirán suavemente.

Para obtener una intersección más uniforme de dos caminos, puede escalarlos antes de la intersección y reducirlos después.

No sé si es una buena solución, pero funcionó bien para mí. También es rápido. En mi ejemplo, interseco una ruta redondeada con un patrón que creé (rayas). Se ve bien incluso cuando está escalado.

Aquí mi código:

    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);
}

Se ve aún suave al hacer zoom con canvas.scale ():

Mire la interpolación de polígonos ( http://en.wikipedia.org/wiki/Polynomial_interpolation )

Básicamente, toma n nodos equiespaciados (la interpolación óptima no es equiespaciada, pero para su caso debería ser lo suficientemente buena y fácil de implementar)

Termina con un polígono de orden n que disminuye el error entre su curva si (<- grande si) su línea es lo suficientemente suave .

En su caso, está haciendo una interpolación lineal (orden 1).

El otro caso (como lo recomendó GriffinHeart ) fue usar Splines ( http://en.wikipedia.org/wiki/Spline_interpolation )

Cualquiera de los casos le daría alguna forma de ajuste polinómico para su curva.

Si el objetivo de la conversión es solo para el almacenamiento, y cuando lo vuelve a mostrar en la pantalla necesita que sea suave, entonces el almacenamiento de mayor fidelidad que puede obtener, al tiempo que minimiza el almacenamiento total requerido para persistir en una curva dada podría ser para almacenar realmente los atributos del círculo (o un arco, más bien) y volver a dibujarlo a pedido.

Origen. Radio. Iniciar / detener ángulos para dibujar el arco.

Si necesita convertir el círculo / arco en puntos de todos modos para renderizar, entonces puede hacerlo al cargarlo desde el almacenamiento, mientras almacena siempre solo los atributos.

¿Hay alguna razón para elegir curvas en lugar de líneas rectas? Las líneas rectas son más sencillas de trabajar y se pueden representar de manera eficiente en hardware.

El otro enfoque que vale la pena considerar es almacenar un par de bits por píxel, indicando si está dentro, fuera o en el contorno de la forma. Esto debería comprimir bien y podría ser más eficiente que las líneas para selecciones complejas.

También puede encontrar estos artículos interesantes / útiles:

• http://blog.getpaint.net/2008/06/02/whats-coming-in-paintnet-v335/ (mitad inferior)
• 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/

Eche un vistazo a la interpolación de curvas: hay algunos tipos diferentes que puede implementar que ayudarán a suavizar su curva. Cuantos más puntos puedas obtener en ese círculo, mejor. El almacenamiento es bastante barato, por lo que si extraer 360 nodos cercanos es lo suficientemente barato (incluso a 8 bytes para la posición; 360 nodos es difícil de almacenar).

Puede colocar aquí algunas muestras de interpolación con solo cuatro puntos; y los resultados son bastante buenos (mi favorito es el Bezier para este caso, aunque otros podrían aportar otras soluciones efectivas).

Puedes jugar aquí también.