 |
Minimum Distance Between Point and Line Segment
AB is the line SEGMENT.
C is the point to measure its distance from AB.
The shortest line from a point to a line is an orthogonal line. The orthogonal line intersects at a tangent. If the orthogonal line were rotated in either direction, it would move off the other line and would have to be increased to remain in intersection, thus it is has the minimum distance.
A-------------B
|
|
C
According to linear algebra, the dot product can be used to compute a projection of the vector onto another vector. In this case, the projection of C onto AB.
AC . AB
t = --------------
||AB|| * ||AB||
DotProduct( AC, AB )
t = --------------------
DistanceSquared( B ) = DotProduct( AB, AB )
t is a scalar that can be used to compute the point of intersection I:
I = A + t * (B - A)
Computer implementation:
The goal is find the minimum distance on a point on LINE SEGMENT. If the intersection is outside the LINE SEGMENT, then instead, compute the distances between CA and CB and return the minimum.
This C++ code is meant for testing/demonstration. It is implemented as a class/object as a lot of results are computed which are stored in data members (too complex for a function's return value).
References:
- "Linear Algebra", Tom Apostol
- comp.graphics.algorithms FAQ
////////////////////////////////////////////////////////////////////////////////
///
class DistancePointLineSegment
{
public:
/*****************************************************************************
* This constructor is the minimum distance function.
*****************************************************************************/
DistancePointLineSegment( const Vector2& a,
const Vector2& b,
const Vector2& c )
{
// AC and AB are vectors with A as the origin.
// Compute orthogonal projection of C onto AB as the scalar t.
const Vector2 ac( c - a );
const Vector2 ab( b - a );
mT = DotProduct( ac, ab )
/ DotProduct( ab, ab );
// If intersection is on the line SEGMENT (within A..B),
// then t = {0,..,1}.
if ( (mT >= 0.0f) and (mT <= 1.0f) )
{
mIfIntersectsLineSegment = true;
mIntersection.x = a.x + mT * (b.x - a.x);
mIntersection.y = a.y + mT * (b.y - a.y);
mDistance = Distance( mIntersection - c );
}
else
{
// The intersection is outside the line SEGMENT.
// Instead, compute the distances between CA and CB
// and return the minimum.
mIfIntersectsLineSegment = false;
//mIntersection.x = N/A
//mIntersection.y = N/A
mDistance = std::min( Distance( c-a ), Distance( c-b ) );
}
}
public:
bool mIfIntersectsLineSegment; ///< true if intersection on LINE SEGMENT (false if outside segment)
fp mT; ///< always valid
Vector2 mIntersection; ///< N/A if not mIfIntersectsLineSegment
fp mDistance; ///< minimum distance between point C and line segment AB
};
Test results:
"intersection = " means intersection within line segment (not infinite line)
----------------------------------------
Diagonal line from +Y to -X. Midpoint/intersection is obvious.
line = Vector2:(0,500) Vector2:(-500,0)
point = Vector2:(0,0)
t = 0.5
distance = 353.553
intersection = Vector2:(-250,250)
----------------------------------------
Horizontal line that spans -X..+X. Intersection is obvious.
line = Vector2:(-50,50) Vector2:(50,50)
point = Vector2:(0,0)
t = 0.5
distance = 50
intersection = Vector2:(0,50)
----------------------------------------
Diagonal thru origin.
line = Vector2:(-50,50) Vector2:(100,-100)
point = Vector2:(0,0)
t = 0.333333
distance = 0
intersection = Vector2:(0,0)
----------------------------------------
Diagonal aiming at origin but halfway there.
line = Vector2:(-50,50) Vector2:(-25,25)
point = Vector2:(0,0)
t = 2
distance = 35.3553
intersection = none
----------------------------------------
Diagonal aiming at origin but halfway there (swap a,b).
line = Vector2:(-25,25) Vector2:(-50,50)
point = Vector2:(0,0)
t = -1
distance = 35.3553
intersection = none
----------------------------------------
Directly aims at origin but does not quite reach.
line = Vector2:(-50,-50) Vector2:(-0.1,-0.1)
point = Vector2:(0,0)
t = 1.002
distance = 0.141421
intersection = none
----------------------------------------
Directly aims at origin but does not reach (swap a,b).
line = Vector2:(-0.1,-0.1) Vector2:(-50,-50)
point = Vector2:(0,0)
t = -0.00200401
distance = 0.141421
intersection = none
----------------------------------------
Skewed above origin towards NE.
line = Vector2:(-100,10) Vector2:(100,500)
point = Vector2:(0,0)
t = 0.0539093
distance = 96.3637
intersection = Vector2:(-89.2181,36.4156)
|
|
World 
Perspective 
