By Zevan | March 13, 2009
Actionscript:
-
// completely unoptimized line to line intersection test:
-
// from wikipedia: http://en.wikipedia.org/wiki/Line-line_intersection
-
function intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point {
-
var nx:Number, ny:Number, dn:Number;
-
nx = (p1.x * p2.y - p1.y * p2.x) * (p3.x - p4.x) - (p1.x - p2.x) * (p3.x * p4.y - p3.y * p4.x);
-
dn = (p1.x - p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x - p4.x);
-
ny = (p1.x * p2.y - p1.y * p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x * p4.y - p3.y * p4.x);
-
return new Point(nx / dn, ny / dn);
-
}
-
-
//
-
// test out the function:
-
//
-
-
stage.frameRate = 30;
-
var a:Sprite = dot();
-
a.x = a.y = 100;
-
-
var b:Sprite = dot();
-
b.x = b.y = 200;
-
-
var c:Sprite = dot();
-
c.x = 200
-
c.y = 100;
-
-
var d:Sprite = dot();
-
d.x = 100
-
d.y = 200;
-
-
var inter:Sprite = dot(0xFF0000,true);
-
-
addEventListener(Event.ENTER_FRAME, onLoop);
-
function onLoop(evt:Event):void {
-
var p:Point = intersection(a, b, c, d);
-
inter.x = p.x;
-
inter.y = p.y
-
-
with(graphics){
-
clear();
-
lineStyle(0,0x000000);
-
moveTo(a.x, a.y);
-
lineTo(b.x, b.y);
-
moveTo(c.x, c.y);
-
lineTo(d.x,d.y);
-
}
-
}
-
-
// draggable dot
-
function dot(col:uint = 0x507399, noDrag:Boolean = false):Sprite {
-
var s:Sprite = Sprite(addChild(new Sprite));
-
with(s.graphics) beginFill(col), drawCircle(0,0,5);
-
if (!noDrag){
-
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 snippet shows the first step toward a usable line to line intersection test. While this demo is fully functional, there is some room for optimization within the intersection() function itself...
From Equations to Code
When I go directly from an equation to code I like to try to make the code resemble the equation... test to make sure it works and then add optimizations. I do this to keep things clear for myself and also so that I have a step by step process to show my students.
The optimizations and additional features that I'll add to this function tomorrow will make it look very different from the original equation from wikipedia. Some things that I'll do:
1) tweak the equation to use fewer operators (it has 12 multiplications right now)
2) wrap duplicate mathmatical operations in variables
3) add the ability to test for line segments rather than infinite lines
4) move any object instantiation outside the function
etc...
Posted in Math, misc | Tagged actionscript, flash |
By Zevan | March 12, 2009
Actionscript:
-
var canvas:BitmapData = Bitmap(addChild(new Bitmap(new BitmapData(400, 400, false, 0x000000)))).bitmapData;
-
-
function line(x1:Number, y1:Number, x2:Number, y2:Number, res:int=10):void{
-
var dx:Number = x2 - x1;
-
var dy:Number = y2 - y1;
-
var dist:Number = Math.sqrt((dx * dx) + (dy * dy));
-
var step:Number = 1 / (dist / res);
-
for (var i:Number = 0; i<=1; i+= step){
-
// lerp : a + (b - a) * f
-
canvas.setPixel(x1 + dx * i, y1 + dy * i, 0xFFFFFF);
-
}
-
}
-
-
addEventListener(Event.ENTER_FRAME, onLoop);
-
function onLoop(evt:Event):void {
-
canvas.fillRect(canvas.rect, 0x000000);
-
line(100 , 100, mouseX, mouseY,1);
-
line(100 + 50, 100, mouseX+ 50, mouseY,5);
-
}
Yesterday I posted an implementation of the Bresenham Line Algorithm. Today I'm posting a comparatively slow way to draw a line with setPixel(). This snippet uses lerp and the Pythagorean theorem. It works nicely for small numbers of lines, its easy to draw dotted lines with it and its easy to explain. In a real app where you needed to use setPixel() to draw a line you should use one of the fast algorithms like Wu or Bresenham.
I didn't originally write this snippet to use set pixel... a few weeks ago I wrote something very similar to calculate a set of x y coords between two given points. In the program I used it in speed wasn't an issue (as I only needed to run the function one time). I've needed this kind of function many times before in games and small apps...
This was the original:
Actionscript:
-
function calculatePoints(x1:Number, y1:Number, x2:Number, y2:Number, res:int=10):Array{
-
var points:Array = new Array();
-
var dx:Number = x2 - x1;
-
var dy:Number = y2 - y1;
-
var dist:Number = Math.sqrt((dx * dx) + (dy * dy));
-
var step:Number = 1 / (dist / res);
-
for (var i:Number = 0; i<=1; i+= step){
-
points.push(new Point(x1 + dx * i, y1 + dy * i));
-
}
-
return points;
-
}
-
-
trace(calculatePoints(0,0,100,0,10));
-
/* outputs:
-
(x=0, y=0),(x=10, y=0),(x=20, y=0),(x=30.000000000000004, y=0),(x=40, y=0),(x=50, y=0),(x=60, y=0),(x=70, y=0),(x=80, y=0),(x=89.99999999999999, y=0),(x=99.99999999999999, y=0)
-
*/
...and another version to allow you to specify the number of points to calculate rather than the pixel interval at which they should be calculated:
Actionscript:
-
function calculatePoints(x1:Number, y1:Number, x2:Number, y2:Number, pointNum:int=10):Array{
-
var points:Array = new Array();
-
var step:Number = 1 / (pointNum + 1);
-
for (var i:Number = 0; i<=1; i+= step){
-
points.push(new Point(x1 + (x2 - x1) * i, y1 + (y2 - y1) * i));
-
}
-
return points;
-
}
-
-
trace(calculatePoints(0,30,30,0,1));
-
/* outputs:
-
(x=0, y=30),(x=15, y=15),(x=30, y=0)
-
*/
This last version isn't perfect, sometimes the pointNum will be off by 1, I may fix that in a future post.
By Zevan | March 11, 2009
Actionscript:
-
var canvas:BitmapData = Bitmap(addChild(new Bitmap(new BitmapData(400,400, false, 0x000000)))).bitmapData;
-
-
drawLine(10,10,100,90, 0xFF0000);
-
drawLine(100,90,60,80, 0xFF0000);
-
drawLine(100,90,95,60, 0xFF0000);
-
-
for (var i:int = 0; i<100; i+=1){
-
drawLine(i *4, 100 + i, 200, 390);
-
}
-
// code ported from here:
-
// http://www.edepot.com/linebenchmark.html
-
function drawLine(x1:int, y1:int, x2:int, y2:int, col:uint = 0xFFFFFF){
-
var x:int, y:int;
-
var dx:int, dy:int;
-
var incx:int , incy:int
-
var balance:int;
-
-
if (x2>= x1){
-
dx = x2 - x1;
-
incx = 1;
-
}else{
-
dx = x1 - x2;
-
incx = -1;
-
}
-
-
if (y2>= y1){
-
dy = y2 - y1;
-
incy = 1;
-
}else{
-
dy = y1 - y2;
-
incy = -1;
-
}
-
-
x = x1;
-
y = y1;
-
-
if (dx>= dy){
-
dy <<= 1;
-
balance = dy - dx;
-
dx <<= 1;
-
-
while (x != x2){
-
canvas.setPixel(x, y, col);
-
if (balance>= 0){
-
y += incy;
-
balance -= dx;
-
}
-
balance += dy;
-
x += incx;
-
}
-
canvas.setPixel(x, y, col);
-
}else{
-
dx <<= 1;
-
balance = dx - dy;
-
dy <<= 1;
-
-
while (y != y2){
-
canvas.setPixel(x, y, col);
-
if (balance>= 0){
-
x += incx;
-
balance -= dy;
-
}
-
balance += dx;
-
y += incy;
-
}
-
canvas.setPixel(x, y, col);
-
}
-
}
This snippet shows Brensenham's line drawing algorithm. I ported this implementation from here... all the line algorithms in that link are easy to port to actionscript. I've messed with them all at some point.
Tomorrow I'm going to post a super slow line drawing algorithm... so I figured I'd post a fast line drawing algorithm today.
By Zevan | March 10, 2009
Actionscript:
-
var harmonic:Number = 0;
-
var k:Number = 1;
-
addEventListener(Event.ENTER_FRAME, onLoop);
-
function onLoop(evt:Event):void {
-
harmonic += 1 / k;
-
trace("+");
-
trace("1 / " + k + " = " + harmonic);
-
k+=1;
-
}
Read more about the harmonic series at wikipedia.
1 / 1 = 1
+
1 / 2 = 1.5
+
1 / 3 = 1.8333333333333333
+
1 / 4 = 2.083333333333333
+
...
Posted in Math | Tagged actionscript, flash, Math |