Line intersection with AABB Rectangle?

by

I would recommend simply doing a line-segment-line-segment intersection check on each line segment (edge) that makes up the rectangle. Here is a line segment intersection detection algorithm I wrote ages ago, dredged up from one of my old XNA projects:

// a1 is line1 start, a2 is line1 end, b1 is line2 start, b2 is line2 end
static bool Intersects(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersection)
{
    intersection = Vector2.Zero;

    Vector2 b = a2 - a1;
    Vector2 d = b2 - b1;
    float bDotDPerp = b.X * d.Y - b.Y * d.X;

    // if b dot d == 0, it means the lines are parallel so have infinite intersection points
    if (bDotDPerp == 0)
        return false;

    Vector2 c = b1 - a1;
    float t = (c.X * d.Y - c.Y * d.X) / bDotDPerp;
    if (t < 0 || t > 1)
        return false;

    float u = (c.X * b.Y - c.Y * b.X) / bDotDPerp;
    if (u < 0 || u > 1)
        return false;

    intersection = a1 + t * b;

    return true;
}

I will leave inputting each edge into the above method and collecting the results as an exercise to the reader 🙂

Edit 1 year later now I’ve gone to university and done a Graphics course:

Take a look at the Cohen–Sutherland algorithm to do this efficiently when you have a large set of lines where most do not intersect the rectangle. It uses a 9 segment grid and you place each endpoint of the line in a region of said grid:

grid

Using this we can tell if there will not be any line intersections:

grid with lines

For example here CD will not intersect the rectangle (shown in red in the first image) as both C and D are in the top row and neither will AB. For the ones where the line may intersect the the rectangle we have to try the line-line intersections.

They way the sections are numbered/labelled allows us to simply do x AND y != 0 (where x and y are the labels of the sections for each of the line’s endpoints) to determine if there will not be an intersection.

Using this method means we have to many, many fewer line-line intersections which speeds up the whole thing massively.

More Related Contents:

  1. How to add a char every X specific char in C# [closed]
  2. Reading a file line by line in C#
  3. Intersect Two Lists in C#
  4. How to draw an updating line
  5. How to intersect two polygons?
  6. How to Draw on Zoomable Image in C# windows Forms
  7. How can I tell if a point belongs to a certain line?
  8. All cases covered Bresenham’s line-algorithm [closed]
  9. Intersect with a custom IEqualityComparer using Linq
  10. Convert string[] to Array
  11. I see an error CS8070 . How i can fix the error?
  12. Winforms Double Buffering
  13. ASP.NET Core Web API exception handling
  14. Make first letter of a string upper case (with maximum performance)
  15. Efficient way to remove ALL whitespace from String?
  16. Using StringWriter for XML Serialization
  17. What does “where T : class, new()” mean?
  18. Custom method names in ASP.NET Web API
  19. ASP.NET Core 2.0 LDAP Active Directory Authentication
  20. How to round up value C# to the nearest integer?
  21. Capture username with log4net
  22. ASP.NET MVC Authorization
  23. How to achieve remove_if functionality in .NET ConcurrentDictionary
  24. How accurate is Thread.Sleep(TimeSpan)?
  25. Regex to match a word with + (plus) signs
  26. How do you do transition effects using the Frame control in WPF?
  27. How to pass a table as parameter to MySqlCommand?
  28. Reportviewer tool missing in visual studio 2017 RC
  29. .Net’s Directory Services throws a strange exception
  30. How to Convert string “07:35” (HH:MM) to TimeSpan

Leave a Comment