Category Archives: graphics algorithms

Distance Between Point and Line (optimized)

By Zevan | June 4, 2009

Actionscript:

/**
Original function by Pieter Iserbyt:
http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/DistancePoint.java
from Paul Bourke's website:
http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/
*/
function pointToLineDist(x1:Number, y1:Number, x2:Number, y2:Number,x3:Number, y3:Number):Number {
    var dx:Number=x2-x1;
    var dy:Number=y2-y1;
    if (dx==0&&dy==0) {
        x2+=1;
        y2+=1;
        dx=dy=1;
    }
    var u:Number = ((x3 - x1) * dx + (y3 - y1) * dy) / (dx * dx + dy * dy);
 
    var closestX:Number;
    var closestY:Number;
    if (u<0) {
        closestX=x1;
        closestY=y1;
    } else if (u> 1) {
        closestX=x2;
        closestY=y2;
    } else {
        closestX=x1+u*dx;
        closestY=y1+u*dy;
    }
    dx=closestX-x3;
    dy=closestY-y3;
    return Math.sqrt(dx * dx +  dy * dy);
}
 
/**
Test out the function
*/
 
var dotA:Sprite = dot(100, 100);
var dotB:Sprite = dot(200, 200);
var dotC:Sprite = dot(150, 100, 0x0000FF);
var txt:TextField = TextField(dotC.addChild(new TextField()));
with(txt) x = 5, y = 5, autoSize = "left", selectable = false, mouseEnabled = false;
 
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
    graphics.clear();
    graphics.lineStyle(0,0x000000);
    graphics.moveTo(dotA.x, dotA.y);
    graphics.lineTo(dotB.x, dotB.y);
    txt.text = pointToLineDist(dotA.x, dotA.y, dotB.x, dotB.y, dotC.x, dotC.y).toFixed(2);
}
 
// draggable dot
function dot(xp:Number, yp:Number, col:uint = 0xFF0000, rad:Number=4):Sprite {
    var s:Sprite = Sprite(addChild(new Sprite));
    s.x = xp;
    s.y = yp;
    with(s.graphics) beginFill(col), drawCircle(0,0,rad);
    s.buttonMode = true;
    s.addEventListener(MouseEvent.MOUSE_DOWN, onDrag);
    return s;
}
function onDrag(evt:MouseEvent):void { evt.currentTarget.startDrag() }
stage.addEventListener(MouseEvent.MOUSE_UP, onUp);
function onUp(evt:MouseEvent):void{stopDrag() }

This is the same as yesterdays post about the distance between a point and a line segment. I just took a few minutes to optimize the function - it runs close to 3X faster now. For more info see yesterdays post.

Also posted in Math, misc | Tagged actionscript, as3, flash | 1 Comment

Distance Between Point and Line Segment

By Zevan | June 3, 2009

CLICK HERE TO COPY

Actionscript:

/**
Original function by Pieter Iserbyt:
http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/DistancePoint.java
from Paul Bourke's website:
http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/
*/
function pointToLineDistance(p1:Sprite, p2:Sprite, p3:Sprite):Number {
    var xDelta:Number = p2.x - p1.x;
    var yDelta:Number = p2.y - p1.y;
    if ((xDelta == 0) && (yDelta == 0)) {
        // p1 and p2 cannot be the same point
        p2.x += 1;
        p2.y += 1;
        xDelta = 1;
            yDelta = 1;
    }
    var u:Number = ((p3.x - p1.x) * xDelta + (p3.y - p1.y) * yDelta) / (xDelta * xDelta + yDelta * yDelta);
    var closestPoint:Point;
    if (u <0) {
        closestPoint = new Point(p1.x, p1.y);
    } else if (u> 1) {
        closestPoint = new Point(p2.x, p2.y);
    } else {
        closestPoint = new Point(p1.x + u * xDelta, p1.y + u * yDelta);
    }
    return Point.distance(closestPoint, new Point(p3.x, p3.y));
}
 
/**
Test out the function
*/
 
var dotA:Sprite = dot(100, 100);
var dotB:Sprite = dot(200, 200);
var dotC:Sprite = dot(150, 100, 0x0000FF);
var txt:TextField = TextField(dotC.addChild(new TextField()));
with(txt) x = 5, y = 5, autoSize = "left", selectable = false, mouseEnabled = false;
 
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
    graphics.clear();
    graphics.lineStyle(0,0x000000);
    graphics.moveTo(dotA.x, dotA.y);
    graphics.lineTo(dotB.x, dotB.y);
    txt.text = pointToLineDistance(dotA, dotB, dotC).toFixed(2);
}
 
// draggable dot
function dot(xp:Number, yp:Number, col:uint = 0xFF0000, rad:Number=4):Sprite {
    var s:Sprite = Sprite(addChild(new Sprite));
    s.x = xp;
    s.y = yp;
    with(s.graphics) beginFill(col), drawCircle(0,0,rad);
    s.buttonMode = true;
    s.addEventListener(MouseEvent.MOUSE_DOWN, onDrag);
    return s;
}
function onDrag(evt:MouseEvent):void { evt.currentTarget.startDrag() }
stage.addEventListener(MouseEvent.MOUSE_UP, onUp);
function onUp(evt:MouseEvent):void{stopDrag() }

