Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm trying to find the points on two lines where the two lines are the closest. I've implemented the following method (Points and Vectors are as you'd expect, and a Line consists of a Point on the line and a non-normalized direction Vector from that point):

void CDClosestPointsOnTwoLines(Line line1, Line line2, Point* closestPoints)
{
    closestPoints[0] = line1.pointOnLine;
    closestPoints[1] = line2.pointOnLine;

    Vector d1 = line1.direction;
    Vector d2 = line2.direction;

    float a = d1.dot(d1);
    float b = d1.dot(d2);
    float e = d2.dot(d2);

    float d = a*e - b*b;
    if (d != 0) // If the two lines are not parallel.
    {
        Vector r = Vector(line1.pointOnLine) - Vector(line2.pointOnLine);
        float c = d1.dot(r);
        float f = d2.dot(r);

        float s = (b*f - c*e) / d;
        float t = (a*f - b*c) / d;
        closestPoints[0] = line1.positionOnLine(s);
        closestPoints[1] = line2.positionOnLine(t);
    }
    else
    {
        printf("Lines were parallel.\n");
    }
}

I'm using OpenGL to draw three lines that move around the world, the third of which should be the line that most closely connects the other two lines, the two end points of which are calculated using this function.

The problem is that the first point of closestPoints after this function is called will lie on line1, but the second point won't lie on line2, let alone at the closest point on line2! I've checked over the function many times but I can't see where the mistake in my implementation is. I've checked my dot product function, scalar multiplication, subtraction, positionOnLine() etc. etc. So my assumption is that the problem is within this method implementation.

If it helps to find the answer, this is function supposed to be an implementation of section 5.1.8 from 'Real-Time Collision Detection' by Christer Ericson.

Many thanks for any help!

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

I've tested your code on a little program with OpenGL on a 2D space and the algorithm seems correct.

You says that direction is a non-normalized vector. Review that the method positionOnLine uses a normalized vector to do his calculations. I've used:

Vector2Df positionOnLine( float d )
{
    // where m_direction is a normalized vector
    return m_point + m_direction * d; 
}

More code:

My code is like this:

struct Line
{
    Line( const Vector2Df& p, const Vector2Df& d )
        : m_point( p )
        , m_direction( d )
    {
        m_direction.normalize();
    }

    Vector2Df positionOnLine( float d )
    {
        return m_point + m_direction * d;
    }

    Vector2Df   m_point;
    Vector2Df   m_direction;
};

// Lines creation
Vector2Df v1( 0.f, 0.f );
Vector2Df v2( 100.f, 100.f );

Vector2Df v3( 10.f, 0.f );
Vector2Df v4( 100.f, 110.f );

Line l1( v1, v2 - v1 );
Line l2( v3, v4 - v3 );
share|improve this answer
    
I've ensured that this is normalized and now it seems that the shortest connecting now at least starts and finishes in a way that connects the two lines. The problem now is that this isn't the shortest distance. The end point of the connecting line is always very close to the start of the other line. –  James Bedford Mar 14 '11 at 17:22
    
I think the problem lies with how I'm passing in my two lines... I'm just not sure why? I'm passing a start point of the line, and then a point 100 * the normalized direction away from it for the end point of the line (for both lines), does this seem right? Thanks for your help! –  James Bedford Mar 14 '11 at 19:04
    
But, then? How do you calculate the direction of a line? If you have the direction, why do you need the second point? Remember you are dealing with lines, not segments. I've edited my answer so you can see my code. –  momboco Mar 14 '11 at 23:10
    
Many, many thanks for the help! I managed to trace my problem down to the matrix manipulation I was doing to the vectors I was passing into the line creation functons! Thanks! –  James Bedford Mar 15 '11 at 19:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.