Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

Finding the intersection of two lines

Posted on 2010-09-02
13
Medium Priority
?
384 Views
Last Modified: 2012-05-10
Could you let me know the formlua for finding intersection of two lines ASAP? I have gone through google search could not find useful one so far.
 
Line1:  (x1,y1)-----------------------------------(x2,y2)
Line2:  (x3,y3)-----------------------------------(x4,y4)
0
Comment
Question by:shanpalaniram
  • 4
  • 3
  • 3
  • +2
12 Comments
 
LVL 86

Expert Comment

by:Mike Tomlinson
ID: 33587800
What language are you working in?...

There are various ways to do it but there isn't really a straight formula...it's more of a process.

The segments could:

(1) Be parallel and never intersect.
(2) Be parallel and intersect in a point or overlap in a segment.
(3) Be parallel and not intersect, but would if they were extended.

(4) Be non-parallel and intersect in a point.
(5) Be non-parallel and not intersect, but you need to know where they would intersect if one or both segments were extrapolated.
0
 

Author Comment

by:shanpalaniram
ID: 33588050
Thanks. I am working on VC++6.0.
0
 
LVL 86

Expert Comment

by:Mike Tomlinson
ID: 33588332
Can't help you with specific code as I haven't written anything in C/C++ in literally years.

I've used this method successfully in VB.Net:
http://www.cs.princeton.edu/algs4/91primitives/

Look in the third section called "Line segment intersection" which uses parameterized formulas and determinants.  You have to handle the special cases with ugly code but this approach will give you ALL of the information I outlined in my previous post.

Lemme know if you want to see the VB.Net code...
0
Prepare for your VMware VCP6-DCV exam.

Josh Coen and Jason Langer have prepared the latest edition of VCP study guide. Both authors have been working in the IT field for more than a decade, and both hold VMware certifications. This 163-page guide covers all 10 of the exam blueprint sections.

 

Author Comment

by:shanpalaniram
ID: 33594673
Could you send the VB .NET code please?
0
 
LVL 86

Accepted Solution

