Milan Toth

Milan Toth is the Chief Flash Developer of Jasmin Media Group, he created one of the world's biggest flash media server system. He loves Eclipse and OS X, AS3 and JAVA, sci-fi and horror, metal and electronic.

View all articles by Milan Toth
The first and most preferred method for intersection calculation is the per-product calculation. There are two vectors, v1 and v2. Create a third vector vector between the starting points of these vectors, and calculate the per product of v2 and the two other vectors. These two scalars have to be divided to get the mulitplication ratio of v1 to reach intersection point. So:

v1 ( bx1 , by1 );
v2 ( bx2 , by2 );
v3 ( bx3 , by3 );

Per product is equal with dot product of normal of first vector and the second vector, so we need normals:

n1 ( -by1 , bx1 );
n3 ( -by3 , bx3 );

Dot products:

dp1 = n3.v2 = -by3*bx2 + bx3*by2;
dp2 = n1.v2 = -by1*bx2 + bx1*by2;

ratio = dp1/dp2;
crossing vector = v1*rat;

And that's it.

Let's see the other algorythm. Calculate the intersection point of the two lines on the vectors using the equation of the line.

v1 ( bx1 , by1 );
v2 ( bx2 , by2 );

l1: y1 = m1*x1 + b1;
l2: y2 = m2*x2 + b2;

Where the lines crossing: x1 = x2 and y1 = y2 so

y = m1*x + b1;
y = m2*x + b2;

m1*x + b1 = m2*x + b2;
x*( m1 - m2 ) = b2 - b1;

so

x = ( b2 - b1 ) / ( m1 - m2 );
y = m1 * x + b1;

And we are ready.

So, we have two formulas:

Dot product:

dp1 = n3.v2 = -by3*bx2 + bx3*by2;
dp2 = n1.v2 = -by1*bx2 + bx1*by2;

ratio = dp1/dp2;
crossing vector = v1*rat;

Line intersection:

x = ( b2 - b1 ) / ( m1 - m2 );
y = m1 * x + b1;

