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:
dlaczego nie użyć b-splajnów?
—
GriffinHeart
jeśli wiesz, że chodzi o okrąg i prostokąt, dlaczego nie przechowywać okręgu i prostokąta? I w formie uogólnionej - jakiekolwiek wygenerowane dane wejściowe są prawdopodobnie rozsądnym formatem do przechowywania. Jeśli szukasz schematu kompresji, który wydaje się innym pytaniem (lub przynajmniej potrzebowalibyśmy znacznie więcej informacji na temat danych źródłowych być pomocnym).
—
Jeff Gates
Może to być dowolny nieprzewidywalny kształt, jak powiedziałem w pierwszym zdaniu - okrąg i prostokąt są tutaj tylko przykładem testowym.
—
Lumis
@Lumis naprawdę powinieneś spojrzeć na b-splajny, po to są. Czy jest jakiś powód, aby spróbować wdrożyć własne rozwiązanie?
—
GriffinHeart
Cóż, klasa ścieżki zbuduje te krzywe z splajnami, więc już go używasz. Mam inną sugestię, mniej zorientowaną na matematykę: zamiast zapisywać punkty, zapisz dane wprowadzone przez użytkownika (wzorzec poleceń) i powtórz je, aby zbudować ten sam „obraz”.
—
GriffinHeart
