Test for rectangle-line intersection

Question

I am trying to see if an imagebox interacts with an e graphics line. my current code:

e.Graphics.DrawLine(SystemPens.ButtonShadow, a, b);

if (pictureBox1.Bounds.IntersectsWith(e.GraphicsLine.Bounds))
{
    dead();
}

I am unsure how to do this.

Answer 1

To test for intersection of a rectangle and a line you can either use one of the many methods from the Wikipedia article or use a GDI+ trick involving GraphicsPaths and Regions..:

using System.Drawing.Drawing2D;
..

bool Intersects(Point a, Point b, Rectangle r)
{
    if (Math.Min(a.X, b.X) > r.Right)  return false;   // *
    if (Math.Max(a.X, b.X) < r.Left)   return false;   // *
    if (Math.Min(a.Y, b.Y) > r.Bottom) return false;   // *
    if (Math.Max(a.Y, b.Y) < r.Top)    return false;   // *

    if (r.Contains(a)) return true;   // **
    if (r.Contains(b)) return true;   // **

    using (GraphicsPath gp = new GraphicsPath())
    using (Pen pen = new Pen(Color.Empty, 0.5f))
    using (Region reg = new Region(r))
    using (Graphics g = CreateGraphics())
    {
        gp.AddLine(a,b);
        gp.Widen(pen);   // we need to widen the line path just a little
        reg.Intersect(gp);
        if (reg.IsEmpty(g)) return false;
    }
    return true;
}

Here is a small test result:

Since Region.IsEmpty is probably not very fast I have prepended the call with a few trivial tests for better speed. For a discussion of performance issues with Region see here. From this I guess one can conclude that testing with a simple rectangle will in fact still be reasonably fast..

For a truely fast test you may need to implement a real clipping method. This looks nice..

But the GDI+ trick with the region has one big advantage over the analytical methods: I will work with any shapes you can put into a GraphicsPath, including circles, ellipes, polygons, all sorts of combinations and also complex tracing paths. And since the Region supports all set operations, your imagination is the limit..

This allows you to test complex shapes of spaceships or monsters; and with a few extra tricks you can even test rotated shapes.

Note that if you go for testing complex shapes you will want to:

• pass in the GraphicsPath
• use its bounding rectangle (gp.GetBounds()) for the first four tests (*)
• remove the other two tests (**) since the bounding rectangle will not work now; in fact they only work with rectangles; I had to remove them for the following ellipse demo.

Here is the same example, simply replacing the rectangle with an ellipse:

Answer 2

Here you go. The original code was in C and i translated to vb.net. The code works with a line and a rectangle.

'//min_clip_x is the distance of the left side of rect
'//min_clip_y is the distance of the upper side of rect
'//max_clip_x is the distance of the right side of rect
'//min_clip_y is the distance of the down side of rect