Last night I was working late and found myself in need of a way to calculate the distance between a point and a line. After a quick google search I found myself once again on Paul Bourke's extremely useful website. I was in a rush, so I just quickly ported the java code (by Pieter Iserbyt) and wrote this test snippet to make sure it works.

This code could be optimized a bit, but it works nicely.

I needed this for a commercial project, but as I was porting the code I thought of an interesting way to use this code to draw a gradient - may write and post that tomorrow.

Also posted in Math | Tagged actionscript, as3, flash | 5 Comments

Polygon Triangulation

By Zevan | May 29, 2009

CLICK HERE TO COPY

Actionscript:

var triangulate:Triangulate = new Triangulate();
 
var poly:Array=[];
 
stage.addEventListener(MouseEvent.MOUSE_DOWN, onDown);
function onDown(evt:MouseEvent):void {
    poly.push(new Pnt(mouseX, mouseY));
}
 
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
    var i:int;
    graphics.clear();
    var verts:Array=triangulate.process(poly);
 
    if (verts==null) {
        // draw a red polygon if there is some kind of error,
        // or if there are too few points on the poly
        if (poly.length>1) {
            graphics.lineStyle(0,0xFF0000);
            graphics.moveTo(poly[0].x, poly[0].y);
            for (i = 1; i<poly.length; i++) {
                graphics.lineTo(poly[i].x, poly[i].y);
            }
        }
    }else{
        // draw the triangulated polygon
        var tcount:int = verts.length / 3;
        graphics.lineStyle(0,0x000000);
        for (i = 0; i<tcount; i++) {
            var index:int = i * 3;
            var p1:Pnt=verts[index];
            var p2:Pnt=verts[index+1];
            var p3:Pnt=verts[index+2];
            graphics.moveTo(p1.x,p1.y);
            graphics.lineTo(p2.x,p2.y);
            graphics.lineTo(p3.x,p3.y);
            graphics.lineTo(p1.x,p1.y);
        }
    }
}

The above demo's a class that triangulates a polygon given a list of points. To test this snippet you'll need the Pnt and Triangulate Classes, which you can download or copy from below.

Polygon triangulation is useful for lots of things... I first found that I needed it back in my Director days. I wanted to be able to draw a polygon and then extrude it into 3D space - in order to do this I needed to triangulate the polygon that was drawn. Luckily there was an undocumented feature in Lingo that did the triangulation. I'll probably do an extrusion demo soon. I've been looking into this to make the QuickBox2D polygon stuff a little easier.

Take a look at the swf here

Download all source and fla here....

Here is the Triangulate class:

CLICK HERE TO COPY

Actionscript:

/**
This code is a quick port of code written in C++ which was submitted to 
flipcode.com by John W. Ratcliff  // July 22, 2000 
See original code and more information here:
http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
 
ported to actionscript by Zevan Rosser
www.actionsnippet.com
*/
 
