Do two line segments intersect in c# or vb.net using xna?

Question

I have been looking for ages for a suitable method of finding if two line segments (2 sets of x,y co-ords each) intercept. I have seen many (including: How do you detect where two line segments intersect?), but all the one I have seen have flaws. Mainly that they do not detect a collision if the lines are parallel but overlap each other.

I also do not need the point of intersection to be returned, just a boolean would be fine.

I would be really grateful if someone could point me in the right direction cos apparently I suck at geometry. :(

It seems to me the 'parallel lines' case would need to be treated separately. All other intersection algorithms would test for a single point of intersection. I'd expect the parallel case would be fairly trivial to solve, though. How often do you expect precise parallel lines, though? That's nigh impossible if you're using floating-point values to represent lines. EDIT: Actually, the top solution given in the question you posted provides a solution for that case, too. Look for the part where he gives an inequality that tests for colinearity. — Kenogu Labz, Oct 18 '12 at 21:12
If I am honest, reading the top answer of that question. I get lost on the second sentence... I don't think I would not be able to organise any of what he is saying into usable code without seriously studying some maths... I have enough on my plate with programming atm. I think I have found an a suitable method, which although doesn't solve the parallel lines problem, does make it easy for me to cobble something together... I will post it here when its done. — Gravitate, Oct 18 '12 at 22:01
Alright. I can also try posting an answer here later that should help explain how to translate the math into code. I think you'll find it's not as difficult as it looks! :) — Kenogu Labz, Oct 18 '12 at 22:11

Peter Gluck · Accepted Answer · 2012-10-19T21:52:28.470

5

There are certainly mathematically elegant ways to do it, but if you are looking for an easy-to-understand algorithm using basic algebra, try this (this is NOT code):

Let's define two line segments by their endpoints:

l0 : { (x0, y0), (x1, y1) }
l1 : { (x2, y2), {x3, y3) }

First, obtain the slope-intercept form of each line. You can look up the formulae for m, b or derive them yourself:

l0 : m0 * x + b0
l1 : m1 * x + b1

if (m0 != m1) the lines are not parallel. To find the potential intersection point solve l0 = l1:

x = (b1 - b0) / (m0 - m1)
y = m0 * x + b0

The segments will intersect if and only if (x, y) lies on both segments. Note that it is sufficient to check only the x-coordinate since we have already established that (x, y) is on both lines:

[Edited to reflect excellent input from @KenoguLabz]

(x0 <= x <= x1) AND (x2 <= x <= x3) AND (y0 <= y <= y1) AND (y2 <= y <= y3)

min(x0, x1) <= x <= max(x0, x1) AND min(x2, x3) <= x <= max(x2, x3)

If the lines are parallel and you want to know if they overlap, substitute the endpoints of one line for x above (you only need test against the opposite line, though)

Hope this helps. Good luck!

edited Oct 19 '12 at 21:52

answered Oct 19 '12 at 00:45

Peter Gluck

8,168
1
38
37

1

That final check can be simplified to simply check either x OR y coordinates, I believe. Also note that you need to make sure x0 <= x1, x2 <= x3, etc. for this to work. Think of it as xh, xi, xj and xk where xh = min(x0, x1), xi = max(x0, x1), xj = min(x2, x3) and xk = max(x2, x3). Then the condition becomes (xh <= x <= xi) AND (xj <= x <= xk). – Kenogu Labz Oct 19 '12 at 01:45
Thank you, I think I understood a bit more of that. I don't know how you worked out the formulas to solve l0=l1 though. @KenoguLabz Why do you only have to check x OR y? Does that mean you don't even need to calculate one of the x and y co-ords? – Gravitate Oct 19 '12 at 20:19
Finding l0 = l1 is done algebraically from the slope-intercept form. You have y = m0 * x + b0 and y = m1 * x + b1. When these two lines intersect, x and y are the same. This allows us to solve for x and y independently. If we take the value of y from the equation for l0 and substitute the value of y from equation l1, you get: m0 * x + b0 = m1 * x + b1. Solving for x: m1 * x - m0 * x = b1 - b0 ==> x = (b1 - b0) / (m0 - m1). Then substitute the value you find into one of the equations l0 or l1 to find the value of y. This may be best posted in the answer itself, or as another answer. – Kenogu Labz Oct 19 '12 at 21:02
What I meant by 'only checking x or y' is that you only need to use either the first two or the last two parts of the test he gave above. So you can use (x0 <= x <= x1) AND (x2 <= x <= x3), or you can use (y0 <= y <= y1) AND (y2 <= y <= y3). You can use both as well, but the logic would be redundant. – Kenogu Labz Oct 19 '12 at 21:05
And as a last note: if you're planning on developing games, you'll likely be using quite a bit of algebra and trigonometry. Make sure you've brushed up on that before you dig deeper; it's not easy, but it's rewarding, and you'll be able to make the mechanics and graphics of your game much more robust having done so. – Kenogu Labz Oct 19 '12 at 21:11
1

