Finding Line segment-Rectangle intersection point

Question

Simply put, I have:

• A viewport rectangle where (0,0) is the bottom-left corner, (1,1) is the top-right and (0.5,0.5) is the centre of the screen.
• A point (a,b) which is outside of the rectangle.

This is in viewport coordinates so +X is right, +Y is up on the screen.

And I need a function which takes these parameters and returns the point on the edge of the rectangle where the line (between the centre of the rectangle (0.5,0.5) and the point (a,b)) intersects it.

I know how to do this on paper with given coordinates but I just can't figure it out when it comes down to code. Also, I realise questions like this have been addressed in different threads - but I can't find a simple input to output function anywhere.

I'm doing this in the Unity3D engine so preferably in Javascript but any language or pseudocode would be a great help as I can probably hand convert it.

EDIT To clarify, I'm looking for something like:

function IntersectFromViewportCenter(x : float, y : float) {
    ...
    return Point(x1, y1);
}

Where (x,y) is the point outside of the circle and (x1,y1) is the intersection point.

Thanks

Answer 1

Shift all system to be centered at point (0,0). Calc intersection of ray from origin to (shifted) point (x',y') with box (-1,-1)-(1,1). Scale and shift back. I did not consider trivial case with point inside the box ( is it needed?)

x = x - 0.5
y = y - 0.5
if Abs(x) >= Abs(y) then  //vertical box edge
  y1 = y/x  //care with case both y and x = 0
  x1 = Sign(x) //+-1
else   // horizontal edge
  x1 = x/y
  y1 = Sign(y)

x1 = 0.5*x1 + 0.5
y1 = 0.5*y1 + 0.5

Answer 2

MBo has the right idea. Here's a way to implement in in Unity. I don't think UnityScript is worth using – in particular, it doesn't support extension methods – so you really should switch languages. (Also, Unity is actually not named Unity3D.)

This script can go anywhere in the Project:

using UnityEngine;

public static class UnityEngineExtensions {

public static Vector2 Abs(this Vector2 vector) {
    for (int i = 0; i < 2; ++i) vector[i] = Mathf.Abs(vector[i]);
    return vector;
}   

public static Vector2 DividedBy(this Vector2 vector, Vector2 divisor) {
    for (int i = 0; i < 2; ++i) vector[i] /= divisor[i];
    return vector;
}

public static Vector2 Max(this Rect rect) {
    return new Vector2(rect.xMax, rect.yMax);
}

public static Vector2 IntersectionWithRayFromCenter(this Rect rect, Vector2 pointOnRay) {
    Vector2 pointOnRay_local = pointOnRay - rect.center;
    Vector2 edgeToRayRatios = (rect.Max() - rect.center).DividedBy(pointOnRay_local.Abs());
    return (edgeToRayRatios.x < edgeToRayRatios.y) ?
        new Vector2(pointOnRay_local.x > 0 ? rect.xMax : rect.xMin, 
            pointOnRay_local.y * edgeToRayRatios.x + rect.center.y) :
        new Vector2(pointOnRay_local.x * edgeToRayRatios.y + rect.center.x, 
            pointOnRay_local.y > 0 ? rect.yMax : rect.yMin);
}

}

Attach this other script to a Game Object, and set its variables in the Inspector.

#pragma warning disable 0649
using System;
using UnityEngine;

public class VisualizeRectIntersectionWithRayFromCenter : MonoBehaviour {

[SerializeField] Rect rect;
[SerializeField] Vector2 point;

[Serializable] class Colors {
    public Color rect, point, intersection;
} [SerializeField] Colors colors;

void OnDrawGizmos() {
    Gizmos.color = colors.rect;
    Vector2[] corners = {new Vector2(rect.xMin, rect.yMin), new Vector2(rect.xMin, rect.yMax),
        rect.Max(), new Vector2(rect.xMax, rect.yMin)};
    int i = 0;
    while (i < 3) Gizmos.DrawLine(corners[i], corners[++i]);
    Gizmos.DrawLine(corners[3], corners[0]);

    Gizmos.color = colors.point;
    Gizmos.DrawLine(rect.center, point);

    Gizmos.color = colors.intersection;
    Gizmos.DrawLine(rect.center, rect.IntersectionWithRayFromCenter(pointOnRay: point));
}

}

