Я создал алгоритм, который преобразует любую кривую, т.е. путь, в минимальное количество точек, чтобы я мог сохранить ее в файл или базу данных.

Метод прост: он перемещает три точки равными шагами и измеряет угол между линиями, которые образуют эти точки. Если угол больше, чем допуск, он создает новую кубическую кривую для этой точки. Затем он перемещает линии вперед и снова измеряет угол ...

Для тех, кто знает класс Android Path - обратите внимание, что dstPath - это пользовательский класс, который записывает точки в массив, поэтому я могу сохранить их позже, в то время как srcPath является результатом объединения регионов и поэтому не имеет для меня ключевых точек. сохранить.

Проблема в том, что окружность не выглядит гладкой, как вы можете видеть на этом изображении, созданном с помощью приведенного ниже кода, где исходный путь состоит из идеального круга и прямоугольника. Я пытался изменить угол допуска и длину шагов, но ничего не помогало. Интересно, можете ли вы предложить какое-либо улучшение этого алгоритма или другой подход.

РЕДАКТИРОВАТЬ: я сейчас опубликовал весь код для тех, кто использует Android Java, чтобы они могли легко попробовать и экспериментировать.

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

}

Вот сравнение между оригиналом и тем, что производит мой алгоритм:

Я думаю, что у вас есть две проблемы:

Несимметричные контрольные точки

Сначала вы начинаете с равных расстояний от p0 до p1 и от p1 до p2. Если угол допуска между отрезками не достигнут, вы перемещаете p1 и p2 вперед, но оставляете p0 на прежнем уровне. Это увеличивает расстояние между p0 до p1, сохраняя расстояние между p1 до p2 одинаковым. Когда вы создаете кривую, используя p1 в качестве контрольных точек, она может быть сильно смещена в сторону p2 в зависимости от того, сколько итераций прошло с момента последней кривой. Если бы вы переместили p2 вдвое больше, чем p1, вы бы получили равные расстояния между точками.

Квадратичные кривые

Как уже упоминалось в других ответах, квадратичная кривая не очень хороша для этого случая. Соседние кривые, которые вы создаете, должны иметь общую контрольную точку и касательную . Когда ваши входные данные представляют собой просто точки, Catmull-Rom Spline является хорошим выбором для этой цели. Это кубическая кривая Эрмита, в которой касательные для контрольных точек рассчитываются по предыдущим и следующим точкам.

API-интерфейс Path в Android поддерживает кривые Безье, которые в отношении параметров немного отличаются от кривых Эрмита. К счастью, кривые Эрмита можно преобразовать в кривые Безье. Вот первый пример кода, который я нашел, когда гуглил. Этот ответ Stackoverflow также, кажется, дает формулу.

Вы также упомянули проблему острых краев. Имея входные данные, вы не сможете определить, есть ли фактический острый угол или просто очень крутая кривая. Если это становится проблемой, вы можете сделать итерацию более адаптивной, увеличивая / уменьшая шаг по мере необходимости.

Изменить: После дальнейшего размышления квадратные кривые могут быть использованы в конце концов. Вместо того, чтобы рисовать квадратную кривую от p0 до p2, используя p1 в качестве контрольной точки, нарисуйте ее из p0 в p1, используя новую точку p0_1 в качестве контрольных точек. Смотрите картинку ниже.

Если p0_1 находится на пересечении касательных в p0 и p1, результат должен быть гладким. Более того, поскольку PathMeasure.getPosTan()в качестве третьего параметра также возвращается касательная, вы можете использовать фактические точные касательные вместо приближений от соседних точек. При таком подходе вам нужно меньше изменений в существующем решении.

Основываясь на этом ответе , точка пересечения может быть рассчитана по следующей формуле:

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;

Это решение, однако, работает, только если и u, и v неотрицательны. Смотрите вторую картинку:

Здесь лучи не пересекаются, хотя линии будут, так как и отрицательно. В этом случае невозможно нарисовать квадратичную кривую, которая бы плавно соединялась с предыдущей. Здесь вам нужны кривые Безье. Вы можете рассчитать контрольные точки для него либо с помощью метода, приведенного ранее в этом ответе, либо получить их непосредственно из касательных. Проекция p0 на касательный луч p0 + u * t0 и наоборот для другого луча дает обе контрольные точки c0 и c1. Вы также можете настроить кривую, используя любую точку между p0 и c0 вместо c0, пока она лежит на касательном луче.