package {
    
    public class Triangulate {
        
        private const EPSILON:Number = 0.0000000001;
        
        public function Triangulate(){}
        
        public function process(contour:Array):Array{
            var result:Array = [];
            var n:int = contour.length
            if ( n <3 ) return null
            
            var verts:Array = [];
            
              /* we want a counter-clockwise polygon in verts */
            var v:int
            
              if ( 0.0 <area(contour) ){
                for (v=0; v<n; v++) verts[v] = v;
              }else{
                for(v=0; v<n; v++) verts[v] = (n-1)-v;
              }
            
              var nv:int = n;
            
              /*  remove nv-2 vertsertices, creating 1 triangle every time */
              var count:int = 2*nv;   /* error detection */
             var m:int;
              for(m=0, v=nv-1; nv>2; )
              {
                /* if we loop, it is probably a non-simple polygon */
                if (0>= (count--)){
                  //** Triangulate: ERROR - probable bad polygon!
                 // trace("bad poly");
                  return null;
                }
            
                /* three consecutive vertices in current polygon, <u,v,w> */
                var u:int = v; if (nv <= u) u = 0;     /* previous */
                v = u+1; if (nv <= v) v = 0;     /* new v    */
                var w:int = v+1; if (nv <= w) w = 0;     /* next     */
            
                if ( snip(contour,u,v,w,nv,verts)){
                  var a:int,b:int,c:int,s:int,t:int;
            
                  /* true names of the vertices */
                  a = verts[u]; b = verts[v]; c = verts[w];
            
                  /* output Triangle */
                  result.push( contour[a] );
                  result.push( contour[b] );
                  result.push( contour[c] );
            
                  m++;
            
                  /* remove v from remaining polygon */
                  for(s=v,t=v+1;t<nv;s++,t++) verts[s] = verts[t]; nv--;
            
                  /* resest error detection counter */
                  count = 2 * nv;
                }
              }
            
              return result;
        }
        
        // calculate area of the contour polygon
        public function area(contour:Array):Number{
            var n:int = contour.length;
            var a:Number  = 0.0;
            
            for(var p:int=n-1, q:int=0; q<n; p=q++){
                a += contour[p].x * contour[q].y - contour[q].x * contour[p].y;
            }
            return a * 0.5;
        }
        
        // see if p is inside triangle abc
        public function insideTriangle(ax:Number, ay:Number, bx:Number, by:Number, cx:Number, cy:Number,px:Number,py:Number):Boolean{
                                                           
              var aX:Number, aY:Number, bX:Number, bY:Number
              var cX:Number, cY:Number, apx:Number, apy:Number;
              var bpx:Number, bpy:Number, cpx:Number, cpy:Number;
              var cCROSSap:Number, bCROSScp:Number, aCROSSbp:Number;
            
              aX = cx - bx;  aY = cy - by;
              bX = ax - cx;  bY = ay - cy;
              cX = bx - ax;  cY = by - ay;
              apx= px  -ax;  apy= py - ay;
              bpx= px - bx;  bpy= py - by;
              cpx= px - cx;  cpy= py - cy;
            
              aCROSSbp = aX*bpy - aY*bpx;
              cCROSSap = cX*apy - cY*apx;
              bCROSScp = bX*cpy - bY*cpx;
            
              return ((aCROSSbp>= 0.0) && (bCROSScp>= 0.0) && (cCROSSap>= 0.0));
        }
        
        private function snip(contour:Array, u:int, v:int, w:int, n:int, verts:Array):Boolean{
              var p:int;
              var ax:Number, ay:Number, bx:Number, by:Number;
              var cx:Number, cy:Number, px:Number, py:Number;
            
                  ax = contour[verts[u]].x;
                  ay = contour[verts[u]].y;
                
                  bx = contour[verts[v]].x;
                  by = contour[verts[v]].y;
                
                  cx = contour[verts[w]].x;
                  cy = contour[verts[w]].y;
            
          if ( EPSILON> (((bx-ax)*(cy-ay)) - ((by-ay)*(cx-ax))) ) return false;
            
              for (p=0;p<n;p++){
                    if( (p == u) || (p == v) || (p == w) ) continue;
                    px = contour[verts[p]].x
                    py = contour[verts[p]].y
                    if (insideTriangle(ax,ay,bx,by,cx,cy,px,py)) return false;
              }
              return true;
        }
    }
}

... and the Pnt class:

CLICK HERE TO COPY

Actionscript:

// Point class, no reason to use AS3's build in Point
package{
    public class Pnt {
        public var x:Number;
        public var y:Number;
        public function Pnt(x:Number, y:Number){
            this.x = x;
            this.y = y;
        }
    }
}

I also found a nice description of the basic technique being employed here.

UPDATE:
This should be obvious, but I was targeting fp9 with this... thus the use of Array instead of Vector.

Also posted in 3D, Math, misc | Tagged actionscript, flash | 6 Comments

sine cosine Gradient

By Zevan | May 25, 2009

CLICK HERE TO COPY

Actionscript:

[SWF(width=600,height=500,frameRate=30)]
var canvas:BitmapData=new BitmapData(600,500,false,0x000000);
addChild(new Bitmap(canvas));
var size:Number=canvas.width*canvas.height;
var w:Number=canvas.width;
var wd:Number=1/w;
var pix:Vector.<uint> = new Vector.<uint>();
var sin:Number;
var cos:Number;
var dx:Number=110;
var dy:Number=52;
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
    dx+=0.001;
    canvas.lock();
    for (var i:int = 0; i<size; i++) {
        var xp:Number=i%w;
        var yp:Number=int(i*wd);
        var xx:Number=xp*0.05+dx;
        var yy:Number=yp*0.05+dy;
        var t:Number= (xx * yy) % 3.14159265;
        //compute sine
        // technique from http://lab.polygonal.de/2007/07/18/fast-and-accurate-sinecosine-approximation/
        // by Michael Baczynski
        if (t<0) {
            sin=1.27323954*t+.405284735*t*t;
        } else {
            sin=1.27323954*t-0.405284735*t*t;
        }
        //compute cosine: sin(t + PI/2) = cos(t)
        t+=1.57079632;
        if (t>3.14159265) {
            t-=6.28318531;
        }
        if (t<0) {
            cos=1.27323954*t+0.405284735*t*t;
        } else {
            cos=1.27323954*t-0.405284735*t*t;
        }
        var c:Number=sin+cos*cos*cos;
        // fast math abs
        c=c<0? -c:c;
        c=c*140;
        // math max 255
        c=c>255?255:c;
        pix[i]=c<<16|c<<8|c;
    }
    canvas.setVector(canvas.rect, pix);
    canvas.unlock();
}

The above snippet will animate a gradient that looks like this:

Also posted in BitmapData, Vector, pixel manipulation | 3 Comments

Category Archives: graphics algorithms

Distance Between Point and Line (optimized)

Distance Between Point and Line Segment

Polygon Triangulation

sine cosine Gradient

Search

Pages

Recent Posts

Categories

Archives

RSS Feeds