@Gravitate To expand on what Kenogu Labz said, the reason you need only check either the x OR the y coordinates is because you've already established that `(x, y)` is on the line. If x satisfies the relationship then so will y, and vice versa. – Peter Gluck Oct 19 '12 at 21:45
I realise I am sounding quite unintelligent here (I don't know why I struggle so much with algebra, I think it is just the way it's written, it is like another language to me. I am fine with source code and that kind of logic). @KenguLabs Thank you for your input but I am afraid I couldn't follow much of what you said. Thank you Peter for clarifying. I understand now that because the lines are not parallel, they must cross somewhere along their infinite length (but perhaps not in our segment) so we can then check where either the x or y value is on the line because the other will match up. – Gravitate Oct 19 '12 at 22:05
@PeterGluck You say to check if parallel lines overlap, I can substitute in an endpoint and check against the other line. It's not as simple as that is it? I would then have to check the y co-ords as well wouldn't I. Also if one line was smaller, it could fit within the other lines start and end points but still not over lap couldn't it?... I may need a diagram to explain what I mean... – Gravitate Oct 20 '12 at 11:42
Yes, it is that simple. If the x value matches, the y value will also match because it satisfies the solution to the intersection point equation. Think of it this way: if it is the same line then m0 = m1 and b0 = b1. – Peter Gluck Oct 22 '12 at 07:13

score 2 · Answer 2 · edited Feb 26 '13 at 19:12

Here is a small class that I recently wrote. The +/- of the slope and angle may not always be correct (for example, when angle should be -90, it returns 90, but the trig functions I use are unaffected by this). The function you will probably be most interested in is GetIntersection, which returns Nothing (null) for parallel lines, otherwise it returns a Point. Here is the code:

