Curve fitting

Sve vezano u matematiku & fiziku koja zaluta u vaš projekt.
Post Reply
User avatar
Denis
Sajentist on djuti!
Posts: 2618
Joined: Tue Aug 26, 2008 9:35 pm
Smallest prime number bigger than 20: 23

Curve fitting

Post by Denis » Sun May 15, 2011 5:59 pm

Imam jedan problemčić koji ne znam kako pametno riješiti. Imam neke točke između kojih moram povući liniju (crtanje mišem, ako se dovoljno brzo giba ne uhvati se većina točaka prijeđenog puta). Znači dobijem ovak šta:
Image
Ova prva linija je brz miš, druga spor.

Sad, kako povezati te točke međusobno da se dobije "glatka" linija. Ako idem preko pravaca, dobit ću previše grube veze (kad miš ide sporo bi još i ok izgledalo, na onoj gore bi izgledalo jadunjavo). Kako onda "povući" te linije? Googleao sam o interpolaciji i curve fittingu, našao na Wikipediji čista matematička objašnjenja (istina, nisam se udubio u proučavanje :oops: ). Ono što sam vidio mi se čini suviše kompleksno za računanje s većim brojem točaka u nekom normalnom vremenu.
Ima netko neki primjer ili može objasniti metodu koja bi radila "dovoljno dobro" (treba čisto izgledati ok, ne treba mi neka velika matematička preciznost) za ovakav slučaj?

User avatar
Burek_fr0m_SPACE
Man from Another Place
Posts: 229
Joined: Tue Aug 26, 2008 2:11 pm
Smallest prime number bigger than 20: 23
Location: Black Lodge
Contact:

Re: Curve fitting

Post by Burek_fr0m_SPACE » Sun May 15, 2011 7:22 pm

Probaj kubičnu interpolaciju. Ako ti odgovara oblik koji se time dobije, kod bi izgledao ovako otprilike :

Code: Select all

double cubicInterpolate (double p[4], double x) {
	return p[1] + 0.5 * x*(p[2] - p[0] + x*(2.0*p[0] - 5.0*p[1] + 4.0*p[2] - p[3] + x*(3.0*(p[1] - p[2]) + p[3] - p[0])));
}
To bi dva puta radio za 2D, po svakoj osi. Tu ti je p array koordinata po jednoj osi, gdje je p[1] - p[2] interval koji hoćeš popuniti, a p[0] i p[3] su tačke prije i poslije njega, a x bi bio broj od 0.0 do 1.0 koji se, jelte, odnosi na poziciju između koju hoćeš da dobiješ.

User avatar
Overseer
Spaaaaaaace!
Spaaaaaaace!
Posts: 593
Joined: Tue Aug 26, 2008 2:02 pm

Re: Curve fitting

Post by Overseer » Sun May 15, 2011 8:37 pm

Slažem se s burekom, malo zaroni i prouči to, izrazito je korisno za ovakav tip problema. Elegantno i jednostavno pri tome!
Don't combine bracket and dot syntax in Objective-C, it's bad practice and quite irritating.
There is no such thing as a better graphics API. They are just different. And hot. And sexy. I should stop now.
Your matrices are belong to us.

User avatar
EmP
Veliki brat malih trokuta
Posts: 498
Joined: Tue Sep 01, 2009 10:14 pm
Smallest prime number bigger than 20: 23
Location: Zagreb
Contact:

Re: Curve fitting

Post by EmP » Sun May 15, 2011 10:11 pm

http://en.wikipedia.org/wiki/B%C3%A9zier_curve

Za početak možeš uzet kvadratnu B krivulju. To ti je najjednostavnije moguće. Iz sveg što piše na wikipediji, kvardatna Bezierova krivulja ti je ovo:
Image
Image

Postaviš si dva susjedna klika kao rubne točke (P0 i P2) i kontrolnu točku (P1) izračunaš kao sjecište pravaca. Ako su ti K1, K2, ..., Kn pozicije klikova, za krivulju između K5 i K6 kontrolnu točku izračunaš kao sjecište pravaca K4K5 i K6K7.

Ima tu malih problema s rubnim slučajevima, al ne da mi se sad crtat.
Nexus 64213 blog - IKON: moja verzija JSONa
Stareater blog - lijepe slike kak napreduje kod