Answer 3

Since some general Line/Rect approaches have been provided, here is an approach that is optimized to avoid Raycasts in trivial cases (completely inside or completely outside the Rect): https://gist.github.com/JohannesMP/50dad3175bf2925df508b642091e41c4

It also efficiently provides both the entry and exit point (necessary in my use case):

Here is a basic overview of this approach:

1. Divide the area around the rect into Sectors as follows (Where S4 is the rect itself):

   S0| S1 |S2
   --+----+--   ^
   S3| S4 |S5   |
   --+----+--   y
   S6| S7 |S8    x-->
   

2. Given the sectors where the line segment begins and ends, we know what raycasts need to be performed (Ex: S0-S2 never needs to raycast, while S4-S1 only needs to raycast the top edge, etc)

3. Pre-compute this data and store it in a small 9x9 static array. We are basically using a bit of static memory to avoid conditional checks.
4. At runtime find the Sector that the start and end points of the line occupy, and use the result to Raycast only the necessary edges of the Rect.

Additionally you can simplify the raycast into one dimension if you handle vertical and horizontal lines separately.

---

In my personal use case (lots of line segments, where the vast majority are either completely inside or completely outside the Rect) this approach is faster than the general case, since Raycasts are only performed when necessary.

Answer 4

bool LineRectIntersection(Vector2 lineStartPoint, Vector2 lineEndPoint, Rect rectangle, ref double resultX, ref double resultY)
{
    Vector2 minXLinePoint = (lineStartPoint.x <= lineEndPoint.x) ? (lineStartPoint) : (lineEndPoint);
    Vector2 maxXLinePoint = (lineStartPoint.x <= lineEndPoint.x) ? (lineEndPoint) : (lineStartPoint);
    Vector2 minYLinePoint = (lineStartPoint.y <= lineEndPoint.y) ? (lineStartPoint) : (lineEndPoint);
    Vector2 maxYLinePoint = (lineStartPoint.y <= lineEndPoint.y) ? (lineEndPoint) : (lineStartPoint);

    double rectMaxX = rectangle.xMax;
    double rectMinX = rectangle.xMin;
    double rectMaxY = rectangle.yMax;
    double rectMinY = rectangle.yMin;

    if (minXLinePoint.x <= rectMaxX && rectMaxX <= maxXLinePoint.x)
    {
        double m = (maxXLinePoint.y - minXLinePoint.y) / (maxXLinePoint.x - minXLinePoint.x);

        double intersectionY = ((rectMaxX - ((double)minXLinePoint.x)) * m) + ((double)minXLinePoint.y);

        if(minYLinePoint.y <= intersectionY && intersectionY <= maxYLinePoint.y)
        {
            resultX = rectMaxX;
            resultY = intersectionY;

            return true;
        }
    }

    if (minXLinePoint.x <= rectMinX && rectMinX <= maxXLinePoint.x)
    {
        double m = (maxXLinePoint.y - minXLinePoint.y) / (maxXLinePoint.x - minXLinePoint.x);

        double intersectionY = ((rectMinX - ((double)minXLinePoint.x)) * m) + ((double)minXLinePoint.y);

        if (minYLinePoint.y <= intersectionY && intersectionY <= maxYLinePoint.y)
        {
            resultX = rectMinX;
            resultY = intersectionY;

            return true;
        }
    }

    if (minYLinePoint.y <= rectMaxY && rectMaxY <= maxYLinePoint.y)
    {
        double rm = (maxYLinePoint.x - minYLinePoint.x) / (maxYLinePoint.y - minYLinePoint.y);

        double intersectionX = ((rectMaxY - ((double)minYLinePoint.y)) * rm) + ((double)minYLinePoint.x);

        if (minXLinePoint.x <= intersectionX && intersectionX <= maxXLinePoint.x)
        {
            resultX = intersectionX;
            resultY = rectMaxY;

            return true;
        }
    }

    if (minYLinePoint.y <= rectMinY && rectMinY <= maxYLinePoint.y)
    {
        double rm = (maxYLinePoint.x - minYLinePoint.x) / (maxYLinePoint.y - minYLinePoint.y);

        double intersectionX = ((rectMinY - ((double)minYLinePoint.y)) * rm) + ((double)minYLinePoint.x);

        if (minXLinePoint.x <= intersectionX && intersectionX <= maxXLinePoint.x)
        {
            resultX = intersectionX;
            resultY = rectMinY;

            return true;
        }
    }

    return false;
}

