Solved

Finding the intersection of two lines

Posted on 2010-09-02
13
361 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
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)

 
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:Ingeborg Hawighorst
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

Backup Your Microsoft Windows Server®

Backup all your Microsoft Windows Server – on-premises, in remote locations, in private and hybrid clouds. Your entire Windows Server will be backed up in one easy step with patented, block-level disk imaging. We achieve RTOs (recovery time objectives) as low as 15 seconds.

Question has a verified solution.

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

Suggested Solutions

A theme is a collection of property settings that allow you to define the look of pages and controls, and then apply the look consistently across pages in an application. Themes can be made up of a set of elements: skins, style sheets, images, and o…
Lync meeting or Lync conferencing is what many organizations would like to deploy to allow them save money. But companies are now giving up for various reasons, one of which is that they cannot join external meetings (non-federated company meetings)…
Viewers will learn the different options available in the Backstage view in Excel 2013.
The viewer will learn how to use a discrete random variable to simulate the return on an investment over a period of years, create a Monte Carlo simulation using the discrete random variable, and create a graph to represent the possible returns over…

911 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

21 Experts available now in Live!

Get 1:1 Help Now