Edit2: если ваша позиция рисования в p1, вы можете вычислить контрольные точки Безье для p2 с помощью следующего псевдокода:

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

С их помощью вы можете добавить путь от p1 до p2:

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

Замените векторные операции на отдельные операции над массивами float [ 2 ], чтобы они соответствовали вашему коду. Вы начинаете с инициализации, p1 = start;а p2 и p3 являются следующими точками. p0 изначально не определено. Для первого сегмента, где у вас еще нет p0, вы можете использовать квадратичную кривую от p1 до p2 с cp2 в качестве контрольной точки. То же самое для конца пути, где у вас нет p3, вы можете нарисовать квадратную кривую от p1 до p2 с cp1 в качестве контрольной точки. В качестве альтернативы вы можете инициализировать p0 = p1 для первого сегмента и p3 = p2 для последнего сегмента. После каждого сегмента вы сдвигаете значения p0 = p1; p1 = p2; and p2 = p3;при движении вперед.

Когда вы сохраняете путь, вы просто сохраняете все точки p0 ... pN. Нет необходимости сохранять контрольные точки cp1 и cp2, так как они могут быть рассчитаны по мере необходимости.

Edit3: так как кажется, что трудно получить хорошие входные значения для генерации кривой, я предлагаю другой подход: использовать сериализацию. Android Path не поддерживает его, но, к счастью, класс Region поддерживает. Смотрите этот ответ для кода. Это должно дать вам точный результат. Это может занять некоторое пространство в сериализованной форме, если он не оптимизирован, но в этом случае он должен сжиматься очень хорошо. Сжатие легко в Android Java, используя GZIPOutputStream .

Что бы сделал W3C?

В интернете была эта проблема. World Wide Web Consortium заметил. Он имеет рекомендованную стандартное решение с 1999 года: Scalable Vector Graphics (SVG) . Это формат файла на основе XML , специально разработанный для хранения 2D-фигур.

" Масштабируемый-что? "

Масштабируемая векторная графика !

• Масштабируемость : предназначена для плавного масштабирования до любого размера.
• Вектор : Он основан на математическом понятии векторов .
• Графика . Он предназначен для создания фотографий.

Вот техническая спецификация для SVG версии 1.1.
^{(Не пугайтесь названия; на самом деле это приятно читать.)}

Они записали, как именно должны храниться основные фигуры, такие как круги или прямоугольники . Например, прямоугольники имеют следующие свойства: x, y, width, height, rx, ry. (The rxи ryможет быть использована для скругленных углов.)

Вот их пример прямоугольника в SVG: (Ну, два действительно - один для контура холста.)

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

Вот что это представляет:

Как указано в спецификации, вы можете оставить некоторые свойства, если они вам не нужны. (Например, rxи ryатрибуты здесь не использовались.) Да, наверху есть куча хлама, DOCTYPEкоторый вам не понадобится только для вашей игры. Они тоже не обязательны.

пути

Пути SVG - это «пути» в том смысле, что если вы положите карандаш на бумагу, переместите его и, в конце концов, поднимите его , у вас будет путь. Они не должны быть закрыты , но они могут быть.

У каждого пути есть dатрибут (мне нравится думать, что он обозначает «рисовать»), содержащий данные о пути , последовательность команд, которые обычно просто помещают перо на бумагу и перемещают его .

Они дают пример треугольника:

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

Смотрите dатрибут в path?

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

MЯвляется командой для Переместить в ( а затем по координатам), то Ls является для линии к (с координатами) и zявляется командой , чтобы закрыть путь (т.е. нарисовать линию назад к первой локации, то не нужна координаты).

Прямые линии скучные? Используйте кубические или квадратичные команды Безье!

Теория, лежащая в основе кривых Безье, хорошо освещена в других местах (например, в Википедии ), но вот краткое изложение: у Безье есть начальная и конечная точки, возможно, со многими контрольными точками, которые влияют на то, где проходит кривая между ними.

В спецификации также приведены инструкции по преобразованию большинства основных фигур в контуры, если вы захотите.

Почему и когда использовать SVG

Тщательно решите, хотите ли вы пойти по этому пути (каламбур), потому что действительно довольно сложно представить любую произвольную 2D фигуру в тексте! Вы можете сделать свою жизнь намного проще, если, например, ограничите себя только путями, состоящими из (потенциально очень многих) прямых линий.

