?
Solved

Finding the intersection of two lines

Posted on 2010-09-02
13
Medium Priority
?
381 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
  • 3
  • +2
13 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
How Blockchain Is Impacting Every Industry

Blockchain expert Alex Tapscott talks to Acronis VP Frank Jablonski about this revolutionary technology and how it's making inroads into other industries and facets of everyday life.

 

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

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)

Question has a verified solution.

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

As with any other System Center product, the installation for the Authoring Tool can be quite a pain sometimes. This article serves to help you avoid making these mistakes and hopefully save you a ton of time on troubleshooting :)  Step 1: Make sur…
Deploying a Microsoft Access application in a Citrix environment is not difficult but takes a few steps. However, Citrix system people are often of little help, as they typically know next to nothing about Access. The script provided here will take …
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 view will learn how to download and install SIMTOOLS and FORMLIST into Excel, how to use SIMTOOLS to generate a Monte Carlo simulation of 30 sales calls, and how to calculate the conditional probability based on the results of the Monte Carlo …

719 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