Stworzyłem algorytm, który konwertuje dowolną krzywą, tj. Ścieżkę na minimalną liczbę punktów, dzięki czemu mogę zapisać ją w pliku lub bazie danych.

Metoda jest prosta: przesuwa trzy punkty w równych krokach i mierzy kąt między liniami, które tworzą te punkty. Jeśli kąt jest większy niż tolerancja, to tworzy nową krzywą sześcienną do tego punktu. Następnie przesuwa linie do przodu i ponownie mierzy kąt…

Dla tych, którzy znają klasę ścieżki Android - zauważ, że dstPath jest klasą niestandardową, która zapisuje punkty w tablicy, dzięki czemu mogę zapisać punkty później, podczas gdy srcPath jest wynikiem związku regionów i dlatego nie ma dla mnie kluczowych punktów zapisać.

Problem polega na tym, że okrąg nie wygląda gładko, jak widać na tym obrazie, utworzonym przez poniższy kod, gdzie ścieżka źródłowa składa się z idealnego koła i prostokąta. Próbowałem zmienić kąt tolerancji i długość kroków, ale nic nie pomaga. Zastanawiam się, czy możesz zasugerować jakąkolwiek poprawę tego algorytmu lub inne podejście.

EDYCJA: Teraz opublikowałem cały kod dla tych, którzy używają Androida Java, aby mogli łatwo spróbować i eksperymentować.

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

}

Oto porównanie między oryginałem a tym, co wytwarza mój algorytm:

Myślę, że masz dwa problemy:

Niesymetryczne punkty kontrolne

Początkowo zaczynasz od równych odległości między p0 do p1 i p1 do p2. Jeśli kąt tolerancji między segmentami linii nie jest spełniony, przesuwasz p1 i p2 do przodu, ale trzymaj p0 tam, gdzie było. Zwiększa to odległość między p0 a p1, przy jednoczesnym zachowaniu tej samej odległości między p1 a p2. Kiedy tworzysz krzywą, używając p1 jako punktów kontrolnych, może być ona silnie odchylona w kierunku p2 w zależności od tego, ile iteracji minęło od ostatniej krzywej. Gdybyś przesunął p2 dwa razy więcej niż p1, uzyskałbyś równe odległości między punktami.

Krzywe kwadratowe

Jak wspomniano również w innych odpowiedziach, krzywa kwadratowa nie jest w tym przypadku bardzo dobra. Tworzone sąsiednie krzywe powinny mieć wspólny punkt kontrolny i styczną . Gdy twoje dane wejściowe są tylko punktami, Catmull-Rom Spline jest dobrym wyborem do tego celu. Jest to sześcienna krzywa Hermite, w której styczne do punktów kontrolnych są obliczane na podstawie poprzednich i następnych punktów.

Interfejs API ścieżki w Androidzie obsługuje krzywe Béziera, które różnią się nieco od krzywych Hermite pod względem parametrów. Na szczęście krzywe Hermite można przekształcić w krzywe Béziera. Oto pierwszy przykładowy kod, który znalazłem, gdy Googling. Wydaje się, że ta odpowiedź Stackoverflow również daje formułę.

Wspomniał pan również o problemie ostrych krawędzi. Dzięki posiadanym danym wejściowym nie można wykryć, czy istnieje ostry róg, czy tylko bardzo stroma krzywa. Jeśli stanie się to problemem, możesz sprawić, by iteracja była bardziej adaptacyjna, zwiększając / zmniejszając krok w locie w miarę potrzeb.

Edycja: Po dalszym przemyśleniu można jednak zastosować krzywe kwadratowe. Zamiast rysować krzywą kwadratową od p0 do p2, używając p1 jako punktu kontrolnego, narysuj ją od p0 do p1, używając nowego punktu p0_1 jako punktów kontrolnych. Zobacz zdjęcie poniżej.

Jeśli p0_1 znajduje się na przecięciu stycznych w p0 i p1, wynik powinien być gładki. Co więcej, ponieważ PathMeasure.getPosTan()zwraca również styczną jako trzeci parametr, można użyć rzeczywistych dokładnych stycznych zamiast przybliżeń z sąsiednich punktów. Dzięki takiemu podejściu potrzebujesz mniej zmian w istniejącym rozwiązaniu.

Na podstawie tej odpowiedzi punkt przecięcia można obliczyć za pomocą następującego wzoru:

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;

To rozwiązanie działa jednak tylko wtedy, gdy zarówno u, jak i v są nieujemne. Zobacz drugie zdjęcie:

Tutaj promienie nie przecinają się, chociaż linie by się przecięły, ponieważ u jest ujemny. W takim przypadku nie jest możliwe narysowanie krzywej kwadratowej, która płynnie łączy się z poprzednią. Tutaj potrzebujesz krzywych Béziera. Możesz obliczyć punkty kontrolne za pomocą metody podanej wcześniej w tej odpowiedzi lub wyprowadzić je bezpośrednio ze stycznych. Rzutowanie p0 na promień styczny p0 + u * t0 i odwrotnie dla drugiego promienia daje oba punkty kontrolne c0 i c1. Możesz także dostosować krzywą, używając dowolnego punktu między p0 a c0 zamiast c0, o ile leży ona na promieniu stycznym.

