Преобразование 2D-кривой в точки для хранения данных

12

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

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

Для тех, кто знает класс 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();
         }
    }

}

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

сравнение между путями;  заметно более ровные углы на производной

Lumis
источник
почему бы не использовать b-сплайны?
GriffinHeart
4
если вы знаете, что это круг и прямоугольник, почему бы не сохранить круг и прямоугольник? И в обобщенном виде - независимо от того, какой ввод сгенерировал, ваша вещь, вероятно, является разумным форматом для ее хранения. Если вы ищете схему сжатия, которая кажется другим вопросом (или, по крайней мере, нам потребуется гораздо больше информации об исходных данных быть полезным).
Джефф Гейтс
Это может быть любая непредсказуемая форма, как я сказал в первом предложении - круг и прямоугольник здесь - только пример теста.
Лумис
@Lumis, тебе действительно стоит заглянуть в b-сплайны, для чего они нужны. Есть ли причина попробовать реализовать собственное решение?
GriffinHeart
1
Ну, класс путей построит эти кривые со сплайнами, так что вы уже используете его. У меня есть другое предложение, менее ориентированное на математику: вместо сохранения точек сохраните пользовательский ввод (шаблон команды) и воспроизведите его, чтобы создать тот же «образ».
GriffinHeart

Ответы:

6

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

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

Сначала вы начинаете с равных расстояний от 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 .

msell
источник
Это звучит многообещающе. Однако используются не p0, а p1, p2, p3, p0 предназначен только для хранения новых определенных точек при их вычислении и ради прямых линий, чтобы они не отбирались на каждом шаге. Можете ли вы помочь мне, как рассчитать x, y для новых контрольных точек?
Лумис
Я мог бы сделать это позже, но пока проверить stackoverflow.com/questions/2931573/... . С помощью u и v вы можете получить точку пересечения.
msell
Спасибо за помощь, я хотел бы попробовать это, но это должно быть написано на Java для Android. Vector2 и t1, p1 и т. Д. Не являются массивами с плавающей точкой, поэтому я не могу выполнять с ними никаких прямых операций, таких как t1 = -t1 или u * t0. Я предполагаю, что t1 = -t1 означает t1.x = -t1x; t1.y = -t1.y и т. д., верно?
Лумис
Да, это был просто псевдокод, чтобы сделать его более компактным и читабельным.
Msell
Ну, сюжет утолщается. Поскольку пересечение области двух путей в Android возвращает путь, который НЕ является сглаженным, касательные находятся над этим местом. Таким образом, правильным решением было бы сначала провести некоторую плавную кривую через заданные точки, а затем сделать выборку. Ваш код отлично работает на пути сглаживания, он производит правильные контрольные точки.
Лумис
13

Что бы сделал 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 является хорошим примером.

Анко
источник
Вопрос в том, чтобы преобразовать кривую в точки, а не сохранить ее. Но спасибо за эту ссылку, это хорошо знать о стандарте SVG.
Лумис
@Lumis Заголовок и содержание предложили бы иначе. Попробуйте перефразировать вопрос. (Или, теперь, когда это вполне установлено, спрашивая другого.)
Anko
4

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

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

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

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

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

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

amitp
источник
Вы правы, вторая точка только «тянет» кривую к ней. Для cubicTo требуются две контрольные точки вместо одной в качестве quadTo. Проблема, конечно, в том, как получить правильные контрольные точки. Обратите внимание, что я не хочу терять острые углы, так как исходный путь может быть комбинацией любой формы, прямой или круглой - в основном я делаю инструмент выбора изображения, где я могу сохранить выбранный путь.
Лумис
4

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

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

Вот мой код:

    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 (): введите описание изображения здесь

user1344545
источник
Спасибо, кто когда-либо потратил мне 10 репутации, чтобы добавить изображения :-)
user1344545
1
Удивительно, но этот простой трюк решает две проблемы: во-первых, он делает результирующий путь пересечения или объединения гладким, а во-вторых, мой код в вопросе, когда выборка этого же увеличенного пути дает совершенно гладкий результат. Какое неожиданное и простое решение, спасибо!
Лумис
@user Редактирование бесплатно. Для пользователей <2k-rep, на самом деле это +2.
Анко
@Lumis Я немного запутался - я думал, ты спросил, как хранить пути?
Анко
1
К сожалению, после дополнительного тестирования я обнаружил, что, поскольку Region использует пиксели, которые путь будет занимать при прорисовке, приложению легко не хватит памяти, если масштабирование Path велико и выполняется многократно. Таким образом, это решение ограничено и рискованно, но хорошо иметь в виду.
Лумис
3

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

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

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

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

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

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

Yuuta
источник
2

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

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

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

jefflunt
источник
Исходная траектория / кривая может быть любой формы, включая рисунок свободной линии. Я рассматривал это решение, которое должно было бы сохранять каждый компонент отдельно, а затем объединять их при загрузке, но оно требует большого объема работы и замедляло бы манипулирование таким сложным объектом, поскольку каждое преобразование должно было бы применяться к каждому из его компоненты, чтобы иметь возможность сохранить его снова.
Лумис
2

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

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

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

Адам
источник
1

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

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

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

Вон Хилтс
источник