Category Archives: misc

Line Intersection Part 1 (unoptimized)

By Zevan | March 13, 2009
CLICK HERE TO COPY
Actionscript:
  1. // completely unoptimized line to line intersection test:
  2. // from wikipedia: http://en.wikipedia.org/wiki/Line-line_intersection
  3. function intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point {
  4.     var nx:Number, ny:Number, dn:Number;
  5.     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);
  6.     dn = (p1.x - p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x - p4.x);
  7.     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);
  8.     return new Point(nx / dn, ny / dn);
  9. }
  10.  
  11. //
  12. // test out the function:
  13. //
  14.  
  15. stage.frameRate = 30;
  16. var a:Sprite = dot();
  17. a.x = a.y = 100;
  18.  
  19. var b:Sprite = dot();
  20. b.x = b.y = 200;
  21.  
  22. var c:Sprite = dot();
  23. c.x = 200
  24. c.y = 100;
  25.  
  26. var d:Sprite = dot();
  27. d.x = 100
  28. d.y = 200;
  29.  
  30. var inter:Sprite = dot(0xFF0000,true);
  31.  
  32. addEventListener(Event.ENTER_FRAME, onLoop);
  33. function onLoop(evt:Event):void {
  34.     var p:Point = intersection(a, b, c, d);
  35.     inter.x = p.x;
  36.     inter.y = p.y
  37.    
  38.     with(graphics){
  39.         clear();
  40.         lineStyle(0,0x000000);
  41.         moveTo(a.x, a.y);
  42.         lineTo(b.x, b.y);
  43.         moveTo(c.x, c.y);
  44.         lineTo(d.x,d.y);
  45.     }
  46. }
  47.  
  48. // draggable dot
  49. function dot(col:uint = 0x507399, noDrag:Boolean = false):Sprite {
  50.     var s:Sprite = Sprite(addChild(new Sprite));
  51.     with(s.graphics) beginFill(col), drawCircle(0,0,5);
  52.     if (!noDrag){
  53.         s.buttonMode = true;
  54.        s.addEventListener(MouseEvent.MOUSE_DOWN, onDrag);
  55.     }
  56.     return s;
  57. }
  58. function onDrag(evt:MouseEvent):void {
  59.     evt.currentTarget.startDrag()
  60. }
  61.  
  62. stage.addEventListener(MouseEvent.MOUSE_UP, onUp);
  63. function onUp(evt:MouseEvent):void{
  64.     stopDrag();
  65. }

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...

Also posted in Math | Tagged , | Leave a comment

Slow Line Drawing

By Zevan | March 12, 2009
CLICK HERE TO COPY
Actionscript:
  1. var canvas:BitmapData = Bitmap(addChild(new Bitmap(new BitmapData(400, 400, false, 0x000000)))).bitmapData;
  2.  
  3. function line(x1:Number, y1:Number, x2:Number, y2:Number, res:int=10):void{
  4.     var dx:Number = x2 - x1;
  5.     var dy:Number = y2 - y1;
  6.     var dist:Number = Math.sqrt((dx * dx) + (dy * dy));
  7.     var step:Number = 1 / (dist / res);
  8.     for (var i:Number = 0; i<=1; i+= step){
  9.         // lerp : a  + (b - a) * f
  10.         canvas.setPixel(x1 + dx * i, y1 + dy * i, 0xFFFFFF);
  11.     }
  12. }
  13.  
  14. addEventListener(Event.ENTER_FRAME, onLoop);
  15. function onLoop(evt:Event):void {
  16.    canvas.fillRect(canvas.rect, 0x000000);
  17.   line(100 , 100, mouseX, mouseY,1);
  18.   line(100 + 50, 100, mouseX+ 50, mouseY,5);
  19. }

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:

CLICK HERE TO COPY
Actionscript:
  1. function calculatePoints(x1:Number, y1:Number, x2:Number, y2:Number, res:int=10):Array{
  2.     var points:Array = new Array();
  3.     var dx:Number = x2 - x1;
  4.     var dy:Number = y2 - y1;
  5.     var dist:Number = Math.sqrt((dx * dx) + (dy * dy));
  6.     var step:Number = 1 / (dist / res);
  7.     for (var i:Number = 0; i<=1; i+= step){
  8.         points.push(new Point(x1 + dx * i, y1 + dy * i));
  9.     }
  10.     return points;
  11. }
  12.  
  13. trace(calculatePoints(0,0,100,0,10));
  14. /* outputs:
  15. (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)
  16. */

...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:

CLICK HERE TO COPY
Actionscript:
  1. function calculatePoints(x1:Number, y1:Number, x2:Number, y2:Number, pointNum:int=10):Array{
  2.     var points:Array = new Array();
  3.     var step:Number = 1 / (pointNum + 1);
  4.     for (var i:Number = 0; i<=1; i+= step){
  5.         points.push(new Point(x1 + (x2 - x1) * i, y1 + (y2 - y1) * i));
  6.     }
  7.     return points;
  8. }
  9.  
  10. trace(calculatePoints(0,30,30,0,1));
  11. /* outputs:
  12. (x=0, y=30),(x=15, y=15),(x=30, y=0)
  13. */

This last version isn't perfect, sometimes the pointNum will be off by 1, I may fix that in a future post.

Also posted in Math, graphics algorithms, pixel manipulation, setPixel | Tagged , | Leave a comment

