Eu criei um algoritmo que converte qualquer curva, ou seja, caminho em número mínimo de pontos, para que eu possa salvá-lo em um arquivo ou banco de dados.

O método é simples: move três pontos em etapas iguais e mede o ângulo entre as linhas que esses pontos formam. Se o ângulo for maior que a tolerância, ele cria uma nova curva cúbica para esse ponto. Então ele move as linhas para frente e mede o ângulo novamente ...

Para quem conhece a Android Path Class - Observe que o dstPath é uma classe personalizada, que registra os pontos em uma matriz para que eu possa salvar os pontos mais tarde, enquanto o srcPath é o resultado de uma união de regiões e, portanto, não tem pontos-chave para mim. salvar.

O problema é que o círculo não parece suave como você pode ver nesta imagem, produzida pelo código abaixo, onde o caminho de origem consiste em um círculo e um retângulo perfeitos. Tentei alterar o ângulo de tolerância e o comprimento dos passos, mas nada ajuda. Gostaria de saber se você pode sugerir alguma melhoria nesse algoritmo ou uma abordagem diferente.

Edição: Agora, eu publiquei o código inteiro para aqueles que usam java Android, para que eles possam facilmente experimentar.

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

}

Aqui está uma comparação entre o original e o que meu algoritmo produz:

Eu acho que você tem dois problemas:

Pontos de controle não simétricos

Inicialmente, você começa com distâncias iguais entre p0 a p1 e p1 a p2. Se o ângulo de tolerância entre os segmentos de linha não for atingido, mova p1 e p2 para frente, mas mantenha p0 onde estava. Isso aumenta a distância entre p0 e p1, mantendo a mesma distância entre p1 e p2. Quando você cria uma curva usando p1 como pontos de controle, ela pode ser fortemente influenciada por p2, dependendo de quantas iterações passaram desde a última curva. Se você mover p2 duas vezes a quantidade que p1, obterá distâncias iguais entre os pontos.

Curvas quadráticas

Como mencionado em outras respostas, a curva quadrática não é muito boa para este caso. As curvas adjacentes criadas devem compartilhar um ponto de controle e uma tangente . Quando seus dados de entrada são apenas pontos, o Catmull-Rom Spline é uma boa opção para esse fim. É uma curva Hermite cúbica, onde as tangentes para os pontos de controle são calculadas a partir dos pontos anteriores e seguintes.

A API do Path no Android suporta curvas Bézier, que são um pouco diferentes das curvas Hermite em relação aos parâmetros. Felizmente, as curvas Hermite podem ser convertidas em curvas Bézier. Aqui está o primeiro código de exemplo que encontrei ao pesquisar no Google. Essa resposta do Stackoverflow também parece fornecer a fórmula.

Você também mencionou o problema das arestas cortantes. Com os dados de entrada que você possui, é impossível detectar se existe um canto agudo real ou apenas uma curva muito íngreme. Se isso se tornar um problema, você poderá tornar a iteração mais adaptável aumentando / diminuindo a etapa rapidamente, conforme necessário.

Edit: Depois de pensar mais, as curvas quadráticas poderiam ser usadas, afinal. Em vez de desenhar uma curva quadrática de p0 a p2 usando p1 como ponto de controle, desenhe-a de p0 a p1 usando um novo ponto p0_1 como pontos de controle. Veja a figura abaixo.

Se p0_1 estiver na interseção das tangentes em p0 e p1, o resultado deverá ser suave. Ainda melhor, como os PathMeasure.getPosTan()retornos também tangentes como terceiro parâmetro, você pode usar tangentes precisas reais em vez de aproximações de pontos adjacentes. Com essa abordagem, você precisa de menos alterações na sua solução existente.

Com base nesta resposta , o ponto de interseção pode ser calculado com a seguinte 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;

Essa solução, no entanto, funciona apenas se u e v não forem negativos. Veja a segunda foto:

Aqui os raios não se cruzam, apesar das linhas, pois u é negativo. Nesse caso, não é possível desenhar uma curva quadrática que se conecte suavemente à anterior. Aqui você precisa das curvas bézier. Você pode calcular os pontos de controle com o método fornecido anteriormente nesta resposta ou derivá-los diretamente das tangentes. Projetar p0 no raio tangente p0 + u * t0 e vice-versa para o outro raio fornece ambos os pontos de controle c0 e c1. Você também pode ajustar a curva usando qualquer ponto entre p0 e c0 em vez de c0, desde que esteja no raio tangente.

