milgra
about
articles
projects
blogroll
bit-101
coding horror
blameit
failblog
beszeljukmac
sghu
navigation
posts
docs
admin
|
Vector intersection calculations
|
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!!!
Source code
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!!!
|
|