Home
Search
 
What's New
Index
Books
Links
Q & A
Newsletter
Banners
 
Feedback
Tip Jar
 
C# Helper...
 
XML RSS Feed
Follow VBHelper on Twitter
 
 
MSDN Visual Basic Community
 
 
 
 
 
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-2010 Rocky Mountain Computer Consulting, Inc.   All rights reserved.
  Updated