They calculate the intersection point of two vectors, but beware : we still don't know if this intersection point is on both vectors!!! So, additional calculations needed, we can check if the intersection point's x coordinate is between the x-axis intervals of the two "parent" vectors, or, using dot product method, we can calculate the ratio for the other vector, and if it is 1 for both vectors, they intersect. I think the line intersection version with interval check is simpler and faster, but let's prove it!!!

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

    public class Vectors extends Sprite
    {
        
        public function Vectors( )
        {
            
            addEventListener( Event.ENTER_FRAME , init );
            
        }
        
        public function init ( event:Event ):void
        {
            
            removeEventListener( Event.ENTER_FRAME , init );
            
            // cycle count

            var CYCLES:Number = 100000;

            // helpers
            
            var a:Number;
            var v1:Vector;
            var v2:Vector;
            var crossPoint:Point;
            
            var delay:Number;
            var timeStamp:Number;
            
            // calculation duration
            
            var duration:Number = 0;
            
            // multiple vectors with per product
            
            for ( a = 0 ; a < CYCLES ; a++ )
            {
                
                v1 = new Vector( Math.random( ) * stage.stageWidth ,
                                 Math.random( ) * stage.stageHeight ,
                                 Math.random( ) * stage.stageWidth ,
                                 Math.random( ) * stage.stageHeight );

                v2 = new Vector( Math.random( ) * stage.stageWidth ,
                                 Math.random( ) * stage.stageHeight ,
                                 Math.random( ) * stage.stageWidth ,
                                 Math.random( ) * stage.stageHeight );

                timeStamp = ( new Date( ) ).time;
                
                crossPoint = perProduct( v1 , v2 );
                
                delay = ( new Date( ) ).time - timeStamp;
                
                duration += delay;                
                                
                
            }
                        
            trace( "multivector per product duration: " + duration + " ms" );
            
            duration = 0;
            
            // multiple vectors with line crossing
            
            for ( a = 0 ; a < CYCLES ; a++ )
            {
                
                v1 = new Vector( Math.random( ) * stage.stageWidth ,
                                 Math.random( ) * stage.stageHeight ,
                                 Math.random( ) * stage.stageWidth ,
                                 Math.random( ) * stage.stageHeight );

                v2 = new Vector( Math.random( ) * stage.stageWidth ,
                                 Math.random( ) * stage.stageHeight ,
                                 Math.random( ) * stage.stageWidth ,
                                 Math.random( ) * stage.stageHeight );

                timeStamp = ( new Date( ) ).time;
                
                crossPoint = lineCrossing( v1 , v2 );
                
                delay = ( new Date( ) ).time - timeStamp;
                
                duration += delay;                
                                    
            }
            
            trace( "multivector line crossing duration: " + duration + " ms" );
                        
            v1 = new Vector( Math.random( ) * stage.stageWidth ,
                             Math.random( ) * stage.stageHeight ,
                             Math.random( ) * stage.stageWidth ,
                             Math.random( ) * stage.stageHeight );

            v2 = new Vector( Math.random( ) * stage.stageWidth ,
                             Math.random( ) * stage.stageHeight ,
                             Math.random( ) * stage.stageWidth ,
                             Math.random( ) * stage.stageHeight );
                             
            timeStamp = ( new Date( ) ).time;
            
            // one vector with per product
                             
            for ( a = 0 ; a < CYCLES ; a++ )
            {
                
                crossPoint = perProduct( v1 , v2 );
                
            }
            
            duration = ( new Date( ) ).time - timeStamp;
            
            trace( "simplevector per product duration: " + duration + "ms" );
                             
            timeStamp = ( new Date( ) ).time;
            
            // one vector with line crossing
                             
            for ( a = 0 ; a < CYCLES ; a++ )
            {
                
                crossPoint = lineCrossing( v1 , v2 );
                
            }
            
            duration = ( new Date( ) ).time - timeStamp;
            
            trace( "simplevector line crossing duration: " + duration +"ms" );            
        }

            
        public function lineCrossing ( v1 : Vector , v2 : Vector ):Point
        {

            var m1:Number = v1.by / v1.bx;
            var b1:Number = v1.sy - m1 * v1.sx;
            var m2:Number = v2.by / v2.bx;
            var b2:Number = v2.sy - m2 * v2.sx;

            var cx:Number = ( b2 - b1 )/( m1 - m2 );
            var cy:Number = m1 * cx + b1;

            return new Point( cx , cy );            
            
        }
        
        
        public function perProduct ( v1 : Vector , v2 : Vector ):Point
        {

            var v3bx:Number = v2.sx - v1.sx;
            var v3by:Number = v2.sy - v1.sy;
            
            var perP1:Number = v3bx * v2.by - v3by * v2.bx;
            var perP2:Number = v1.bx * v2.by - v1.by * v2.bx;
            
            var ratio:Number = perP1 / perP2;

            var cx:Number = v1.sx + v1.bx * ratio;
            var cy:Number = v1.sy + v1.by * ratio;

            return new Point( cx , cy );                    
            
        }
        
    }        
    
}
class Vector
{
    
    // start points
    
    public var sx:Number;
    public var sy:Number;
    
    // base vectors
    
    public var bx:Number;
    public var by:Number;
    
    public function Vector( argsx : Number , 
                                          argsy : Number , 
                                          argex : Number , 
                                          argey : Number )
    {
        
        sx = argsx;
        sy = argsy;
        
        bx = argex - sx;
        by = argey - sy;
        
    }
    
}


Here are my first five results:

multivector per product duration: 383 ms
multivector line crossing duration: 416 ms
simplevector per product duration: 237ms
simplevector line crossing duration: 235ms

multivector per product duration: 420 ms
multivector line crossing duration: 366 ms
simplevector per product duration: 236ms
simplevector line crossing duration: 231ms

multivector per product duration: 415 ms
multivector line crossing duration: 430 ms
simplevector per product duration: 238ms
simplevector line crossing duration: 236ms

multivector per product duration: 411 ms
multivector line crossing duration: 408 ms
simplevector per product duration: 234ms
simplevector line crossing duration: 234ms

multivector per product duration: 425 ms
multivector line crossing duration: 407 ms
simplevector per product duration: 246ms
simplevector line crossing duration: 236ms

Line crossing method looks a little bit better, altough per product could be faster in some cases.

That's all folks!!!