User avatar
Denis
Sajentist on djuti!
Posts: 2618
Joined: Tue Aug 26, 2008 9:35 pm
Smallest prime number bigger than 20: 23

Re: Curve fitting

Post by Denis » Sun May 15, 2011 10:42 pm

Napravio implementaciju s kubičnom interpolacijom, radi solidno dobro. Slika:
Image

Source u C#u za XNA, ako nekoga zanima:
Spoiler! :

Code: Select all

using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;

namespace Drawing
{
    public class Game1 : Microsoft.Xna.Framework.Game
    {
        //stvari koje trebaju XNAu
        GraphicsDeviceManager graphics;
        SpriteBatch spriteBatch;

        Texture2D dot; //dot s kojim prikazujemo pixel

        //bufferi
        List<Vector2> finalPoints;
        List<Vector2> inputBuffer;

        MouseState current; //stanje miša

        int cPRECIZNOST = 100; //koliko točaka ćemo generirati između 2 inputa

        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
            Content.RootDirectory = "Content";
            IsMouseVisible = true;
        }

        protected override void Initialize()
        {
            finalPoints = new List<Vector2>();
            inputBuffer = new List<Vector2>();
            base.Initialize();
        }

        protected override void LoadContent()
        {
            spriteBatch = new SpriteBatch(GraphicsDevice);
            dot = Content.Load<Texture2D>("dot");
        }

        double cubicInterpolate (double[] p, double x) 
        {
            return p[1] + 0.5 * x*(p[2] - p[0] + x*(2.0*p[0] - 5.0*p[1] + 4.0*p[2] - p[3] + x*(3.0*(p[1] - p[2]) + p[3] - p[0])));
        } //credits to Burek_fr0m_SPACE

        protected override void Update(GameTime gameTime)
        {
            current = Mouse.GetState();

            if (current.LeftButton == ButtonState.Pressed)
            {
                //dodajemo prve dvije točke na finalni popis, jer interpolaciju nad novim inputom vršimo
                //na temelju zadnje dvije točke finalnog popisa
                if (finalPoints.Count < 2) finalPoints.Add(new Vector2(current.X, current.Y));
                else if (!inputBuffer.Contains(new Vector2(current.X, current.Y))) inputBuffer.Add(new Vector2(current.X, current.Y));
            }

            if (inputBuffer.Count == 2) //kad skupimo dovoljno novog inputa
            {
                double x, y;
                int endIndex = finalPoints.Count; //gdje je zadnja točka na popisu
                //potrebno, jer se dodavanjem novih točaka Count povećava 
                for (int j = 0; j < cPRECIZNOST; ++j)
                {
                    x = cubicInterpolate(new double[] { finalPoints[endIndex - 2].X, finalPoints[endIndex - 1].X, inputBuffer[0].X, inputBuffer[1].X }, (float)j / cPRECIZNOST);
                    y = cubicInterpolate(new double[] { finalPoints[endIndex - 2].Y, finalPoints[endIndex - 1].Y, inputBuffer[0].Y, inputBuffer[1].Y }, (float)j / cPRECIZNOST);
                    finalPoints.Add(new Vector2((float)x, (float)y));
                }
                inputBuffer.Clear(); //input obrađen, čistimo
            }
    
            base.Update(gameTime);
        }

        protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.CornflowerBlue);

            //iscrtavanje
            spriteBatch.Begin();
            foreach (Vector2 point in finalPoints) spriteBatch.Draw(dot, point, Color.White);
            spriteBatch.End();

            base.Draw(gameTime);
        }
    }
}
Hvala!
EmP wrote:http://en.wikipedia.org/wiki/B%C3%A9zier_curve

Za početak možeš uzet kvadratnu B krivulju. To ti je najjednostavnije moguće. Iz sveg što piše na wikipediji, kvardatna Bezierova krivulja ti je ovo:
Image
Image

Postaviš si dva susjedna klika kao rubne točke (P0 i P2) i kontrolnu točku (P1) izračunaš kao sjecište pravaca. Ako su ti K1, K2, ..., Kn pozicije klikova, za krivulju između K5 i K6 kontrolnu točku izračunaš kao sjecište pravaca K4K5 i K6K7.

Ima tu malih problema s rubnim slučajevima, al ne da mi se sad crtat.
Izgleda zanimljivo, budem sutra isprobao s tim.

Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest