Ich habe einen Algorithmus erstellt, der jede Kurve, dh jeden Pfad, in eine Mindestanzahl von Punkten konvertiert, damit ich sie in einer Datei oder Datenbank speichern kann.
Die Methode ist einfach: Sie bewegt drei Punkte in gleichen Schritten und misst den Winkel zwischen den Linien, die diese Punkte bilden. Wenn der Winkel größer als die Toleranz ist, wird eine neue kubische Kurve zu diesem Punkt erstellt. Dann werden die Linien nach vorne verschoben und der Winkel erneut gemessen…
Für diejenigen, die Android Path Class kennen - Beachten Sie, dass der dstPath eine benutzerdefinierte Klasse ist, die die Punkte in einem Array aufzeichnet, damit ich die Punkte später speichern kann, während der srcPath das Ergebnis einer Regions-Union ist und daher keine Schlüsselpunkte für mich hat speichern.
Das Problem ist, dass der Kreis nicht glatt aussieht, wie Sie in diesem Bild sehen können, das durch den folgenden Code erzeugt wird, in dem der Quellpfad aus einem perfekten Kreis und einem Rechteck besteht. Ich habe versucht, den Toleranzwinkel und die Schrittlänge zu ändern, aber nichts hilft. Ich frage mich, ob Sie eine Verbesserung dieses Algorithmus oder einen anderen Ansatz vorschlagen können.
BEARBEITEN: Ich habe jetzt den gesamten Code für diejenigen veröffentlicht, die Android Java verwenden, damit sie es einfach ausprobieren und experimentieren können.
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();
}
}
}
Hier ist ein Vergleich zwischen dem Original und dem, was mein Algorithmus erzeugt:
Antworten:
Ich denke, Sie haben zwei Probleme:
Nicht symmetrische Kontrollpunkte
Sie beginnen zunächst mit gleichen Abständen zwischen p0 bis p1 und p1 bis p2. Wenn der Toleranzwinkel zwischen den Liniensegmenten nicht eingehalten wird, bewegen Sie p1 und p2 vorwärts, aber behalten p0 bei, wo es war. Dies erhöht den Abstand zwischen p0 und p1, während der Abstand zwischen p1 und p2 gleich bleibt. Wenn Sie eine Kurve mit p1 als Kontrollpunkt erstellen, kann sie stark in Richtung p2 verschoben sein, je nachdem, wie viele Iterationen seit der letzten Kurve vergangen sind. Wenn Sie p2 doppelt so weit bewegen wie p1, erhalten Sie gleichmäßige Abstände zwischen den Punkten.
Quadratische Kurven
Wie auch in anderen Antworten erwähnt, ist die quadratische Kurve für diesen Fall nicht sehr gut. Benachbarte Kurven, die Sie erstellen, sollten einen Kontrollpunkt und eine Tangente gemeinsam haben . Wenn Ihre Eingabedaten nur Punkte sind, verwenden Sie Catmull-Rom-Spline eine gute Wahl für diesen Zweck. Es ist eine kubische Hermite-Kurve, bei der die Tangenten für die Kontrollpunkte aus den vorherigen und nächsten Punkten berechnet werden.
Die Pfad-API in Android unterstützt Bézier-Kurven, die sich hinsichtlich der Parameter geringfügig von Hermite-Kurven unterscheiden. Glücklicherweise können Hermite-Kurven in Bézier-Kurven umgewandelt werden. Hier ist der erste Beispielcode, den ich beim Googeln gefunden habe. Diese Stackoverflow-Antwort scheint auch die Formel zu geben.
Sie haben auch das Problem der scharfen Kanten erwähnt. Mit den eingegebenen Daten ist es unmöglich zu erkennen, ob es tatsächlich eine scharfe Ecke oder nur eine sehr steile Kurve gibt. Wenn dies zu einem Problem wird, können Sie die Iteration anpassungsfähiger machen, indem Sie den Direktschritt nach Bedarf vergrößern / verkleinern.
Edit: Nach weiterem Überlegen könnten doch quadratische Kurven verwendet werden. Anstatt eine quadratische Kurve von p0 nach p2 mit p1 als Kontrollpunkt zu zeichnen, zeichnen Sie sie von p0 nach p1 mit einem neuen Punkt p0_1 als Kontrollpunkt. Siehe das Bild unten.
Wenn sich p0_1 im Schnittpunkt der Tangenten in p0 und p1 befindet, sollte das Ergebnis glatt sein. Seitdem noch besser
PathMeasure.getPosTan()
auch Tangente als dritter Parameter zurückgegeben wird, können Sie tatsächlich genaue Tangenten anstelle von Approximationen benachbarter Punkte verwenden. Mit diesem Ansatz müssen Sie weniger Änderungen an Ihrer vorhandenen Lösung vornehmen.Basierend auf dieser Antwort kann der Schnittpunkt mit der folgenden Formel berechnet werden:
Diese Lösung funktioniert jedoch nur, wenn sowohl u als auch v nicht negativ sind. Siehe das zweite Bild:
Hier kreuzen sich die Strahlen nicht, obwohl die Linien dies tun würden, da u negativ ist. In diesem Fall ist es nicht möglich, eine quadratische Kurve zu zeichnen, die problemlos mit der vorherigen verbunden werden kann. Hier braucht man die schöneren Kurven. Sie können die Kontrollpunkte dafür entweder mit der zuvor in dieser Antwort angegebenen Methode berechnen oder sie direkt aus den Tangenten ableiten. Das Projizieren von p0 auf den Tangentenstrahl p0 + u * t0 und umgekehrt für den anderen Strahl ergibt beide Kontrollpunkte c0 und c1. Sie können die Kurve auch anpassen, indem Sie einen beliebigen Punkt zwischen p0 und c0 anstelle von c0 verwenden, solange er auf dem Tangentenstrahl liegt.
Edit2: Wenn Ihre Zeichnungsposition in p1 ist, können Sie die Bezier-Steuerpunkte zu p2 mit dem folgenden Pseudocode berechnen:
Mit diesen können Sie einen Pfad von p1 nach p2 anhängen:
Ersetzen Sie die Vektoroperationen durch Pro-Komponenten-Operationen für float [ 2 ] -Arrays, damit sie Ihrem Code entsprechen. Sie beginnen mit der Initialisierung
p1 = start;
und p2 und p3 sind die nächsten Punkte. p0 ist anfänglich undefiniert. Für das erste Segment, in dem Sie p0 noch nicht haben, können Sie eine quadratische Kurve von p1 nach p2 mit cp2 als Kontrollpunkt verwenden. Dasselbe gilt für das Ende des Pfades, auf dem Sie nicht über p3 verfügen. Sie können eine quadratische Kurve von p1 nach p2 mit cp1 als Kontrollpunkt zeichnen. Alternativ können Sie p0 = p1 für das erste Segment und p3 = p2 für das letzte Segment initialisieren. Nach jedem Segment verschieben Sie die Werte,p0 = p1; p1 = p2; and p2 = p3;
wenn Sie sich vorwärts bewegen.Wenn Sie den Pfad speichern, speichern Sie einfach alle Punkte p0 ... pN. Die Kontrollpunkte cp1 und cp2 müssen nicht gespeichert werden, da sie nach Bedarf berechnet werden können.
Edit3: Da es anscheinend schwierig ist, gute Eingabewerte für die Kurvenerzeugung zu erhalten, schlage ich einen anderen Ansatz vor: Verwenden Sie die Serialisierung. Android Path scheint dies nicht zu unterstützen, glücklicherweise jedoch die Region-Klasse. Siehe diese Antwort für den Code. Dies sollte Ihnen das genaue Ergebnis liefern. Es kann etwas Platz in der serialisierten Form beanspruchen, wenn es nicht optimiert ist, aber in diesem Fall sollte es sehr gut komprimiert werden. In Android Java ist die Komprimierung mit GZIPOutputStream einfach .
quelle
Was würde der W3C tun?
Das Internet hatte dieses Problem. Das World Wide Web Consortium hat es bemerkt. Seit 1999 gibt es eine empfohlene Standardlösung : Scalable Vector Graphics (SVG) . Es ist ein XML- basiertes Dateiformat, das speziell zum Speichern von 2D-Formen entwickelt wurde.
" Skalierbar - was? "
Skalierbare Vektorgrafiken !
Hier ist die technische Spezifikation für SVG Version 1.1.
(Hab keine Angst vor dem Namen; es ist eigentlich angenehm zu lesen.)
Sie haben genau aufgeschrieben, wie Grundformen wie Kreise oder Rechtecke gespeichert werden sollen. Zum Beispiel Rechtecken haben diese Eigenschaften:
x
,y
,width
,height
,rx
,ry
. (Dasrx
undry
kann für abgerundete Ecken verwendet werden.)Hier ist ihr Beispielrechteck in SVG: (Nun, zwei wirklich - eines für den Canvas-Umriss.)
Hier ist, was es darstellt:
Wie die Spezifikation besagt, können Sie einige der Eigenschaften weglassen, wenn Sie sie nicht benötigen. (Zum Beispiel
rx
undry
Attribute wurden hier nicht verwendet.) Ja, es gibt eine Tonne Cruft oben, überDOCTYPE
die Sie nicht nur für Ihr Spiel benötigen. Sie sind auch optional.Pfade
SVG- Pfade sind "Pfade" in dem Sinne, dass Sie einen Pfad haben , wenn Sie einen Stift auf ein Papier legen, es bewegen und schließlich wieder anheben . Sie haben nicht haben werden geschlossen , aber sie auch sein mögen.
Jeder Pfad hat ein
d
Attribut (ich denke, es steht für "Zeichnen"), das Pfaddaten enthält , eine Folge von Befehlen, mit denen man im Grunde nur einen Stift auf ein Papier legt und es herumbewegt .Sie geben das Beispiel eines Dreiecks:
Siehe das
d
Attribut in derpath
?Das
M
ist ein Befehl für Verschieben nach (gefolgt von Koordinaten), dasL
s steht für Linie nach (mit Koordinaten) undz
ist ein Befehl zum Schließen des Pfades (dh eine Linie zurück zum ersten Ort ziehen, der keine Koordinaten benötigt).Gerade Linien sind langweilig? Verwenden Sie die kubischen oder quadratischen Bézier-Befehle!
Die Theorie hinter den Bézier-Kurven wird an anderer Stelle (z. B. bei Wikipedia ) ausführlich behandelt. Hier jedoch die Zusammenfassung: Béziers haben einen Start- und einen Endpunkt mit möglicherweise vielen Kontrollpunkten, die die Richtung der dazwischen liegenden Kurve beeinflussen.
Die Spezifikation enthält auch Anweisungen zum Konvertieren der meisten Grundformen in Pfade, falls Sie dies möchten.
Warum und wann wird SVG verwendet?
Entscheiden Sie sorgfältig, ob Sie diesen Weg gehen möchten (Wortspiel beabsichtigt), da es sehr kompliziert ist, beliebige 2D-Formen im Text darzustellen! Sie können Ihr Leben so viel einfacher machen, wenn Sie sich z. B. auf Pfade beschränken, die aus (möglicherweise wirklich vielen) geraden Linien bestehen.
Wenn Sie sich jedoch für beliebige Formen entscheiden, ist SVG der richtige Weg: Es bietet eine hervorragende Toolunterstützung: Auf niedriger Ebene finden Sie viele Bibliotheken für XML-Parsing und auf hoher Ebene SVG-Editor-Tools .
Unabhängig davon ist der SVG-Standard ein gutes Beispiel.
quelle
Ihr Code enthält einen irreführenden Kommentar:
Eine quadratische Bezier - Kurve ist nicht gehen durch den zweiten Punkt. Wenn Sie den zweiten Punkt durchlaufen möchten, benötigen Sie einen anderen Kurventyp , z. B. eine Hermitenkurve . Möglicherweise können Sie die Einsiedlerkurven in Beziere konvertieren, damit Sie die Path-Klasse verwenden können.
Ein weiterer Vorschlag ist, anstatt die Punkte abzutasten, den Mittelwert der Punkte zu verwenden, die Sie überspringen.
Ein weiterer Vorschlag besteht darin, anstelle eines Winkels als Schwellenwert die Differenz zwischen der tatsächlichen Kurve und der ungefähren Kurve zu verwenden. Winkel sind nicht das eigentliche Problem. Das eigentliche Problem ist, wenn die Punktmenge nicht zu einer Bezierkurve passt.
Ein weiterer Vorschlag ist die Verwendung von kubischen Beziern, wobei der Tangens des einen mit dem Tangens des nächsten übereinstimmt. Andernfalls (mit Quadraten) passen Ihre Kurven meiner Meinung nach nicht reibungslos zusammen.
quelle
Um eine gleichmäßigere Schnittmenge zwischen zwei Pfaden zu erzielen, können Sie diese vor der Schnittmenge vergrößern und anschließend verkleinern.
Ich weiß nicht, ob es eine gute Lösung ist, aber es hat bei mir gut funktioniert. Es ist auch schnell. In meinem Beispiel schneide ich einen abgerundeten Pfad mit einem von mir erstellten Muster (Streifen). Es sieht auch im skalierten Zustand gut aus.
Hier mein Code:
Sieht beim Zoomen mit canvas.scale () noch flüssig aus:
quelle
Schauen Sie sich die Polygoninterpolation an ( http://en.wikipedia.org/wiki/Polynomial_interpolation) )
Grundsätzlich nehmen Sie n Knoten mit gleichem Abstand (optimale Interpolation ist nicht gleich, sollte aber für Ihren Fall gut genug und einfach zu implementieren sein)
Sie erhalten ein Polygon der Ordnung n, das den Fehler zwischen Ihrer Kurve verringert, wenn (<- big if) Ihre Linie glatt genug ist.
In Ihrem Fall führen Sie eine lineare Interpolation (Reihenfolge 1) durch.
Der andere Fall (wie von GriffinHeart empfohlen) war die Verwendung von Splines ( http://en.wikipedia.org/wiki/Spline_interpolation ).
In beiden Fällen erhalten Sie eine Art Polynom, das für Ihre Kurve geeignet ist.
quelle
Wenn der Konvertierungspunkt nur für die Speicherung bestimmt ist und wenn Sie ihn wieder auf dem Bildschirm rendern, müssen Sie ihn reibungslos wiedergeben, um den Speicher mit der höchsten Wiedergabetreue zu erhalten und gleichzeitig den Gesamtspeicher zu minimieren, der erforderlich ist, um eine bestimmte Kurve beizubehalten um die Attribute des Kreises (oder eher eines Bogens) tatsächlich zu speichern und ihn nach Bedarf neu zu zeichnen.
Ursprung. Radius. Start- / Stoppwinkel zum Zeichnen des Bogens.
Wenn Sie den Kreis / Bogen ohnehin zum Rendern in Punkte konvertieren müssen, können Sie dies möglicherweise beim Laden aus dem Speicher tun, während Sie immer nur die Attribute speichern.
quelle
Gibt es einen Grund für Kurven im Gegensatz zu geraden Linien? Gerade Linien sind einfacher zu bearbeiten und können in Hardware effizient gerendert werden.
Der andere in Betracht zu ziehende Ansatz besteht darin, ein paar Bits pro Pixel zu speichern und anzugeben, ob es sich um eine Innen-, Außen- oder Außenkontur der Form handelt. Dies sollte gut komprimiert werden und ist möglicherweise effizienter als Zeilen für komplexe Auswahlen.
Diese Artikel könnten Sie auch interessieren / nützlich finden:
quelle
Schauen Sie sich die Kurveninterpolation an - es gibt einige verschiedene Arten, die Sie implementieren können, um Ihre Kurve zu glätten. Je mehr Punkte Sie auf diesem Kreis sammeln können, desto besser. Speicher ist ziemlich billig - wenn also das Extrahieren von 360 Knoten in der Nähe billig genug ist (selbst bei 8 Bytes für die Position; das Speichern von 360 Knoten ist kaum teuer).
Sie können mit einigen Interpolation Proben stellen hier mit nur vier Punkten; und die Ergebnisse sind ziemlich gut (mein Favorit ist der Bezier für diesen Fall, obwohl andere vielleicht andere effektive Lösungen vorschlagen).
Sie können in spielen , um hier auch.
quelle