Home
Search
 
What's New
Index
Books
Links
Q & A
Newsletter
Banners
 
Feedback
Tip Jar
 
 
 
 
 
 
 
 
Old Pages
 
Old Index
Site Map
What's New
 
Books
How To
Tips & Tricks
Tutorials
Stories
Performance
Essays
Links
Q & A
New in VB6
Free Stuff
Pictures
 
 
 
TitleSee where two lines intersect
Keywordsline, intersect
CategoriesGraphics, Algorithms
 
Treat the lines as parametric where line 1 is:

    X = x11 + dx1 * t1
    Y = y11 + dy1 * t1

and line 2 is:

    X = x21 + dx2 * t2
    Y = y21 + dy2 * t2

Setting these equal gives:

    x11 + dx1 * t1 = x21 + dx2 * t2
    y11 + dy1 * t1 = y21 + dy2 * t2

Rearranging:

    x11 - x21 + dx1 * t1 = dx2 * t2
    y11 - y21 + dy1 * t1 = dy2 * t2

    (x11 - x21 + dx1 * t1) *   dy2  = dx2 * t2 *   dy2
    (y11 - y21 + dy1 * t1) * (-dx2) = dy2 * t2 * (-dx2)

Adding the equations gives:

    (x11 - x21) * dy2 + ( dx1 * dy2) * t1 +
    (y21 - y11) * dx2 + (-dy1 * dx2) * t1 = 0

Solving for t1 gives:

    t1 * (dy1 * dx2 - dx1 * dy2) =
    (x11 - x21) * dy2 + (y21 - y11) * dx2

    t1 = ((x11 - x21) * dy2 + (y21 - y11) * dx2) /
         (dy1 * dx2 - dx1 * dy2)

Similarly solve for t2.

Notes:

  • If 0 ≤ t1 ≤ 1, then the point lies on segment 1.
  • If 0 ≤ t2 ≤ 1, then the point lies on segment 1.
  • If dy1 * dx2 - dx1 * dy2 = 0 then the lines are parallel.
  • If the point of intersection is not on both segments, then this is almost certainly not the point where the two segments are closest.
 
' Find the point where two segments intersect.
Public Sub FindLineIntersection( _
    ByVal x11 As Single, ByVal y11 As Single, _
    ByVal x12 As Single, ByVal y12 As Single, _
    ByVal x21 As Single, ByVal y21 As Single, _
    ByVal x22 As Single, ByVal y22 As Single, _
    ByRef inter_x As Single, ByRef inter_y As Single, _
    ByRef inter_x1 As Single, ByRef inter_y1 As Single, _
    ByRef inter_x2 As Single, ByRef inter_y2 As Single)
Dim dx1 As Single
Dim dy1 As Single
Dim dx2 As Single
Dim dy2 As Single
Dim t1 As Single
Dim t2 As Single
Dim denominator As Single

    ' Get the segments' parameters.
    dx1 = x12 - x11
    dy1 = y12 - y11
    dx2 = x22 - x21
    dy2 = y22 - y21

    ' Solve for t1 and t2.
    On Error Resume Next
    denominator = (dy1 * dx2 - dx1 * dy2)
    t1 = ((x11 - x21) * dy2 + (y21 - y11) * dx2) / _
        denominator
    If Err.Number <> 0 Then
        ' The lines are parallel.
        inter_x = 1E+38:          inter_y = 1E+38
        inter_x1 = 1E+38:         inter_y1 = 1E+38
        inter_x2 = 1E+38:         inter_y2 = 1E+38
        Exit Sub
    End If
    On Error GoTo 0
    t2 = ((x21 - x11) * dy1 + (y11 - y21) * dx1) / _
        -denominator

    ' Find the point of intersection.
    inter_x = x11 + dx1 * t1
    inter_y = y11 + dy1 * t1

    ' Find the closest points on the segments.
    If t1 < 0 Then
        t1 = 0
    ElseIf t1 > 1 Then
        t1 = 1
    End If
    If t2 < 0 Then
        t2 = 0
    ElseIf t2 > 1 Then
        t2 = 1
    End If
    inter_x1 = x11 + dx1 * t1
    inter_y1 = y11 + dy1 * t1
    inter_x2 = x21 + dx2 * t2
    inter_y2 = y21 + dy2 * t2
End Sub
 
 
Copyright © 1997-2003 Rocky Mountain Computer Consulting, Inc.   All rights reserved.
  Updated