> Because you can use it to determine which side of the line a point is on?

How?

Example: Line through (0,0) and (0,1), and points either side of the line at 
(1,0) and (-1,0)

Post a reply to this message

scott wrote:
>> Because you can use it to determine which side of the line a point is on?
> 
> How?
> 
> Example: Line through (0,0) and (0,1), and points either side of the 
> line at (1,0) and (-1,0)

Suppose you have a line from point A to point B. Compute the vector AB, 

the dot product V . A and call it k.

Which side of the line is point X on? Well, take the dot product V . X, 
and subtract k. The result is negative on one side, positive on the 
other, and zero if X is on the line itself (or at least, parallel to it).

...so basically, it's a ray/plane intersection test, except the "plane" 
is a 2D slide - a line.

A = (0,0)
B = (0,1)
AB = (0,1) - (0,0) = (0,1) [already unital]
V = (0,1) * {(0,-1), (1,0)} = (-1,0)
k = (0,0) . (-1,0) = 0

X = (1,0)
X . V - k = (1,0) . (-1,0) - 0 = -1

Y = (-1,0)
Y . V - k = (-1,0) . (-1,0) - 0 = +1

QED.

Post a reply to this message

> Suppose you have a line from point A to point B. Compute the vector AB, 

> dot product V . A and call it k.
>
> Which side of the line is point X on? Well, take the dot product V . X, 
> and subtract k. The result is negative on one side, positive on the other, 
> and zero if X is on the line itself (or at least, parallel to it).
>
> ...so basically, it's a ray/plane intersection test, except the "plane" is 
> a 2D slide - a line.

Sorry, but that seems much more complicated and using up more instructions 
compared to the cross product:

> A = (0,0)
> B = (0,1)
> AB = (0,1) - (0,0) = (0,1) [already unital]

No need to make AB unital for the cross product method (saves a square root 
and divide).

> V = (0,1) * {(0,-1), (1,0)} = (-1,0)
> k = (0,0) . (-1,0) = 0

No need to calculate V or k for the cross product method (saves some 
multiplies and adds).

> X = (1,0)
> X . V - k = (1,0) . (-1,0) - 0 = -1

X cross AB = (1,0) x (0,1) = (1)(1) - (0)(0) = 1
(saves one subtraction compared to your method)

> Y = (-1,0)
> Y . V - k = (-1,0) . (-1,0) - 0 = +1

Y cross AB = (-1,0) x (0,1) = (-1)(1) - (0)(0) = -1
(saves one subtraction compared to your method)

Post a reply to this message

> No need to make AB unital for the cross product method (saves a square 
> root and divide).

Actually, thinking about it, you wouldn't need to for the dot product 
either. I should have seen that...

>> X = (1,0)
>> X . V - k = (1,0) . (-1,0) - 0 = -1
> 
> X cross AB = (1,0) x (0,1) = (1)(1) - (0)(0) = 1
> (saves one subtraction compared to your method)

Oh, I see. You're only computing the Z ordinate of the cross product? 
Well, I guess that could be quicker, yes...

Post a reply to this message

> Oh, I see. You're only computing the Z ordinate of the cross product? 

Well the other 2 ordinates are always zero, so there seems little point :-)

Post a reply to this message

scott wrote:
>> Oh, I see. You're only computing the Z ordinate of the cross product? 
> 
> Well the other 2 ordinates are always zero, so there seems little point :-)

...that's true, of course. I had it in my head that you would only 
compute the X and Y ordinates (which would take *more* effort than a 
simple dot product). But, of course, that would be pointless.

I should go sit in the corner now. :'{

Post a reply to this message

