Solved

Finding the intersection of two lines

Posted on 2010-09-02
13
358 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
13 Comments
 
LVL 85

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 85

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
 

Author Comment

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

Accepted Solution

by:
Mike Tomlinson earned 168 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
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 
LVL 9

Assisted Solution

by:Orcbighter
Orcbighter earned 166 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 166 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

Expert Comment

by:teylyn
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

Complete VMware vSphere® ESX(i) & Hyper-V Backup

Capture your entire system, including the host, with patented disk imaging integrated with VMware VADP / Microsoft VSS and RCT. RTOs is as low as 15 seconds with Acronis Active Restore™. You can enjoy unlimited P2V/V2V migrations from any source (even from a different hypervisor)

Join & Write a Comment

This collection of functions covers all the normal rounding methods of just about any numeric value.
Article by: Leon
Software Metering within our group of companies has always been an afterthought until auditing of software and licensing became a pain point. Orchestrator and SCCM metering gave us the answer and it was an exciting process.
The viewer will learn how to simulate a series of coin tosses with the rand() function and learn how to make these “tosses” depend on a predetermined probability. Flipping Coins in Excel: Enter =RAND() into cell A2: Recalculate the random variable…
The viewer will learn how to create two correlated normally distributed random variables in Excel, use a normal distribution to simulate the return on different levels of investment in each of the two funds over a period of ten years, and, create a …

746 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now