Public Class LineData
    Public Property Point1() As Point
    Public Property Point2() As Point
    Public ReadOnly Property Slope() As Double
        Get
            # 0=Horizontal Line, NaN=Vertical Line
            Return If(Me.Point1.X = Me.Point2.X, Double.NaN, (Me.Point1.Y - Me.Point2.Y) / (Me.Point1.X - Me.Point2.X))
        End Get
    End Property
    Public ReadOnly Property YIntercept() As Double
        Get
            Return If(Double.IsNaN(Me.Slope), Double.NaN, Me.Point1.Y - Me.Slope * Me.Point1.X)
        End Get
    End Property
    Public ReadOnly Property Angle() As Double
        Get
            Return If(Double.IsNaN(Me.Slope), Math.PI / 2, Math.Atan(Me.Slope))
        End Get
    End Property

    Public Sub New(pt1 As Point, pt2 As Point)
        Me.Point1 = pt1
        Me.Point2 = pt2
    End Sub
    Public Sub New(x1 As Double, y1 As Double, x2 As Double, y2 As Double)
        Me.Point1 = New Point(x1, y1)
        Me.Point2 = New Point(x2, y2)
    End Sub
    Public Sub New(ln As Line)
        Me.New(ln.X1, ln.Y1, ln.X2, ln.Y2)
    End Sub

    Public Function GetParallel(spacing As Double) As LineData
        Return Me.GetParallel(spacing, ParallelPosition.Below)
    End Function

    Public Function GetParallel(spacing As Double, pos As ParallelPosition) As LineData
        If Me.Slope = 0 Then # Horizontal Line
            If pos = ParallelPosition.Above OrElse pos = ParallelPosition.Left Then : Return If(Me.Point2.X > Me.Point1.X, New LineData(Me.Point1.X - spacing, Me.Point1.Y - spacing, Me.Point2.X + spacing, Me.Point2.Y - spacing), New LineData(Me.Point1.X + spacing, Me.Point1.Y - spacing, Me.Point2.X - spacing, Me.Point2.Y - spacing))
            Else : Return If(Me.Point2.X > Me.Point1.X, New LineData(Me.Point1.X - spacing, Me.Point1.Y + spacing, Me.Point2.X + spacing, Me.Point2.Y + spacing), New LineData(Me.Point1.X + spacing, Me.Point1.Y + spacing, Me.Point2.X - spacing, Me.Point2.Y + spacing))
            End If
        ElseIf Double.IsNaN(Me.Slope) Then # Vertical Line
            If pos = ParallelPosition.Above OrElse pos = ParallelPosition.Left Then : Return If(Me.Point2.Y > Me.Point1.Y, New LineData(Me.Point1.X - spacing, Me.Point1.Y - spacing, Me.Point2.X - spacing, Me.Point2.Y + spacing), New LineData(Me.Point1.X - spacing, Me.Point1.Y + spacing, Me.Point2.X - spacing, Me.Point2.Y - spacing))
            Else : Return If(Me.Point2.Y > Me.Point1.Y, New LineData(Me.Point1.X + spacing, Me.Point1.Y - spacing, Me.Point2.X + spacing, Me.Point2.Y + spacing), New LineData(Me.Point1.X + spacing, Me.Point1.Y + spacing, Me.Point2.X + spacing, Me.Point2.Y - spacing))
            End If
        Else #Sloped Line
            Dim verticalshift As Double = Math.Abs(spacing / Math.Cos(-Me.Angle))
            Dim horizontalshift As Double = Math.Abs(spacing / Math.Sin(-Me.Angle))
            If Math.Sign(Me.Slope) = -1 Then
                If Me.Point2.X > Me.Point1.X Then
                    If pos = ParallelPosition.Above OrElse pos = ParallelPosition.Left Then : Return New LineData(Me.Point1.X - horizontalshift, Me.Point1.Y, Me.Point2.X, Me.Point2.Y - verticalshift)
                    Else : Return New LineData(Me.Point1.X, Me.Point1.Y + verticalshift, Me.Point2.X + horizontalshift, Me.Point2.Y)
                    End If
                Else
                    If pos = ParallelPosition.Above OrElse pos = ParallelPosition.Left Then : Return New LineData(Me.Point1.X, Me.Point1.Y - verticalshift, Me.Point2.X - horizontalshift, Me.Point2.Y)
                    Else : Return New LineData(Me.Point1.X + horizontalshift, Me.Point1.Y, Me.Point2.X, Me.Point2.Y + verticalshift)
                    End If
                End If
            Else
                If Me.Point2.X > Me.Point1.X Then
                    If pos = ParallelPosition.Above OrElse pos = ParallelPosition.Right Then : Return New LineData(Me.Point1.X, Me.Point1.Y - verticalshift, Me.Point2.X + horizontalshift, Me.Point2.Y)
                    Else : Return New LineData(Me.Point1.X - horizontalshift, Me.Point1.Y, Me.Point2.X, Me.Point2.Y + verticalshift)
                    End If
                Else
                    If pos = ParallelPosition.Above OrElse pos = ParallelPosition.Right Then : Return New LineData(Me.Point1.X + horizontalshift, Me.Point1.Y, Me.Point2.X, Me.Point2.Y - verticalshift)
                    Else : Return New LineData(Me.Point1.X, Me.Point1.Y + verticalshift, Me.Point2.X - horizontalshift, Me.Point2.Y)
                    End If
                End If
            End If
        End If
    End Function

    Public Function CalculateX(y As Double) As Double
        If Me.Slope = 0 Then # Horizontal Line
            If y = Me.Point1.Y OrElse y = Me.Point2.Y Then Return 0 Else Return Double.NaN
        ElseIf Double.IsNaN(Me.Slope) Then # Vertical Line
            Return Me.Point1.X
        Else
            Return (y - Me.YIntercept) / Me.Slope
        End If
    End Function
    Public Function CalculateY(x As Double) As Double
        If Me.Slope = 0 Then # Horizontal Line
            Return Me.Point1.Y
        ElseIf Double.IsNaN(Me.Slope) Then # Vertical Line
            If x = Me.Point1.X OrElse x = Me.Point2.X Then Return 0 Else Return Double.NaN
        Else
            Return Me.Slope * x + Me.YIntercept
        End If
    End Function

    Public Function GetIntersection(ln As LineData) As Point
        If Me.Slope = ln.Slope OrElse (Double.IsNaN(Me.Slope) AndAlso Double.IsNaN(ln.Slope)) Then : Return Nothing
        Else
            If Double.IsNaN(Me.Slope) Then : Return New Point(Me.Point1.X, ln.CalculateY(Me.Point1.X))
            ElseIf Double.IsNaN(ln.Slope) Then : Return New Point(ln.Point1.X, Me.CalculateY(ln.Point1.X))
            ElseIf Me.Slope = 0 Then : Return New Point(ln.CalculateX(Me.Point1.Y), Me.Point1.Y)
            ElseIf ln.Slope = 0 Then : Return New Point(Me.CalculateX(ln.Point1.Y), ln.Point1.Y)
            Else
                Dim x As Double = (Me.YIntercept - ln.YIntercept) / (ln.Slope - Me.Slope)
                Return New Point(x, Me.CalculateY(x))
            End If
        End If
    End Function

    Public Function GetLine() As Line
        Dim templine As New Line
        templine.X1 = Me.Point1.X
        templine.Y1 = Me.Point1.Y
        templine.X2 = Me.Point2.X
        templine.Y2 = Me.Point2.Y
        Return templine
    End Function
End Class

Public Enum ParallelPosition As Byte
    Above
    Below
    Left
    Right
End Enum

Hopefully this helps!

Do two line segments intersect in c# or vb.net using xna?

2 Answers2