Но если вы решите, что вам нужны произвольные формы, SVG - это то, что вам нужно: у него есть отличная поддержка инструментов: вы можете найти множество библиотек для анализа XML на низком уровне и инструменты редактора SVG на высоком уровне.

Несмотря на это, стандарт SVG является хорошим примером.

Ваш код содержит вводящий в заблуждение комментарий:

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

Квадратичная кривая Безье не проходит через вторую точку. Если вы хотите пройти через вторую точку, вам нужен другой тип кривой, такой как кривая Эрмита . Возможно, вы сможете преобразовать кривые Эрмита в кривые Безье, чтобы вы могли использовать класс Path.

Другое предложение - вместо выборки точек используйте среднее значение точек, которые вы пропускаете.

Другое предложение - вместо использования угла в качестве порога использовать разницу между фактической кривой и приблизительной кривой. Углы не настоящая проблема; реальная проблема заключается в том, что множество точек не соответствует кривой Безье.

Другое предложение состоит в том, чтобы использовать кубические Безье, тангенс одного совпадает с тангенсом следующего. В противном случае (с квадратиками) я думаю, что ваши кривые не будут гладко совпадать.

Чтобы получить более плавное пересечение двух путей, вы можете масштабировать их до пересечения и уменьшать их после.

Я не знаю, хорошее ли это решение, но оно хорошо сработало для меня. Это также быстро. В моем примере я пересекаю округленный путь с созданным мной узором (полосами). Это выглядит хорошо, даже когда масштабируется.

Вот мой код:

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

Выглядит по-прежнему гладко при масштабировании с canvas.scale ():

Посмотрите на интерполяцию полигонов ( http://en.wikipedia.org/wiki/Polynomial_interpolation )

По сути, вы берете n равноотстоящих узлов (оптимальная интерполяция не равнораспределена, но для вашего случая она должна быть достаточно хорошей и простой в реализации)

В итоге получается многоугольник порядка n, который уменьшает ошибку между вашей кривой, если (<- большой, если) ваша линия достаточно гладкая .

В вашем случае вы делаете линейную (порядок 1) интерполяцию.

Другой случай (как рекомендовано GriffinHeart ) заключался в использовании сплайнов ( http://en.wikipedia.org/wiki/Spline_interpolation )

В любом случае вы получите некоторую форму полиномиальной подгонки для вашей кривой.

Если точка преобразования предназначена только для хранилища, и когда вы возвращаете ее на экран, вам нужно, чтобы она была гладкой, то хранилище с максимально высокой точностью воспроизведения вы можете получить, при этом минимизируя общий объем хранилища, необходимый для сохранения заданной кривой. на самом деле сохранить атрибуты круга (или, скорее, дуги) и заново нарисовать его по требованию.

Происхождение. Радиус. Начать / остановить углы для рисования дуги.

Если вам все равно нужно преобразовать круг / дугу в точки для рендеринга, вы можете сделать это при загрузке из хранилища, сохраняя при этом только атрибуты.

Есть ли причина идти по кривым, а не по прямым? С прямыми линиями проще работать, и их можно эффективно визуализировать на аппаратном уровне.

Другой подход, который стоит рассмотреть, - хранить пару бит на пиксель, указав, находится ли он внутри, снаружи или на контуре фигуры. Это должно хорошо сжиматься и может быть более эффективным, чем строки для сложных выборов.

Вы также можете найти эти статьи интересными / полезными:

• http://blog.getpaint.net/2008/06/02/whats-coming-in-paintnet-v335/ (нижняя половина)
• 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/

Посмотрите на интерполяцию кривой - есть несколько различных типов, которые вы можете реализовать, которые помогут сгладить вашу кривую. Чем больше очков вы можете получить на этом круге, тем лучше. Хранилище довольно дешево - поэтому, если извлечь 360 близких узлов достаточно дешево (даже при 8 байтах для позиции; 360 узлов вряд ли стоит дорого хранить).

Вы можете разместить с некоторыми интерполяционными выборками здесь только с четырьмя точками; и результаты довольно хорошие (мой фаворит - Безье для этого случая, хотя другие могут вмешаться в другие эффективные решения).

Вы можете поиграть и здесь .