As3 Function for extrapolating points on a spline

Question

I was hoping someone could help me working out some advanced data reformatting. What I'm hoping for is a function where I can input a value along with an array of key positions like so:

function remap(percentage:Number, keypoints:Array) { ...

The array would start with the minimum and end with the maximum point, with nested key points along the way. For example, I would input something like remap(0.25, [0:0,80:50,100:100] ) and the function would 'imagine' a spline curve graph from (0,0)-(100,100) with a key point of (80,50), then return the y value that is 25% along that graph.

Hopefully that's clear... Any ideas?

Answer 1

The equation for the Hermite Curve is this:

(via Wikipedia)

Where p(t) is the point on the curve at t (percent 0.0 to 1.0)

1. p0 is the first control point
2. m0 is the first anchor point
3. p1 is the second control point
4. m1 is the scond control point

So, the equation in actionscript would be something like this:

        /*
         * Computes x,y values for a given traversal of a Hermite Curve
         * @param t:Number - a normalized value (0.0 to 1.0) describing path traversal
         * @param points:Array - an array contining the 4 points describing the curve (P0,T0,P1,T1 - always in this order)
         * Anchor points are relative to they're control points
         */
        private function hermite(t:Number,points:Array):Point{
            var result:Point = new Point();
            result.x = (2 * Math.pow(t,3) - 3 * t * t + 1) * points[0].x+
                        (Math.pow(t,3) - 2 * t * t + t) * points[1].x + 
                        (- 2 * Math.pow(t,3) + 3*t*t) * points[2].x +
                        ( Math.pow(t,3) - t*t) * points[3].x;
            result.y = (2 * Math.pow(t,3) - 3 * t * t + 1) * points[0].y+
                        (Math.pow(t,3) - 2 * t * t + t) * points[1].y + 
                        (- 2 * Math.pow(t,3) + 3*t*t) * points[2].y +
                        ( Math.pow(t,3) - t*t) * points[3].y;
            return result;
        }

You can see a basic demo here

Still, I am a bit concerned because you're example mentions 3 points (2 control points and one anchor point).

Cubic Curves(Hermite/Catmull-Rom/etc.) have 2 control points and 2 anchor points (equations at power of 3 - cubic)

If you only need one control point, you need to use a Quadratic Curve:

(Image from Adobe Actionscript 3 Documentation)

Cubic Curve:

Quadratic Curve:

(Animations from Wikipedia)

The Quadratic Equation is this:

Which would translate to:

private function quad(t:Number,p:Array):Point{
            var result:Point = new Point();
            var oneMinusTSq:Number = (1-t) * (1-t);
            var TSq:Number = t*t;
            result.x = oneMinusTSq*p[0].x+2*(1-t)*t*p[1].x+TSq*p[2].x;
            result.y = oneMinusTSq*p[0].y+2*(1-t)*t*p[1].y+TSq*p[2].y;
            return result;
        }

And a bit of test code:

package {
    import flash.display.Sprite;
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.geom.Point;

    /**
     * @author george
     */
    public class BasicQuad extends Sprite {
        private var p0:Point = new Point(0,0);
        private var p1:Point = new Point(80,50);
        private var p2:Point = new Point(100,100);
        private var pts:Array = [p0,p1,p2];
        private var t:Number = 0;
        private var pt : Point;

        public function BasicQuad() {
            init();
        }
        private function init():void{
            stage.doubleClickEnabled = true;
            stage.addEventListener(MouseEvent.DOUBLE_CLICK, reset);
            reset();
        }
        private function reset(event : MouseEvent = null) : void {
            graphics.clear();
            graphics.lineStyle(3,0x009900,.5);
            t = 0;
            this.addEventListener(Event.ENTER_FRAME, draw);
        }
        private function draw(event : Event) : void {
            trace(t,pt);
            pt = quad(t, pts);
            if(t == 0) graphics.moveTo(pt.x,pt.y);//draw
            graphics.lineTo(pt.x,pt.y);
            t+= 0.015;
            if(t >= 1) removeEventListener(Event.ENTER_FRAME, draw);//done
        }
        private function quad(t:Number,p:Array):Point{
            var result:Point = new Point();
            var oneMinusTSq:Number = (1-t) * (1-t);
            var TSq:Number = t*t;
            result.x = oneMinusTSq*p[0].x+2*(1-t)*t*p[1].x+TSq*p[2].x;
            result.y = oneMinusTSq*p[0].y+2*(1-t)*t*p[1].y+TSq*p[2].y;
            return result;
        }
    }
}

Also, am not clear what you mean by

advanced data reformatting

The code snippets are the formulas written as code, but there are other ways to compute this.

A quadratic Bézier curve is the path traced by the function B(t), given points P0, P1, and P2,

We need to go from P0 to P1 and from P1 to P2. Since you're looking for a Flash/ActionScript solution, we can take advantage of the Point's interpolate() method. So we interpolate between P0 and P1 to get let's say P01 then from P1 to P2 to get P12 and the interpolation through all 3 points will be the interpolation between P01 and P12:

function quadLerp(t:Number,p:Array):Point {
            var p1:Point = Point.interpolate(p[1], p[0], t);
            var p2:Point = Point.interpolate(p[2], p[1], t);
            return Point.interpolate(p2, p1, t);
        }

The code looks a bit backwards from what I wrote above because of how the actionscript interpolation is implemented: "The level of interpolation between the two points. Indicates where the new point will be, along the line between pt1 and pt2. If f=1, pt1 is returned; if f=0, pt2 is returned."

UPDATE

Further confused:

In reference to your question: my example actually mentions 3 control points and 0 anchor points

are you trying to simply get the y value of the current x along a series of lines (multiple points, 0 anchor points...straight lines) ?

Remember I dont need the graph itself - I just need a point on it Simply walk on a straight line graph/jagged line(no curves whatsoever) ?

If, so, you can do something like this:

1. Loop through all the points of your path and find the line for the current x value (this will be the line for which the start x position is smaller than the given x and the end x position of the line is larger than the given x position)
2. Calculate the ratio between the x distance from the start of the line to the given x and the whole line (end.x-start.x)
3. Use this ratio to divide the current line 'height' (difference between end.y and start.y) and offset it by the start.y, taking advantage of similar triangles, according to Thales' Theorem

Here's a quick sketch to illustrate the idea: Imagine a right angled triangle where the current line is the hypothenuse(ABC). Now imagine a vertical line from your mouse cursor splitting that triangle into two similar triangle(OO'). The small triangle has the same angles as the large one and it's sides are proportional. You use the ratio between AO and AB to divide AC by and obtain the length of OO' (the y position on the line for that x).