Edycja2: Jeśli twoja pozycja rysowania jest w p1, możesz obliczyć punkty kontrolne Beziera do p2 za pomocą następującego pseudo kodu:

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

Za ich pomocą możesz dołączyć ścieżkę od p1 do p2:

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

Zamień operacje wektorowe na operacje na komponentach na tablicach pływających [ 2 ], aby dopasować je do kodu. Zaczynasz od inicjalizacji, p1 = start;a p2 i p3 to kolejne punkty. p0 jest początkowo niezdefiniowany. Dla pierwszego segmentu, w którym nie masz jeszcze p0, możesz użyć krzywej kwadratowej od p1 do p2 z cp2 jako punktem kontrolnym. To samo na końcu ścieżki, na której nie masz p3, możesz narysować krzywą kwadratową od p1 do p2 z cp1 jako punktem kontrolnym. Alternatywnie możesz zainicjować p0 = p1 dla pierwszego segmentu i p3 = p2 dla ostatniego segmentu. Po każdym segmencie przesuwasz wartości p0 = p1; p1 = p2; and p2 = p3;podczas ruchu do przodu.

Zapisując ścieżkę, zapisujesz wszystkie punkty p0 ... pN. Nie trzeba zapisywać punktów kontrolnych cp1 i cp2, ponieważ można je obliczyć w razie potrzeby.

Edycja3: Ponieważ wydaje się, że trudno jest uzyskać dobre wartości wejściowe do generowania krzywej, proponuję inne podejście: użyj serializacji. Wygląda na to, że Ścieżka Androida nie obsługuje tego, ale na szczęście klasa Region ma. Zobacz tę odpowiedź dotyczącą kodu. To powinno dać ci dokładny wynik. Jeśli nie jest zoptymalizowany, może zająć trochę miejsca w postaci serializowanej, ale w takim przypadku powinien się bardzo dobrze kompresować. Kompresja jest łatwa w Javie Androida za pomocą GZIPOutputStream .

Co zrobiłby W3C?

Internet miał ten problem. World Wide Web Consortium zauważył. Ma zalecane standardowe rozwiązanie od 1999 roku: Scalable Vector Graphics (SVG) . Jest to format pliku oparty na języku XML , specjalnie zaprojektowany do przechowywania kształtów 2D.

„Co skalowalne? ”

Skalowalna grafika wektorowa !

• Skalowalne : ma na celu płynne skalowanie do dowolnego rozmiaru.
• Wektor : Opiera się na matematycznym pojęciu wektorów .
• Grafika . Ma to na celu robienie zdjęć.

Oto specyfikacja techniczna SVG w wersji 1.1.
^{(Nie bój się nazwy; naprawdę jest przyjemnie czytać.)}

Zapisali dokładnie, jak mają być przechowywane podstawowe kształty, takie jak koła lub prostokąty . Na przykład prostokąty mają te właściwości: x, y, width, height, rx, ry. (Za pomocą rxi rymożna używać zaokrąglonych narożników.)

Oto ich przykładowy prostokąt w SVG: (Cóż, dwa naprawdę - jeden dla obrysu płótna).

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

Oto, co reprezentuje:

Jak podano w specyfikacji, możesz pominąć niektóre właściwości, jeśli ich nie potrzebujesz. (Na przykład rxi ryatrybuty nie zostały tutaj użyte.) Tak, na górze jest mnóstwo cruft, o DOCTYPEktórych nie będziesz potrzebować tylko w swojej grze. Są też opcjonalne.

Ścieżki

Ścieżki SVG są „ścieżkami” w tym sensie, że jeśli położysz ołówek na papierze, przesuniesz go i ostatecznie podniesiesz , masz ścieżkę. Nie muszą być zamknięte , ale mogą być.

Każda ścieżka ma datrybut (lubię myśleć, że oznacza „rysować”), zawierający dane ścieżki , sekwencję poleceń polegającą na po prostu umieszczeniu pióra na papierze i przesuwaniu go .

Podają przykład trójkąta:

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

Zobacz datrybut w path?

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

MJest komenda do Przenieś do (następnie współrzędnych), że Lów są za linię do (ze współrzędnymi) i zjest polecenie, aby zamknąć ścieżkę (czyli narysować linię z powrotem do pierwszego miejsca, to nie potrzeba współrzędne).

Proste linie są nudne? Użyj sześciennych lub kwadratowych poleceń Béziera!

Teoria leżąca u podstaw krzywych Béziera jest dobrze omówiona gdzie indziej (np. Na Wikipedii ), ale oto streszczenie: Béziers ma punkt początkowy i końcowy, z możliwie wieloma punktami kontrolnymi, które wpływają na to, gdzie przebiega krzywa pomiędzy nimi.

Specyfikacja zawiera również instrukcje dotyczące konwertowania najbardziej podstawowych kształtów na ścieżki w razie potrzeby.

