Get intersection point of rectangle and line

Question

I need get intersection point of rectangle and line. I have point B inside rectangle(center of rectangle) and have point A outside. And i need to find point C on one of rectangle borders. Also I get width and height of rectangle.

All this will be WPF application, so if any build in functions i will be very happy.

Answer 1

Hope It works 100%

I am also had this same problem. So after two days of hard effort finally I created this method,

Main method,

    // Tuple<entryPoint, exitPoint, lineStatus>
    private Tuple<Point, Point, Line> GetIntersectionPoint(Point a, Point b, Rectangle rect)
    {
        if (IsWithinRectangle(a, rect) && IsWithinRectangle(b, rect))
        {
            // Can't set null to Point that's why I am returning just empty object
            return new Tuple<Point, Point, Line>(new Point(), new Point(), Line.InsideTheRectangle);
        }
        else if (!IsWithinRectangle(a, rect) && !IsWithinRectangle(b, rect))
        {
            if (!LineIntersectsRectangle(a, b, rect))
            {
                // Can't set null to Point that's why I am returning just empty object
                return new Tuple<Point, Point, Line>(new Point(), new Point(), Line.NoIntersection);
            }

            Point entryPoint = new Point();
            Point exitPoint = new Point();

            bool entryPointFound = false;

            // Top Line of Chart Area
            if (LineIntersectsLine(a, b, new Point(0, 0), new Point(rect.Width, 0)))
            {
                entryPoint = GetPointFromYValue(a, b, 0);
                entryPointFound = true;
            }
            // Right Line of Chart Area
            if (LineIntersectsLine(a, b, new Point(rect.Width, 0), new Point(rect.Width, rect.Height)))
            {
                if (entryPointFound)
                    exitPoint = GetPointFromXValue(a, b, rect.Width);
                else
                {
                    entryPoint = GetPointFromXValue(a, b, rect.Width);
                    entryPointFound = true;
                }
            }
            // Bottom Line of Chart
            if (LineIntersectsLine(a, b, new Point(0, rect.Height), new Point(rect.Width, rect.Height)))
            {
                if (entryPointFound)
                    exitPoint = GetPointFromYValue(a, b, rect.Height);
                else
                {
                    entryPoint = GetPointFromYValue(a, b, rect.Height);
                }
            }
            // Left Line of Chart
            if (LineIntersectsLine(a, b, new Point(0, 0), new Point(0, rect.Height)))
            {
                exitPoint = GetPointFromXValue(a, b, 0);
            }

            return new Tuple<Point, Point, Line>(entryPoint, exitPoint, Line.EntryExit);
        }
        else
        {
            Point entryPoint = GetEntryIntersectionPoint(rect, a, b);
            return new Tuple<Point, Point, Line>(entryPoint, new Point(), Line.Entry);
        }
    }