Random Sort

By Zevan | February 27, 2009
CLICK HERE TO COPY
Actionscript:
  1. function randomize(a:*, b:*):int{
  2.        return Math.round(Math.random()*8) - 4;
  3. }
  4.  
  5. var i:int;
  6. var fruits:Array;
  7.  
  8. trace("Math.random()");
  9. for (i = 0; i<4; i++){
  10.   // reset fruits array:
  11.   fruits = ["apple", "grape","pear","cherry"];
  12.   fruits.sort(randomize);
  13.   trace(fruits);
  14. }
  15.  
  16.  
  17. // seeds
  18. var s1:Number= 0xFF00FF;
  19. var s2:Number = 0xCCCCCC;
  20. var s3:Number= 0xFF00F0;
  21.  
  22. function tRandomize(a:*, b:*):int{
  23.        return Math.round(rand()*8) - 4;
  24. }
  25.  
  26. trace("\nTausworthe rand()");
  27. for (i= 0; i<4; i++){
  28.   fruits = ["apple", "grape","pear","cherry"];
  29.   fruits.sort(tRandomize);
  30.   trace(fruits);
  31. }
  32. // from www.ams.org/mcom/1996-65-213/S0025-5718-96-00696-5/S0025-5718-96-00696-5.pdf
  33. function rand():Number {
  34.     s1=((s1&4294967294)<<12)^(((s1<<13)^s1)>>19);
  35.     s2=((s2&4294967288)<<4)^(((s2<<2)^s2)>>25);
  36.     s3=((s3&4294967280)<<17)^(((s3<<3)^s3)>>11);
  37.     var r:Number = (s1^s2^s3) * 2.3283064365e-10;
  38.     r = (r<0) ? r+=1 : r;
  39.     return r;
  40. }
  41.  
  42. /*
  43. outputs:
  44. Math.random()
  45. grape,apple,pear,cherry
  46. pear,cherry,apple,grape
  47. grape,apple,pear,cherry
  48. grape,apple,cherry,pear
  49.  
  50. Tausworthe rand()
  51. apple,grape,pear,cherry
  52. cherry,grape,pear,apple
  53. grape,apple,cherry,pear
  54. grape,pear,apple,cherry
  55. */

The above shows how to randomly sort or shuffle an array. This is useful in games. To achieve this I made use of the compareFunction argument of Array.sort(). Most sorting algorithms go through the array and compare values until the desired sort order is achieved. The compareFunction argument is a function that takes two values a and b and returns an integer that is negative positive or zero... see this info from the docs:
* A negative return value specifies that A appears before B in the sorted sequence.
* A return value of 0 specifies that A and B have the same sort order.
* A positive return value specifies that A appears after B in the sorted sequence.

So in the case of a randomizing an array you simply need to return a random int -1, 0 or 1. This is what I've done in the past (Math.round()*2) -1) ... but when I was writing this snippet it seemed like 0 caused less variation in the output of the array so I made the range from -4 to 4 instead. This could have just been my imagination, but it seems like having less chance of a zero caused the arrays to be a bit more shuffled.

The reason I also included a version that uses Tausworthe is because of the easy seeding. In some cases you may want to use seeded randomness to sort an array.

UPDATE:
Was digging around about this and found a much faster method for randomizing arrays... not a big deal if you have small arrays, but if you need to randomize 1000's of values this method is much faster than using Array.sort()

Also posted in arrays | Tagged , | Leave a comment

N to the power of N (with strings)

By Zevan | February 24, 2009
CLICK HERE TO COPY
Actionscript:
  1. var input:String =  "a, b, c";
  2.  
  3. var words:Array = input.split(", ");
  4. var max:String = "";
  5. var maxD:String =  (words.length - 1).toString();
  6. for (var i:int = 0; i<words.length; i++){
  7.     max += maxD;
  8. }
  9. var maxInt:int = parseInt(max,words.length);
  10.  
  11. for(i = 0; i<=maxInt; i++){
  12.      var indices:String = i.toString(words.length);
  13.      var r:String = "";
  14.      var k:int=0;
  15.      for (var j:int = 0; j<indices.length; j++){
  16.          r += words[parseInt(indices.charAt(j))] +" ";
  17.          k++;
  18.      }
  19.      while(k <words.length) {
  20.         r = words[0] +" "+ r;
  21.         k++;
  22.      }
  23.     trace(r);
  24. }
  25. trace(i, " variations");

Like many things on this site, I coded this rather quickly and it can probably be cleaned up...

Setting the input variable of the above snippet to "a, b" will output:

a a
a b
b a
b b
4 variations

Setting the input to "a, b, c" will output:

a a a
a a b
a a c
a b a
a b b
a b c
a c a
a c b
a c c
b a a
b a b
b a c
b b a
b b b
b b c
b c a
b c b
b c c
c a a
c a b
c a c
c b a
c b b
c b c
c c a
c c b
c c c
27 variations

I created this to work with words... inputs like "bread, breath, blobs, backwards". Be careful because you can quickly get millions of outputs:

1 to the power of 1 is 1
2 to the power of 2 is 4
3 to the power of 3 is 27
4 to the power of 4 is 256
5 to the power of 5 is 3125
6 to the power of 6 is 46,656
7 to the power of 7 is 823,543
8 to the power of 8 is 16,777,216
etc...

Also posted in Math, string manipulation | Tagged , | Leave a comment