Edit2: Se sua posição de desenho está em p1, você pode calcular os pontos de controle de bezier para p2 com o seguinte pseudo-código:

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

Com eles, você pode anexar um caminho de p1 a p2:

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

Substitua as operações de vetor por operações por componente nas matrizes float [ 2 ] para corresponder ao seu código. Você começa inicializando p1 = start;e p2 e p3 são os próximos pontos. p0 é inicialmente indefinido. Para o primeiro segmento em que você ainda não possui p0, é possível usar uma curva quadrática de p1 a p2 com cp2 como ponto de controle. O mesmo para o final do caminho em que você não possui p3, é possível desenhar uma curva quadrática de p1 a p2 com cp1 como ponto de controle. Como alternativa, você pode inicializar p0 = p1 para o primeiro segmento e p3 = p2 para o último segmento. Após cada segmento, você altera os valores p0 = p1; p1 = p2; and p2 = p3;ao avançar.

Ao salvar o caminho, basta salvar todos os pontos p0 ... pN. Não há necessidade de salvar os pontos de controle cp1 e cp2, pois eles podem ser calculados conforme necessário.

Edit3: Como parece difícil obter bons valores de entrada para a geração de curvas, proponho outra abordagem: Use serialization. O Android Path não parece suportá-lo, mas felizmente a classe Region sim. Veja esta resposta para o código. Isso deve fornecer o resultado exato. Pode levar algum espaço no formato serializado, se não for otimizado, mas nesse caso deve ser compactado muito bem. A compactação é fácil no Java Android usando o GZIPOutputStream .

O que o W3C faria?

A internet teve esse problema. O World Wide Web Consortium percebeu. Possui uma solução padrão recomendada desde 1999: Scalable Vector Graphics (SVG) . É um formato de arquivo baseado em XML projetado especificamente para armazenar formas 2D.

" Escalável, o que? "

Gráficos vetoriais escaláveis !

• Escalável : deve ser dimensionado suavemente para qualquer tamanho.
• Vetor : É baseado na noção matemática de vetores .
• Gráficos . É para fazer fotos.

Aqui está a especificação técnica para o SVG versão 1.1.
^{(Não se assuste com o nome; é realmente agradável de ler.)}

Eles escreveram exatamente como as formas básicas, como círculos ou retângulos, devem ser armazenadas. Por exemplo, retângulos têm essas propriedades: x, y, width, height, rx, ry. (O rxe rypode ser usado para cantos arredondados.)

Aqui está um exemplo de retângulo no SVG: (Bem, dois realmente - um para o contorno da tela).

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

Aqui está o que ele representa:

Como diz a especificação, você pode deixar de fora algumas propriedades, se não precisar delas. (Por exemplo, rxe os ryatributos não foram usados ​​aqui.) Sim, há uma tonelada de fragmentos no topo sobre os DOCTYPEquais você não precisará apenas para o seu jogo. Eles são opcionais também.

Caminhos

Caminhos SVG são "caminhos" no sentido de que, se você colocar um lápis em um papel, movê-lo e, eventualmente, levantá-lo novamente , você terá um caminho. Eles não precisam ser fechados , mas podem estar.

Cada caminho tem um datributo (eu gosto de pensar que significa "desenhar"), contendo dados do caminho , uma sequência de comandos para basicamente colocar uma caneta em um papel e movê-lo .

Eles dão o exemplo de um 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>

Veja o datributo no path?

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

A Mé um comando para mover a (seguido de coordenadas), os Ls são para Linha para (com coordenadas) e zé um comando para fechar o caminho (isto é desenhar uma linha de volta para o primeiro local, o que não precisa de coordenadas).

Linhas retas são chatas? Use os comandos Bézier cúbicos ou quadráticos !

A teoria por trás das curvas de Bézier é abordada bem em outros lugares (como na Wikipedia ), mas aqui está o resumo executivo: Béziers tem um ponto inicial e final, com possivelmente muitos pontos de controle que influenciam para onde a curva intermediária está indo.