Dlaczego i kiedy używać SVG

Ostrożnie zdecyduj, czy chcesz zejść tą ścieżką (zamierzona gra słów), ponieważ reprezentowanie dowolnego dowolnego kształtu 2D w tekście jest dość skomplikowane! Możesz znacznie ułatwić sobie życie, jeśli np. Ograniczysz się do ścieżek utworzonych z (potencjalnie naprawdę wielu) linii prostych.

Ale jeśli zdecydujesz, że chcesz mieć dowolne kształty, SVG jest właściwą drogą: ma doskonałą obsługę narzędzi: możesz znaleźć wiele bibliotek do analizy XML na niskim poziomie i narzędzia edytora SVG na wysokim poziomie.

Niezależnie od tego standard SVG stanowi dobry przykład.

Twój kod zawiera mylący komentarz:

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

Kwadratowa krzywa Béziera nie przechodzi przez drugi punkt. Jeśli chcesz przejść przez drugi punkt, potrzebujesz innego rodzaju krzywej, takiej jak krzywa pustelnika . Możesz być w stanie przekształcić krzywe pustelnika w beziersy, abyś mógł użyć klasy Path.

Inną sugestią jest zamiast próbkowania punktów, użyj średniej liczby pomijanych punktów.

Inną sugestią jest zamiast używania kąta jako progu, użyj różnicy między krzywą rzeczywistą a krzywą przybliżoną. Kąty nie są prawdziwym problemem; prawdziwym problemem jest to, że zestaw punktów nie pasuje do krzywej Beziera.

Inną sugestią jest użycie sześciennych ramek, z których styczna jednego pasuje do stycznej następnego. W przeciwnym razie (z kwadratami) myślę, że twoje krzywe nie pasują gładko.

Aby uzyskać gładsze skrzyżowanie dwóch ścieżek, możesz przeskalować je przed skrzyżowaniem, a następnie skalować w dół.

Nie wiem, czy to dobre rozwiązanie, ale dla mnie zadziałało. Jest także szybki. W moim przykładzie przecinam zaokrągloną ścieżkę z utworzonym wzorem (paskami). Wygląda dobrze nawet po skalowaniu.

Oto mój kod:

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

Wygląda gładko podczas powiększania za pomocą canvas.scale ():

Spójrz na interpolację wielokątów ( http://en.wikipedia.org/wiki/Polynomial_interpolation )

Zasadniczo bierzesz n równomiernych węzłów (optymalna interpolacja nie jest równa, ale w twoim przypadku powinna być wystarczająco dobra i łatwa do wdrożenia)

Otrzymujesz wielokąt rzędu n, który zmniejsza błąd między twoją krzywą, jeśli (<- duża, jeśli) twoja linia jest wystarczająco gładka .

W twoim przypadku wykonujesz interpolację liniową (rzędu 1).

Innym przypadkiem (jak zalecił GriffinHeart ) było użycie Spline ( http://en.wikipedia.org/wiki/Spline_interpolation )

Każdy przypadek da ci jakąś formę dopasowania wielomianu do twojej krzywej.

Jeśli punktem konwersji jest tylko przechowywanie, a po wyrenderowaniu go z powrotem na ekranie potrzebujesz, aby był płynny, to najwyższą możliwą pamięcią, jaką możesz uzyskać, przy jednoczesnym zminimalizowaniu całkowitego miejsca wymaganego do utrzymania danej krzywej, może być aby faktycznie przechowywać atrybuty koła (lub raczej łuku) i ponownie rysować je na żądanie.

Pochodzenie. Promień. Kąty start / stop do rysowania łuku.

Jeśli i tak musisz przekonwertować okrąg / łuk na punkty w celu renderowania, możesz to zrobić po załadowaniu go z pamięci, zawsze przechowując tylko atrybuty.

Czy istnieje powód, aby wybierać łuki zamiast linii prostych? Proste linie są prostsze w obsłudze i mogą być wydajnie renderowane sprzętowo.

Innym podejściem wartym rozważenia jest przechowywanie kilku bitów na piksel, stwierdzając, czy jest on wewnątrz, na zewnątrz lub na obrysie kształtu. Powinno to dobrze kompresować i może być bardziej wydajne niż wiersze przy złożonych selekcjach.

Te artykuły mogą być również interesujące / przydatne:

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

Spójrz na interpolację krzywej - możesz zaimplementować kilka różnych typów, które pomogą wygładzić twoją krzywą. Im więcej punktów można zdobyć w tym kręgu, tym lepiej. Przechowywanie jest dość tanie - więc jeśli wyodrębnienie 360 ​​zamkniętych węzłów jest wystarczająco tanie (nawet przy 8 bajtach dla pozycji; przechowywanie 360 ​​węzłów nie jest drogie).

Możesz umieścić tutaj niektóre próbki interpolacji , mając tylko cztery punkty; a wyniki są całkiem dobre (moim ulubionym jest Bezier w tym przypadku, chociaż inni mogą wdawać się w inne skuteczne rozwiązania).

Można bawić się tutaj , zbyt.