Intersection points of line bisector with rectangle

You have the equation for CD (in the form (y - y0) = m(x - x0)) which you can transform into the form y = mx + c. You can also transform it into the form x = (1/m)y - (c/m).

You then simply need to find solutions for when x=0, x=512, y=0, y=512.


We start from the center point C and the direction of AB, D:

C.x = (A.x+B.x) / 2
C.y = (A.y+B.y) / 2
D.x = (A.x-B.x) / 2
D.y = (A.y-B.y) / 2

then if P is a point on the line, CP must be perpendicular to D. The equation of the line is:

DotProduct(P-C, D) = 0

or

CD = C.x*D.x + C.y*D.y
P.x * D.x + P.y * D.y - CD = 0

for each of the four edges of the square, we have an equation:

P.x=0 -> P.y = CD / D.y
P.y=0 -> P.x = CD / D.x
P.x=512 -> P.y = (CD - 512*D.x) / D.y
P.y=512 -> P.x = (CD - 512*D.y) / D.x

Except for degenerate cases where 2 points coincide, only 2 of these 4 points will have both P.x and P.y between 0 and 512. You'll also have to check for the special cases D.x = 0 or D.y = 0.


The following code should do the trick:

typedef struct { float x; float y; } Point;
typedef struct { Point point[2]; } Line;
typedef struct { Point origin; float width; float height; } Rect;
typedef struct { Point origin; Point direction; } Vector;

Point SolveVectorForX(Vector vector, float x)
{
    Point solution;
    solution.x = x;
    solution.y = vector.origin.y +
        (x - vector.origin.x)*vector.direction.y/vector.direction.x;
    return solution;
}

Point SolveVectorForY(Vector vector, float y)
{
    Point solution;
    solution.x = vector.origin.x +
        (y - vector.origin.y)*vector.direction.x/vector.direction.y;
    solution.y = y;
    return solution;
}

Line FindLineBisectorIntersectionWithRect(Rect rect, Line AB)
{
    Point A = AB.point[0];
    Point B = AB.point[1];
    int pointCount = 0;
    int testEdge = 0;
    Line result;
    Vector CD;

    // CD.origin = midpoint of line AB
    CD.origin.x = (A.x + B.x)/2.0;
    CD.origin.y = (A.y + B.y)/2.0;

    // CD.direction = negative inverse of AB.direction (perpendicular to AB)
    CD.direction.x = (B.y - A.y);
    CD.direction.y = (A.x - B.x);

    // for each edge of the rectangle, check:
    // 1. that an intersection with CD is possible (avoid division by zero)
    // 2. that the intersection point falls within the endpoints of the edge
    // 3. if both check out, use that point as one of the solution points
    while ((++testEdge <= 4) && (pointCount < 2))
    {
        Point point;

        switch (testEdge)
        {
            case 1: // check minimum x edge of rect
                if (CD.direction.x == 0) { continue; }
                point = SolveVectorForX(CD, rect.origin.x);
                if (point.y < rect.origin.y) { continue; }
                if (point.y > (rect.origin.y + rect.height)) { continue; }
                break;

            case 2: // check maximum x edge of rect
                if (CD.direction.x == 0) { continue; }
                point = SolveVectorForX(CD, rect.origin.x + rect.width);
                if (point.y < rect.origin.y) { continue; }
                if (point.y > (rect.origin.y + rect.height)) { continue; }
                break;

            case 3: // check minimum y edge of rect
                if (CD.direction.y == 0) { continue; }
                point = SolveVectorForY(CD, rect.origin.y);
                if (point.x < rect.origin.x) { continue; }
                if (point.x > (rect.origin.x + rect.width)) { continue; }
                break;

            case 4: // check maximum y edge of rect
                if (CD.direction.y == 0) { continue; }
                point = SolveVectorForY(CD, rect.origin.y + rect.height);
                if (point.x < rect.origin.x) { continue; }
                if (point.x > (rect.origin.x + rect.width)) { continue; }
                break;
        };

        // if we made it here, this point is one of the solution points
        result.point[pointCount++] = point;
    }

    // pointCount should always be 2
    assert(pointCount == 2);

    return result;
}