A especificação também fornece instruções para converter as formas mais básicas em caminhos, caso você queira.

Por que e quando usar SVG

Decida com cuidado se você deseja seguir esse caminho (trocadilhos), porque é realmente muito complicado representar qualquer forma 2D arbitrária no texto! Você pode tornar sua vida muito mais fácil se, por exemplo, se limitar a apenas caminhos feitos de (potencialmente muitas) linhas retas.

Mas se você decidir que deseja formas arbitrárias, o SVG é o caminho a seguir: ele oferece excelente suporte a ferramentas: você pode encontrar muitas bibliotecas para análise de XML no nível inferior e ferramentas de edição do SVG no nível superior.

Independentemente disso, o padrão SVG é um bom exemplo.

Seu código contém um comentário enganoso:

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

Uma curva quadrática de bezier não passa pelo segundo ponto. Se você quiser passar pelo segundo ponto, precisará de um tipo diferente de curva, como uma curva de hermita . Você pode converter as curvas de hermita em beziers para poder usar a classe Path.

Outra sugestão é, em vez de amostrar os pontos, use a média dos pontos que você está pulando.

Outra sugestão é, em vez de usar um ângulo como limite, use a diferença entre a curva real e a curva aproximada. Ângulos não são o verdadeiro problema; o verdadeiro problema é quando o conjunto de pontos não se encaixa em uma curva mais bezier.

Outra sugestão é usar beziers cúbicos, com a tangente de um correspondente à tangente do próximo. Caso contrário (com quadratura), acho que suas curvas não serão iguais.

Para obter uma interseção mais suave de dois caminhos, você pode escalá-los antes do cruzamento e depois depois deles.

Não sei se é uma boa solução, mas funcionou bem para mim. Também é rápido. No meu exemplo, cruzo um caminho arredondado com um padrão que criei (listras). Parece bom mesmo quando dimensionado.

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

Parece ainda suave ao ampliar com canvas.scale ():

Veja a interpolação de polígonos ( http://en.wikipedia.org/wiki/Polynomial_interpolation )

Basicamente, você usa n nós com espaço indeterminado (a interpolação ideal não é indecisa, mas para o seu caso deve ser bom o suficiente e fácil de implementar)

Você termina com um polígono da ordem n que diminui o erro entre sua curva se (<- grande se) sua linha é suave o suficiente.

No seu caso, você está fazendo interpolação linear (ordem 1).

O outro caso (como GriffinHeart recomendado) era usar Splines ( http://en.wikipedia.org/wiki/Spline_interpolation )

Qualquer um dos casos forneceria uma forma de ajuste polinomial para sua curva.

Se o ponto da conversão for apenas para armazenamento, e quando você o renderizar novamente na tela, precisará ser suave, o armazenamento de maior fidelidade possível, e ainda minimizar o armazenamento total necessário para persistir uma determinada curva. para realmente armazenar os atributos do círculo (ou um arco) e redesenha-lo sob demanda.

Origem. Raio. Iniciar / parar ângulos para desenhar o arco.

Se você precisar converter o círculo / arco em pontos de qualquer maneira para renderizar, poderá fazê-lo após carregá-lo do armazenamento, enquanto armazena sempre apenas os atributos.

Existe uma razão para fazer curvas em vez de linhas retas? As linhas retas são mais simples de trabalhar e podem ser renderizadas com eficiência no hardware.

A outra abordagem que vale a pena considerar é armazenar alguns bits por pixel, informando se está dentro, fora ou no contorno da forma. Isso deve compactar bem e pode ser mais eficiente que as linhas para seleções complexas.

Você também pode achar esses artigos interessantes / úteis:

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

Veja a interpolação de curvas - existem alguns tipos diferentes que você pode implementar que ajudarão a suavizar sua curva. Quanto mais pontos você conseguir nesse círculo, melhor. O armazenamento é bastante barato - portanto, se a extração de 360 ​​nós próximos é barata o suficiente (mesmo em 8 bytes de posição; os 360 nós dificilmente podem ser armazenados).

Você pode colocar com algumas amostras de interpolação aqui com apenas quatro pontos; e os resultados são muito bons (o meu favorito é o Bezier para este caso, embora outros possam gritar sobre outras soluções eficazes).

Você pode brincar por aqui também.