Here's the function:

private function getYforX(x:Number,pts:Vector.<Point>):Number{
            var numPts:int = pts.length;
            for (var i : int = 1; i < numPts; i++) {
                if(x > pts[i-1].x && x < pts[i].x) {//find the line on which the cursor lies
                    t = (x-pts[i-1].x)/(pts[i].x-pts[i-1].x);//ratio between the x distance from the start of the line to mouseX and the whole line (end.x-start.x)
                    return pts[i-1].y + ((pts[i].y-pts[i-1].y) * t);//Thales similar triangles version, cheaper version of Point.interpolate(pts[i], pts[i-1], t).y; 
                }
            }
            return -1;
        }

And a quick demo:

package {
    import flash.events.*;
    import flash.display.*;
    import flash.geom.Point;

    public class LerpPoints extends Sprite {

        private var path:Shape = new Shape();
        private var cursor:Shape = new Shape();
        private var numPts:int = 11;
        private var pts:Vector.<Point> = new Vector.<Point>(numPts,true);
        private var t:Number = 0;

        public function LerpPoints() {
            init();
        }
        private function init():void{
            cursor.graphics.lineStyle(10,0x009900);
            cursor.graphics.drawCircle(-3, -3, 3);
            cursor.graphics.lineStyle(1,0x000099);
            cursor.graphics.moveTo(0, -stage.stageHeight);
            cursor.graphics.lineTo(0, stage.stageHeight);
            reset();
            addChild(path);addChild(cursor);
            addEventListener(Event.ENTER_FRAME, update);
            stage.addEventListener(MouseEvent.MOUSE_DOWN, reset);
        }
        private function reset(event:Event = null):void{
            path.graphics.clear();
            for (var i : int = 0; i < numPts; i++) {
                pts[i] = new Point(i*55,Math.random() * 200);//generate points
                path.graphics.lineStyle(3,0);
                if(i == 0) path.graphics.moveTo(pts[0].x,pts[0].y);//draw path
                path.graphics.lineTo(pts[i].x,pts[i].y);
                if(i > 0){//right angled triangles
                    path.graphics.lineStyle(1,0x990000);
                    path.graphics.lineTo(pts[i-1].x,pts[i].y);
                    path.graphics.lineTo(pts[i-1].x,pts[i-1].y);
                    path.graphics.moveTo(pts[i].x,pts[i].y);
                }
            }
        }
        private function update(event:Event):void{
            cursor.x = mouseX;
            cursor.y = getYforX(mouseX, pts);
        }
        private function getYforX(x:Number,pts:Vector.<Point>):Number{
            var numPts:int = pts.length;
            for (var i : int = 1; i < numPts; i++) {
                if(x > pts[i-1].x && x < pts[i].x) {//find the line on which the cursor lies
                    t = (x-pts[i-1].x)/(pts[i].x-pts[i-1].x);//ratio between the x distance from the start of the line to mouseX and the whole line (end.x-start.x)
                    return pts[i-1].y + ((pts[i].y-pts[i-1].y) * t);//Thales similar triangles version, cheaper version of Point.interpolate(pts[i], pts[i-1], t).y; 
                }
            }
            return -1;
        }
    }
}

Note that this works if the x values in your points array are in sorted ascending (e.g. your path goes only left to right)

A dirty hack that comes mind is to loop through the pairs of points and store Y values in a lookup table. The number of loops woud be the 'line detail'

Then again, this confuses me:

just need to to asses an array of points (not just 2) and ideally spline curve them rather than simply joining the dots So you have multiple points, but where does the spline come in, since you mentioned 0 anchor points ?

HTH