by:
Mike Tomlinson earned 672 total points
ID: 33596401
Hopefully you can glean something from this:
Public Class Geometry

    Public Enum SegmentIntersection
        None = 0 ' The segments are parallel and will never intersect
        Point = 1 ' The segments physically intersect in one point
        ExtrapolatedPoint = 2 ' The segments would physically intersect in one point if one or both segments were extended
        Overlapping = 3 ' The segments are parallel and overlap in a point or segment
    End Enum

    Public Shared Function SegmentIntersect( _
        ByVal A As Point, ByVal B As Point, _
        ByVal C As Point, ByVal D As Point, _
        ByRef E As Point, ByRef F As Point) As SegmentIntersection

        ' If one or both of the segments passed in is actually a point then just do a PointToSegmentDistance() calculation:
        If A.Equals(B) OrElse C.Equals(D) Then
            If A.Equals(B) AndAlso C.Equals(D) Then
                If A.Equals(C) Then
                    E = A
                    F = A
                    Return Geometry.SegmentIntersection.Point
                Else
                    Return Geometry.SegmentIntersection.None
                End If
            ElseIf A.Equals(B) Then
                If Geometry.PointToSegmentDistance(A.X, A.Y, C.X, C.Y, D.X, D.Y) = 0 Then
                    E = A
                    F = A
                    Return Geometry.SegmentIntersection.Point
                End If
            ElseIf C.Equals(D) Then
                If Geometry.PointToSegmentDistance(C.X, C.Y, A.X, A.Y, B.X, B.Y) = 0 Then
                    E = C
                    F = C
                    Return Geometry.SegmentIntersection.Point
                End If
            End If
            Return Geometry.SegmentIntersection.None
        End If

        ' We have two actual segments...let's do the calculations for Det1 and Det2:
        Dim Det1 As Double = (A.Y - C.Y) * (D.X - C.X) - (A.X - C.X) * (D.Y - C.Y)
        Dim Det2 As Double = (B.X - A.X) * (D.Y - C.Y) - (B.Y - A.Y) * (D.X - C.X)

        If Det2 <> 0 Then ' Non-Parallel Segments (they intersect or would intersect if extended)
            Dim Det3 As Double = (A.Y - C.Y) * (B.X - A.X) - (A.X - C.X) * (B.Y - A.Y)
            Dim Det4 As Double = (B.X - A.X) * (D.Y - C.Y) - (B.Y - A.Y) * (D.X - C.X)

            Dim r As Double = Det1 / Det2
            Dim s As Double = Det3 / Det4

            ' Compute the intersection point:
            E.X = A.X + r * (B.X - A.X)
            E.Y = A.Y + r * (B.Y - A.Y)
            F = E

            If (r >= 0 AndAlso r <= 1) AndAlso (s >= 0 AndAlso s <= 1) Then
                ' They physically intersect
                Return Geometry.SegmentIntersection.Point
            Else
                ' They would physically intersect if one or both segments were extended
                Return Geometry.SegmentIntersection.ExtrapolatedPoint
            End If
        Else ' Parallel Segments
            If Det1 <> 0 Then ' Non-Overlapping
                Return Geometry.SegmentIntersection.None
            Else ' Overlapping (one point or a segment)
                ' The parallel segments are the same
                If (A.Equals(C) AndAlso B.Equals(D)) OrElse (A.Equals(D) AndAlso B.Equals(C)) Then
                    E = A
                    F = B
                    Return Geometry.SegmentIntersection.Overlapping
                End If

                ' The parallel segments overlap in exactly one point
                If B.Equals(C) OrElse B.Equals(D) Then
                    E = B
                    F = B
                    Return Geometry.SegmentIntersection.Overlapping
                End If
                If A.Equals(C) OrElse A.Equals(D) Then
                    E = A
                    F = A
                    Return Geometry.SegmentIntersection.Overlapping
                End If

                ' The parallel segments are overlapping in a segment
                If Geometry.SegmentContainsPoint(A, B, C) AndAlso Geometry.SegmentContainsPoint(C, D, B) Then
                    E = C
                    F = B
                    Return Geometry.SegmentIntersection.Overlapping
                ElseIf Geometry.SegmentContainsPoint(A, B, D) AndAlso Geometry.SegmentContainsPoint(D, C, B) Then
                    E = D
                    F = B
                    Return Geometry.SegmentIntersection.Overlapping
                ElseIf Geometry.SegmentContainsPoint(B, A, C) AndAlso Geometry.SegmentContainsPoint(C, D, A) Then
                    E = C
                    F = A
                    Return Geometry.SegmentIntersection.Overlapping
                ElseIf Geometry.SegmentContainsPoint(B, A, D) AndAlso Geometry.SegmentContainsPoint(D, C, A) Then
                    E = D
                    F = A
                    Return Geometry.SegmentIntersection.Overlapping
                ElseIf Geometry.SegmentContainsPoint(C, D, A) AndAlso Geometry.SegmentContainsPoint(A, B, D) Then
                    E = A
                    F = D
                    Return Geometry.SegmentIntersection.Overlapping
                ElseIf Geometry.SegmentContainsPoint(C, D, B) AndAlso Geometry.SegmentContainsPoint(B, A, D) Then
                    E = B
                    F = D
                    Return Geometry.SegmentIntersection.Overlapping
                ElseIf Geometry.SegmentContainsPoint(D, C, A) AndAlso Geometry.SegmentContainsPoint(A, B, C) Then
                    E = A
                    F = C
                    Return Geometry.SegmentIntersection.Overlapping
                ElseIf Geometry.SegmentContainsPoint(D, C, B) AndAlso Geometry.SegmentContainsPoint(B, A, C) Then
                    E = B
                    F = C
                    Return Geometry.SegmentIntersection.Overlapping
                End If

                ' One segment completely contains the other
                If Geometry.SegmentContainsPoint(A, B, C) AndAlso Geometry.SegmentContainsPoint(A, B, D) Then
                    E = C
                    F = D
                    Return Geometry.SegmentIntersection.Overlapping
                End If
                If Geometry.SegmentContainsPoint(C, D, A) AndAlso Geometry.SegmentContainsPoint(C, D, B) Then
                    E = A
                    F = B
                    Return Geometry.SegmentIntersection.Overlapping
                End If

                ' Segments are parallel but not touching
                Return Geometry.SegmentIntersection.None
                End If
        End If
    End Function

    Public Shared Function PointToPointDistance(ByVal Ax As Single, _
        ByVal Ay As Single, ByVal Bx As Single, ByVal By As Single) _
        As Single
        ' PointToPointDist = SquareRoot((Bx - Ax)^2 + (By - Ay)^2)
        Return Math.Sqrt((Bx - Ax) * (Bx - Ax) + (By - Ay) * (By - Ay))
    End Function

    Public Shared Function PointToSegmentDistance( _
            ByVal Px As Single, ByVal Py As Single, _
            ByVal Ax As Single, ByVal Ay As Single, _
            ByVal Bx As Single, ByVal By As Single) As Single
        Dim q As Single

        If (Ax = Bx) And (Ay = By) Then
            ' A and B passed in define a point, not a line.
            ' Point to Point Distance
            Return PointToPointDistance(Px, Py, Ax, Ay)
        Else
            ' Distance is the length of the line needed to connect the point to
            ' the(segment)such that the two lines would be perpendicular.

            ' q is the parameterized value needed to get to the intersection
            q = ((Px - Ax) * (Bx - Ax) + (Py - Ay) * (By - Ay)) / _
                ((Bx - Ax) * (Bx - Ax) + (By - Ay) * (By - Ay))

            ' Limit q to 0 <= q <= 1
            ' If q is outside this range then the Point is somewhere past the 
            ' endpoints of our segment.  By setting q = 0 or q = 1 we are 
            ' measuring the actual distacne from the point to one of the 
            ' endpoints(instead)
            If q < 0 Then q = 0
            If q > 1 Then q = 1

            ' Distance
            Return PointToPointDistance( _
                Px, Py, (1 - q) * Ax + q * Bx, (1 - q) * Ay + q * By)
        End If
    End Function

    Public Shared Function SegmentContainsPoint( _
        ByVal A As Point, ByVal B As Point, ByVal C As Point) As Boolean
        ' Two Segments AB and CD have already been determined to have the 
        ' same slope and that they overlap.
        ' AB is the segment, and C is the point in question.
        ' If AB contains C then return true, otherwise return false
        If C.Equals(A) Or C.Equals(B) Then
            Return True
        ElseIf A.X = B.X Then ' Project to the Y-Axis for vertical lines
            Dim minY As Integer = Math.Min(A.Y, B.Y)
            Dim maxY As Integer = Math.Max(A.Y, B.Y)
            If minY <= C.Y AndAlso C.Y <= maxY Then
                Return True
            Else
                Return False
            End If
        Else ' Project to the X-Axis for anything else
            Dim minX As Integer = Math.Min(A.X, B.X)
            Dim maxX As Integer = Math.Max(A.X, B.X)
            If minX <= C.X AndAlso C.X <= maxX Then
                Return True
            Else
                Return False
            End If
        End If
    End Function