Private Function Clip_Line(ByVal x1 As Integer, ByVal y1 As Integer, ByVal x2 As Integer, ByVal y2 As Integer,
                             ByVal min_clip_x As Integer, ByVal max_clip_x As Integer, ByVal min_clip_y As Integer,
                             ByVal max_clip_y As Integer) As Boolean

    Const CLIP_CODE_C As Integer = 0
    Const CLIP_CODE_N As Integer = 8
    Const CLIP_CODE_S As Integer = 4
    Const CLIP_CODE_E As Integer = 2
    Const CLIP_CODE_W As Integer = 1
    Const CLIP_CODE_NE As Integer = 10
    Const CLIP_CODE_SE As Integer = 6
    Const CLIP_CODE_NW As Integer = 9
    Const CLIP_CODE_SW As Integer = 5

    Dim p1_code As Integer = 0
    Dim p2_code As Integer = 0
    Dim xc1, yc1, xc2, yc2 As Integer

    xc1 = x1
    yc1 = y1
    xc2 = x2
    yc2 = y2

    '//determine codes for p1 And p2
    If y1 < min_clip_y Then
        p1_code = p1_code Or CLIP_CODE_N
    Else
        If y1 > max_clip_y Then
            p1_code = p1_code Or CLIP_CODE_S
        End If
    End If

    If (x1 < min_clip_x) Then
        p1_code = p1_code Or CLIP_CODE_W
    Else
        If (x1 > max_clip_x) Then
            p1_code = p1_code Or CLIP_CODE_E
        End If
    End If

    If (y2 < min_clip_y) Then
        p2_code = p2_code Or CLIP_CODE_N
    Else
        If (y2 > max_clip_y) Then
            p2_code = p2_code Or CLIP_CODE_S
        End If
    End If

    If (x2 < min_clip_x) Then
        p2_code = p2_code Or CLIP_CODE_W
    Else
        If (x2 > max_clip_x) Then
            p2_code = p2_code Or CLIP_CODE_E
        End If
    End If

    '//try And trivially reject
    If CBool(p1_code And p2_code) Then
        Return False
    End If

    '//test for totally visible, if so leave points untouched
    If (p1_code = 0 And p2_code = 0) Then
        Return True
    End If

    '//determine end clip point for p1
    Select Case p1_code
        Case CLIP_CODE_C
            Exit Select
        Case CLIP_CODE_N
            yc1 = min_clip_y
            xc1 = CInt(x1 + 0.5 + (min_clip_y - y1) * (x2 - x1) / (y2 - y1))

            Exit Select
        Case CLIP_CODE_S
            yc1 = max_clip_y
            xc1 = CInt(x1 + 0.5 + (max_clip_y - y1) * (x2 - x1) / (y2 - y1))

            Exit Select
        Case CLIP_CODE_W
            xc1 = min_clip_x
            yc1 = CInt(y1 + 0.5 + (min_clip_x - x1) * (y2 - y1) / (x2 - x1))

            Exit Select
        Case CLIP_CODE_E
            xc1 = max_clip_x
            yc1 = CInt(y1 + 0.5 + (max_clip_x - x1) * (y2 - y1) / (x2 - x1))

            Exit Select
        Case CLIP_CODE_NE
            '//north hline intersection
            yc1 = min_clip_y
            xc1 = CInt(x1 + 0.5 + (min_clip_y - y1) * (x2 - x1) / (y2 - y1))
            '//test if intersection Is valid,
            '//if so then done, else compute next
            If (xc1 < min_clip_x) Or (xc1 > max_clip_x) Then
                '//east vline intersection
                xc1 = max_clip_x
                yc1 = CInt(y1 + 0.5 + (max_clip_x - x1) * (y2 - y1) / (x2 - x1))
            End If

            Exit Select
        Case CLIP_CODE_SE
            '//south hline intersection
            yc1 = max_clip_y
            xc1 = CInt(x1 + 0.5 + (max_clip_y - y1) * (x2 - x1) / (y2 - y1))
            '//test if intersection Is valid,
            '//if so then done, else compute next
            If (xc1 < min_clip_x) Or (xc1 > max_clip_x) Then
                '//east vline intersection
                xc1 = max_clip_x
                yc1 = CInt(y1 + 0.5 + (max_clip_x - x1) * (y2 - y1) / (x2 - x1))
            End If

            Exit Select
        Case CLIP_CODE_NW
            '//north hline intersection
            yc1 = min_clip_y
            xc1 = CInt(x1 + 0.5 + (min_clip_y - y1) * (x2 - x1) / (y2 - y1))
            '//test if intersection Is valid,
            '//if so then done, else compute next
            If (xc1 < min_clip_x) Or (xc1 > max_clip_x) Then
                xc1 = min_clip_x
                yc1 = CInt(y1 + 0.5 + (min_clip_x - x1) * (y2 - y1) / (x2 - x1))
            End If

            Exit Select
        Case CLIP_CODE_SW
            '//south hline intersection
            yc1 = max_clip_y
            xc1 = CInt(x1 + 0.5 + (max_clip_y - y1) * (x2 - x1) / (y2 - y1))
            '//test if intersection Is valid,
            '//if so then done, else compute next
            If (xc1 < min_clip_x) Or (xc1 > max_clip_x) Then
                xc1 = min_clip_x
                yc1 = CInt(CDbl(y1) + 0.5 + CDbl(min_clip_x - x1) * CDbl(y2 - y1) / CDbl(x2 - x1))
            End If

            Exit Select
        Case Else
            Exit Select
    End Select

    '//determine end clip point for p2
    Select Case p2_code
        Case CLIP_CODE_C
            Exit Select
        Case CLIP_CODE_N
            yc2 = min_clip_y
            xc2 = CInt(x2 + (min_clip_y - y2) * (x1 - x2) / (y1 - y2))

            Exit Select
        Case CLIP_CODE_S
            yc2 = max_clip_y
            xc2 = CInt(x2 + (max_clip_y - y2) * (x1 - x2) / (y1 - y2))

            Exit Select
        Case CLIP_CODE_W
            xc2 = min_clip_x
            yc2 = CInt(y2 + (min_clip_x - x2) * (y1 - y2) / (x1 - x2))

            Exit Select
        Case CLIP_CODE_E
            xc2 = max_clip_x
            yc2 = CInt(y2 + (max_clip_x - x2) * (y1 - y2) / (x1 - x2))

            Exit Select
        Case CLIP_CODE_NE
            '//north hline intersection
            yc2 = min_clip_y
            xc2 = CInt(x2 + 0.5 + (min_clip_y - y2) * (x1 - x2) / (y1 - y2))
            '//test if intersection Is valid,
            '//if so then done, else compute next
            If (xc2 < min_clip_x) Or (xc2 > max_clip_x) Then
                '//east vline intersection
                xc2 = max_clip_x
                yc2 = CInt(y2 + 0.5 + (max_clip_x - x2) * (y1 - y2) / (x1 - x2))
            End If

            Exit Select
        Case CLIP_CODE_SE
            '//south hline intersection
            yc2 = max_clip_y
            xc2 = CInt(x2 + 0.5 + (max_clip_y - y2) * (x1 - x2) / (y1 - y2))
            '//test if intersection Is valid,
            '//if so then done, else compute next
            If (xc2 < min_clip_x) Or (xc2 > max_clip_x) Then
                '//east vline intersection
                xc2 = max_clip_x
                yc2 = CInt(y2 + 0.5 + (max_clip_x - x2) * (y1 - y2) / (x1 - x2))
            End If

            Exit Select
        Case CLIP_CODE_NW
            '//north hline intersection
            yc2 = min_clip_y
            xc2 = CInt(x2 + 0.5 + (min_clip_y - y2) * (x1 - x2) / (y1 - y2))
            '//test if intersection Is valid,
            '//if so then done, else compute next
            If (xc2 < min_clip_x) Or (xc2 > max_clip_x) Then
                xc2 = min_clip_x
                yc2 = CInt(y2 + 0.5 + (min_clip_x - x2) * (y1 - y2) / (x1 - x2))
            End If

            Exit Select
        Case CLIP_CODE_SW
            '//south hline intersection
            yc2 = max_clip_y
            xc2 = CInt(x2 + 0.5 + (max_clip_y - y2) * (x1 - x2) / (y1 - y2))
            '//test if intersection Is valid,
            '//if so then done, else compute next
            If (xc2 < min_clip_x) Or (xc2 > max_clip_x) Then
                xc2 = min_clip_x
                yc2 = CInt(y2 + 0.5 + (min_clip_x - x2) * (y1 - y2) / (x1 - x2))
            End If

            Exit Select
        Case Else
            Exit Select
    End Select

    '//do bounds check
    If (xc1 < min_clip_x) Or (xc1 > max_clip_x) Or (yc1 < min_clip_y) Or (yc1 > max_clip_y) Or
        (xc2 < min_clip_x) Or (xc2 > max_clip_x) Or (yc2 < min_clip_y) Or (yc2 > max_clip_y) Then

        Return False '//no collision
    End If

    Return True '//collision
End Function