Supporting methods,

    enum Line
    {
        // Inside the Rectangle so No Intersection Point(Both Entry Point and Exit Point will be Null)
        InsideTheRectangle,

        // One Point Inside the Rectangle another Point Outside the Rectangle. So it has only Entry Point
        Entry,

        // Both Point Outside the Rectangle but Intersecting. So It has both Entry and Exit Point
        EntryExit,

        // Both Point Outside the Rectangle and not Intersecting. So doesn't has both Entry and Exit Point
        NoIntersection
    }

    private Point GetEntryIntersectionPoint(Rectangle rect, Point a, Point b)
    {
        // For top line of the rectangle
        if (LineIntersectsLine(new Point(0, 0), new Point(rect.Width, 0), a, b))
        {
            return GetPointFromYValue(a, b, 0);
        }
        // For right side line of the rectangle
        else if (LineIntersectsLine(new Point(rect.Width, 0), new Point(rect.Width, rect.Height), a, b))
        {
            return GetPointFromXValue(a, b, rect.Width);
        }
        // For bottom line of the rectangle
        else if (LineIntersectsLine(new Point(0, rect.Height), new Point(rect.Width, rect.Height), a, b))
        {
            return GetPointFromYValue(a, b, rect.Height);
        }
        // For left side line of the rectangle
        else
        {
            return GetPointFromXValue(a, b, 0);
        }
    }

    public bool LineIntersectsRectangle(Point p1, Point p2, Rectangle r)
    {
        return LineIntersectsLine(p1, p2, new Point(r.X, r.Y), new Point(r.X + r.Width, r.Y)) ||
               LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y), new Point(r.X + r.Width, r.Y + r.Height)) ||
               LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y + r.Height), new Point(r.X, r.Y + r.Height)) ||
               LineIntersectsLine(p1, p2, new Point(r.X, r.Y + r.Height), new Point(r.X, r.Y)) ||
               (r.Contains(p1) && r.Contains(p2));
    }

    private bool LineIntersectsLine(Point l1p1, Point l1p2, Point l2p1, Point l2p2)
    {
        float q = (l1p1.Y - l2p1.Y) * (l2p2.X - l2p1.X) - (l1p1.X - l2p1.X) * (l2p2.Y - l2p1.Y);
        float d = (l1p2.X - l1p1.X) * (l2p2.Y - l2p1.Y) - (l1p2.Y - l1p1.Y) * (l2p2.X - l2p1.X);

        if (d == 0)
        {
            return false;
        }

        float r = q / d;

        q = (l1p1.Y - l2p1.Y) * (l1p2.X - l1p1.X) - (l1p1.X - l2p1.X) * (l1p2.Y - l1p1.Y);
        float s = q / d;

        if (r < 0 || r > 1 || s < 0 || s > 1)
        {
            return false;
        }

        return true;
    }

    // For Large values, processing with integer is not working properly
    // So I here I am dealing only with double for high accuracy
    private Point GetPointFromYValue(Point a, Point b, double y)
    {
        double x1 = a.X, x2 = b.X, y1 = a.Y, y2 = b.Y;
        double x = (((y - y1) * (x2 - x1)) / (y2 - y1)) + x1;
        return new Point((int)x, (int)y);
    }

    // For Large values, processing with integer is not working properly
    // So here I am dealing only with double for high accuracy
    private Point GetPointFromXValue(Point a, Point b, double x)
    {
        double x1 = a.X, x2 = b.X, y1 = a.Y, y2 = b.Y;
        double y = (((x - x1) * (y2 - y1)) / (x2 - x1)) + y1;
        return new Point((int)x, (int)y);
    }

    // rect.Contains(point) is not working properly in some cases.
    // So here I created my own method
    private bool IsWithinRectangle(Point a, Rectangle rect)
    {
        return a.X >= rect.X && a.X <= rect.X + rect.Width && a.Y >= rect.Y && a.Y <= rect.Y + rect.Height;
    }

Answer 2

This is basic math solving line-line intersection, check out topcoder for a tutorial:

Line-Line Intersection One of the most common tasks you will find in geometry problems is line intersection. Despite the fact that it is so common, a lot of coders still have trouble with it. The first question is, what form are we given our lines in, and what form would we like them in? Ideally, each of our lines will be in the form Ax+By=C, where A, B and C are the numbers which define the line. However, we are rarely given lines in this format, but we can easily generate such an equation from two points. Say we are given two different points, (x1, y1) and (x2, y2), and want to find A, B and C for the equation above. We can do so by setting A = y2-y1 B = x1-x2 C = A*x1+B*y1

Answer 3

Solution for C#, WPF:

 /// <summary>
    /// Get Intersection point
    /// </summary>
    /// <param name="a1">a1 is line1 start</param>
    /// <param name="a2">a2 is line1 end</param>
    /// <param name="b1">b1 is line2 start</param>
    /// <param name="b2">b2 is line2 end</param>
    /// <returns></returns>
    public static Vector? Intersects(Vector a1, Vector a2, Vector b1, Vector b2)
    {
        Vector b = a2 - a1;
        Vector d = b2 - b1;
        var 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 null;

        Vector c = b1 - a1;
        var t = (c.X * d.Y - c.Y * d.X) / bDotDPerp;
        if (t < 0 || t > 1)
            {
            return null;
        }

        var u = (c.X * b.Y - c.Y * b.X) / bDotDPerp;
        if (u < 0 || u > 1)
        {
            return null;
        }

        return a1 + t * b;
    }

Edit Found Link to SO question where the answer above comes from.