On 12/11/2009 02:43 AM, Slime wrote:
>> Have you tried this condition?
>>
>> ((distSq<  (radius1Sq+radius2Sq))
>> or (4*radius1Sq*radius2Sq>  (distSq - (radius1Sq+radius2Sq))^2))
>
> Smart. I feel stupid now! =) I see the equivalence, but I'm curious how long
> you took to come up with that. Was it obvious?
>
>   - Slime
>   [ http://www.slimeland.com/ ]
>
>
Well, it comes naturally from
distSq < radius1Sq + radius2Sq + 2 * radius1 * radius2
=>
distSq - (radius1Sq + radius2Sq ) <  2 * radius1 * radius2
=>
(distSq - (radius1Sq + radius2Sq ))^2 <  4 * radius1Sq * radius2Sq,

but the downside is that you have an overflow risk here to check

Post a reply to this message

bart <bart@home> wrote:
> Have you tried this condition?

> ((distSq < (radius1Sq+radius2Sq))
> or (4*radius1Sq*radius2Sq > (distSq - (radius1Sq+radius2Sq))^2))

  I was curious to see how much of a difference sqrt() really makes compared
to avoiding it, so I made this C++ file:

//-------------------------------------------------------------
#include <cmath>
#include <algorithm>

bool circlesCollide1(double cx1, double cy1, double rs1,
                     double cx2, double cy2, double rs2)
{
    const double vx = cx2 - cx1, vy = cy2 - cy1;
    return std::sqrt(vx*vx + vy*vy) < std::sqrt(rs1) + std::sqrt(rs2);
}

bool circlesCollide2(double cx1, double cy1, double rs1,
                     double cx2, double cy2, double rs2)
{
    const double vx = cx2 - cx1, vy = cy2 - cy1;
    const double dist2 = vx*vx + vy*vy;
    const double tmp = dist2 - (rs1 + rs2);
    return dist2 < rs1 + rs2 || 4.0*rs1*rs1 > tmp*tmp;
}
//-------------------------------------------------------------

and then a main program to test the speed:

//-------------------------------------------------------------
#include <iostream>
#include <ctime>

bool circlesCollide1(double cx1, double cy1, double rs1,
                     double cx2, double cy2, double rx2);
bool circlesCollide2(double cx1, double cy1, double rs1,
                     double cx2, double cy2, double rx2);

int main()
{
    double cx1 = -10.0, cy1 = -5.0, rs1_1 = 2.0*2.0, rs1_2 = 16.0*16.0;
    double cx2 = 5.0, cy2 = 10.0, rs2_1 = 2.5*2.5, rs2_2 = 18.0*18.0;
    const int iterations = 200000000;

    std::clock_t iClock = std::clock();
    for(int i = 0; i < iterations; ++i)
    {
        circlesCollide1(cx1, cy1, rs1_1, cx2, cy2, rs2_1);
        circlesCollide1(cx1, cy1, rs1_2, cx2, cy2, rs2_2);
    }
    std::clock_t eClock = std::clock();
    std::cout << "circlesCollide1: " << iterations << " iterations took "
              << double(eClock-iClock) / CLOCKS_PER_SEC << " seconds."
              << std::endl;

    iClock = std::clock();
    for(int i = 0; i < iterations; ++i)
    {
        circlesCollide2(cx1, cy1, rs1_1, cx2, cy2, rs2_1);
        circlesCollide2(cx1, cy1, rs1_2, cx2, cy2, rs2_2);
    }
    eClock = std::clock();
    std::cout << "circlesCollide2: " << iterations << " iterations took "
              << double(eClock-iClock) / CLOCKS_PER_SEC << " seconds."
              << std::endl;
}
//-------------------------------------------------------------

  I compiled with "-O3 -march=native" and got this result:

circlesCollide1: 200000000 iterations took 16.23 seconds.
circlesCollide2: 200000000 iterations took 5.42 seconds.

  (I didn't test that the functions give the correct result, though.)

-- 
                                                          - Warp

Post a reply to this message

On 12/11/2009 02:43 AM, Slime wrote:
>> Have you tried this condition?
>>
>> ((distSq<  (radius1Sq+radius2Sq))
>> or (4*radius1Sq*radius2Sq>  (distSq - (radius1Sq+radius2Sq))^2))
>
> Smart. I feel stupid now! =) I see the equivalence, but I'm curious how long
> you took to come up with that. Was it obvious?
>

hmm, it looks that this sqrt-free test
will equally work in 3D for sphere-sphere intersection test.

Post a reply to this message

> Suppose you have a line from point A to point B. Compute the vector AB, 

> dot product V . A and call it k.

If you do this in 2D, minus the unnecessary normalization, the math is 
equivalent to doing the 3D cross product while ignoring the components you 
know to be 0.

inline vec_t Vec2Cross( const vec2_t v1, const vec2_t v2 )
{
 return v1[0] * v2[1] - v1[1] * v2[0];
}

If the result is positive, v2 points to the "left" of v1, otherwise it 
points to the "right".

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message