End Class

Open in new window

0
 

Author Comment

by:shanpalaniram
ID: 33596498
Thanks a lot. I will go through the code.
0
 
LVL 9

Assisted Solution

by:Orcbighter
Orcbighter earned 664 total points
ID: 33597214
Before you get lost in the code, just remember the algorithm from you year-12 maths:
Its just algebra.

1. First you need the equations of the two lines.
(a) a straight line will have the form of y = mx+b where m is the gradient, or slope, of the line and b is the intercept (the point where it crosses the y-axis). Since you only have two points for each line they are, by cynical definition straight)

(b) the gradient is m = (y2 - y1) / (x2 - x1) where x2 not equal x1

(c) you can test whether the two lines actually do intersect by the simple logic, that only parallel lines do not intersect (if extended forever in each direction). So, if parallel, they would both have the same gradient, otherwise they intersect, so continue.

(d) to get the intercept; after calculating the gradient, take a point and plug the x and y coordinates into the equation b = y - mx

now you have the equation of the first line, now do the second.

2. Then, since at the point of intersection, the two equations will have the same values of x and y, you set the two equations equal to each other. This gives an equation that you can solve for x

3. You substitute that x value in one of the line equations (it doesn't matter which) and solve it for y.

This gives you the x and y coordinates of the intersection.


0
 
LVL 2

Assisted Solution

by:Balajitr
Balajitr earned 664 total points
ID: 33597341
Perhaps this might help...I made it in VB, have'nt got to VC++ so far.

I used the determinant method to solve the equations, error handling to find out if the lines are parallel. Also finds out whether the line segments need to be extended.
'Take values from text-boxes
X1 = Val(Text1.Text)
Y1 = Val(Text2.Text)
X2 = Val(Text3.Text)
Y2 = Val(Text4.Text)
X3 = Val(Text5.Text)
y3 = Val(Text6.Text)
X4 = Val(Text7.Text)
y4 = Val(Text8.Text)

'Intermediate variables
a = Y1 - Y2
b = X2 - X1
c = X2 * Y1 - X1 * Y2
d = y3 - y4
e = X4 - X3
f = X4 * y3 - X3 * y4
denom = (a * e - b * d)

'Get the point of intersection
If denom <> 0 Then
    x = (c * e - b * f) / denom
    y = (a * f - c * d) / denom
Else
    Text9.Text = "Lines do not intersect"
End If

'Find out if the point lies in the segment
Text9.Text = "x = " & Format$(x, "#.###") & " y = " & Format$(y, "#.###")
If Not (((x > X1) And (x < X2)) Or ((x < X1) And (x > X2))) Then
    Text9.Text = Text9.Text & " : Line1 needs to be extended"
End If
If Not (((x > X3) And (x < X4)) Or ((x < X3) And (x > X4))) Then
    Text9.Text = Text9.Text & " : Line2 needs to be extended"
End If

Open in new window

0
 
LVL 2

Expert Comment

by:Balajitr
ID: 33597413
Oops.....some modification required in the last 6 lines :-

If Not (((x >= X1) And (x <= X2)) Or ((x <= X1) And (x >= X2))) Then
    Text9.Text = Text9.Text & " : Line1 needs to be extended"
End If
If Not (((x >= X3) And (x <= X4)) Or ((x <= X3) And (x >= X4))) Then
    Text9.Text = Text9.Text & " : Line2 needs to be extended"
End If

There shoud be comparison with equality.
0
 
LVL 2

Expert Comment

by:Balajitr
ID: 33597652
You could though re-arrange to have a more meaningful flow :-

'Take values from text-boxes
X1 = Val(Text1.Text)
Y1 = Val(Text2.Text)
X2 = Val(Text3.Text)
Y2 = Val(Text4.Text)
X3 = Val(Text5.Text)
y3 = Val(Text6.Text)
X4 = Val(Text7.Text)
y4 = Val(Text8.Text)

'Intermediate variables
a = Y1 - Y2
b = X2 - X1
c = X2 * Y1 - X1 * Y2
d = y3 - y4
e = X4 - X3
f = X4 * y3 - X3 * y4
denom = (a * e - b * d)

'Get the point of intersection
If denom <> 0 Then
    x = (c * e - b * f) / denom
    y = (a * f - c * d) / denom
    Text9.Text = "x = " & Format$(x, "#.###") & " y = " & Format$(y, "#.###")
   
    'Find out if the point lies in the segment
    If Not (((x >= X1) And (x <= X2)) Or ((x <= X1) And (x >= X2))) Then
        Text9.Text = Text9.Text & " : Line1 needs to be extended"
    End If
    If Not (((x >= X3) And (x <= X4)) Or ((x <= X3) And (x >= X4))) Then
        Text9.Text = Text9.Text & " : Line2 needs to be extended"
    End If
Else
    Text9.Text = "Lines do not intersect"
End If
0
 
LVL 2

Expert Comment

by:Balajitr
ID: 33678987
Well, shanpalaniram, did the solution work for you?
0
 
LVL 50
ID: 37163474
This question has been classified as abandoned and is closed as part of the Cleanup Program. See the recommendation for more details.
0

Featured Post

NEW Veeam Agent for Microsoft Windows

Backup and recover physical and cloud-based servers and workstations, as well as endpoint devices that belong to remote users. Avoid downtime and data loss quickly and easily for Windows-based physical or public cloud-based workloads!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

MS Access 2003 or later To MySQL Migration Project Hello All, this is my second article in the category of MS-OFFICE Automation. In internet I am not able to find any comprehensive resource on the Migration of MS Access back-end to MySQL so I fin…
This collection of functions covers all the normal rounding methods of just about any numeric value.
Viewers will learn how to maximize accessibility options in an Excel workbook for users with accessibility issues.
Viewers will learn the different options available in the Backstage view in Excel 2013.

824 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question