Answer 5

@chakmeshma, your solution is almost correct, but you must also check whether the intersection point is within the rect to avoid border cases:

private static bool LineRectIntersection(Vector2 lineStartPoint, Vector2 lineEndPoint, Rect rectangle, ref Vector2 result)
    {
        Vector2 minXLinePoint = lineStartPoint.x <= lineEndPoint.x ? lineStartPoint : lineEndPoint;
        Vector2 maxXLinePoint = lineStartPoint.x <= lineEndPoint.x ? lineEndPoint : lineStartPoint;
        Vector2 minYLinePoint = lineStartPoint.y <= lineEndPoint.y ? lineStartPoint : lineEndPoint;
        Vector2 maxYLinePoint = lineStartPoint.y <= lineEndPoint.y ? lineEndPoint : lineStartPoint;

        double rectMaxX = rectangle.xMax;
        double rectMinX = rectangle.xMin;
        double rectMaxY = rectangle.yMax;
        double rectMinY = rectangle.yMin;

        if (minXLinePoint.x <= rectMaxX && rectMaxX <= maxXLinePoint.x)
        {
            double m = (maxXLinePoint.y - minXLinePoint.y) / (maxXLinePoint.x - minXLinePoint.x);

            double intersectionY = ((rectMaxX - minXLinePoint.x) * m) + minXLinePoint.y;

            if (minYLinePoint.y <= intersectionY && intersectionY <= maxYLinePoint.y
                && rectMinY <= intersectionY && intersectionY <= rectMaxY)
            {
                result = new Vector2((float)rectMaxX, (float)intersectionY);

                return true;
            }
        }

        if (minXLinePoint.x <= rectMinX && rectMinX <= maxXLinePoint.x)
        {
            double m = (maxXLinePoint.y - minXLinePoint.y) / (maxXLinePoint.x - minXLinePoint.x);

            double intersectionY = ((rectMinX - minXLinePoint.x) * m) + minXLinePoint.y;

            if (minYLinePoint.y <= intersectionY && intersectionY <= maxYLinePoint.y
                && rectMinY <= intersectionY && intersectionY <= rectMaxY)
            {
                result = new Vector2((float)rectMinX, (float)intersectionY);

                return true;
            }
        }

        if (minYLinePoint.y <= rectMaxY && rectMaxY <= maxYLinePoint.y)
        {
            double rm = (maxYLinePoint.x - minYLinePoint.x) / (maxYLinePoint.y - minYLinePoint.y);

            double intersectionX = ((rectMaxY - minYLinePoint.y) * rm) + minYLinePoint.x;

            if (minXLinePoint.x <= intersectionX && intersectionX <= maxXLinePoint.x
                && rectMinX <= intersectionX && intersectionX <= rectMaxX)
            {
                result = new Vector2((float)intersectionX, (float)rectMaxY);

                return true;
            }
        }

        if (minYLinePoint.y <= rectMinY && rectMinY <= maxYLinePoint.y)
        {
            double rm = (maxYLinePoint.x - minYLinePoint.x) / (maxYLinePoint.y - minYLinePoint.y);

            double intersectionX = ((rectMinY - minYLinePoint.y) * rm) + minYLinePoint.x;

            if (minXLinePoint.x <= intersectionX && intersectionX <= maxXLinePoint.x
                && rectMinX <= intersectionX && intersectionX <= rectMaxX)
            {
                result = new Vector2((float)intersectionX, (float)rectMinY);

                return true;
            }
        }

        return false;
    }
}