GML how to Find intersection in rectangle

Maa2007

Member


I have a box with varying width and height. I have a point (x1, y1) that inside of said box. And lastly: I have a final point (x2, y2) that exists somewhere outside the box.
If a line were to exist between these two points, how would I find the (x, y) coordinate of the point where this line intersects the border of this box (the point seen in red above).
 

CloseRange

Member
well there might be an easier way but here is how I do it. Back to algebra class :p
firstly you must assume the rectangle isn't rotated, second assume it IS a rectangle.
then make an object called 'oPoint' with nothing in it (this is just so i can return the oPoint object and set its x and y to the coords)
here is a function for it:
Code:
/// calcXY(rectX1, rectY1, rectX2, rectY2, x1, y1, x2, y2);
var rx1 = argument[0];
var ry1 = argument[1];
var rx2 = argument[2];
var ry2 = argument[3];
var x1 = argument[4];
var y1 = argument[5];
var x2 = argument[6];
var y2 = argument[7];

var p;
// forumla for a line is    mx + b    so:
var m = (y2-y1) / (x2-x1); // slope is rise over run
var b = y1 - (m * x1); // with y = mx + b i just solve for b

// Now we go through all 4 'walls' of the rectagle, solve for the x or y of that 'wall' and see if its in bounds (if it is then it's the correct coords)
// ---------- RIGHT WALL
var dy = m * rx2 + b;
if( dy > ry1 && dy < ry2 && x2 > rx2) return instance_create(rx2, dy, oPoint);
// ---------- LEFT WALL
var dy = m * rx1 + b;
if( dy > ry1 && dy < ry2 && x2 < rx1) return instance_create(rx1, dy, oPoint);
// ---------- TOP WALL ( for these walls we solve for x instead so we have the formula x = (y-b)/m
// we also have to do something special if the slope is infinite
var dx = (ry1 - b) / m;
if( x1-x2 == 0 ) dx = x2;
if( dx > rx1 && dx < rx2 && y2 < ry1) return instance_create(dx, ry1, oPoint);
// ---------- BOTTOM WALL
var dx = (ry2 - b) / m;
if( x1-x2 == 0 ) dx = x2;
if( dx > rx1 && dx < rx2 && y2 > ry2) return instance_create(dx, ry2, oPoint);
return instance_create(-1, -1, oPoint);
that should work.... hopefully.... I did just write it and didn't test it :p

to use:
Code:
draw_rectangle(100, 100, 200, 200, true);
draw_line(150, 150, mouse_x, mouse_y);
var p = calcXY(100, 100, 200, 200, 150, 150, mouse_x, mouse_y);
draw_circle(p.x, p.y, 16, false);
instance_destroy(p);
that instance_destroy is important after you are done with the coords otherwise you will end up creating way too many objects

EDIT:
btw it will return -1, -1 if there is no valid point
 
Last edited:
D

dannyjenn

Guest
A less efficient but also less mathematical approach (perhaps easier / more intuitive) would be to simply start on (x1,y1) and then gradually move along the line until you are no longer inside the rectangle. Wherever you end up is (near) the point of intersection. (I believe this is basically a kind of ray casting?)

Code (haven't tested any of this):
Code:
#macro SMALL_AMOUNT 1 // <-- This can be any number above 0. Smaller numbers result in greater accuracy but also slow the loop.

var theta = point_direction(x1,y1,x2,y2); // Begin by getting the angle between (x1,y1) and (x2,y2)

// Then we are going to start at (x1,y1)...
var temp_x = x1;
var temp_y = y1;

// ... And we will gradually move forward in the desired direction until we are no longer inside the rectangle.
while(true){
    // If we are outside the rectangle, we can stop:
    if((temp_x>=rectangle_right_bound)||(temp_x<rectangle_left_bound)||(temp_y>=rectangle_bottom_bound)||(temp_y<rectangle_top_bound)){ // <-- If you modify this if statement, you could make this same code work for pretty much any 2D shape
        break;
    }
    // Otherwise, we move forward by a SMALL_AMOUNT.
    temp_x += lengthdir_x(SMALL_AMOUNT,theta);
    temp_y += lengthdir_y(SMALL_AMOUNT,theta);
}

// Point of intersection:
x_at_interesction = temp_x;
y_at_intersection = temp_y;
Note: This only gets an approximation. (Strictly speaking, what you'll end up with is a point inside the rectangle, but within SMALL_AMOUNT units of the point of intersection.)
 
Last edited by a moderator:

CloseRange

Member
A less efficient but also less mathematical approach (perhaps easier / more intuitive) would be to simply start on (x1,y1) and then gradually move along the line until you are no longer inside the rectangle. Wherever you end up is (near) the point of intersection. (I believe this is basically a kind of ray casting?)

Code (haven't tested any of this):
Code:
#macro SMALL_AMOUNT 1 // <-- This can be any number above 0. Smaller numbers result in greater accuracy but also slow the loop.

var theta = point_direction(x1,y1,x2,y2); // Begin by getting the angle between (x1,y1) and (x2,y2)

// Then we are going to start at (x1,y1)...
var temp_x = x1;
var temp_y = y1;

// ... And we will gradually move forward in the desired direction until we are no longer inside the rectangle.
while(true){
    // If we are outside the rectangle, we can stop:
    if((temp_x>=rectangle_right_bound)||(temp_x<rectangle_left_bound)||(temp_y>=rectangle_bottom_bound)||(temp_y<rectangle_top_bound)){ // <-- If you modify this if statement, you could make this same code work for pretty much any 2D shape
        break;
    }
    // Otherwise, we move forward by a SMALL_AMOUNT.
    temp_x += lengthdir_x(SMALL_AMOUNT,theta);
    temp_y += lengthdir_y(SMALL_AMOUNT,theta);
}

// Point of intersection:
x_at_interesction = temp_x;
y_at_intersection = temp_y;
Note: This only gets an approximation. (Strictly speaking, what you'll end up with is a point inside the rectangle, but within SMALL_AMOUNT units of the point of intersection.)
This method isn't totally farfetched as it's (close, they do it better) how calculators find points of intersections of 2 lines. Using a method of approximation. Approximating a result is also 100% alright, it's the full basis behind calculus so why not.

My suggestion though is instead of starting at 0 and increment by a small amount until you hit the target, to use a calculators method (idk the exact name but i call it splicing)
You start at the start and check if its in the rectangle (if not then there ain't a solution) . If it is go to the midpoint of the line and check if it's in the rectangle. If it isn't go to the left midpoint (halfway from the start midpoint. Lets call this moving left). If it WAS in the rectangle still go to the right midpoint (halfway from the midpoint to the right side. Call this moving right)
from the new midpoints check if its in the rectangle, if it is move right, otherwise move left.

At the start you set some value like 100. And then do this checking and moving left/right 100 times.
This will approximate the value as well but guarantee we never exceed 100 checks and will probobly even be more accurate than the method you described.
For this small task of getting a rectangle point though, i'd still recommend using math.
 
The first code segment is for a rectangle which is not rotated. See second code segment for a solution involving rotated rectangles.

Both of these solutions assume the line's start point is NOT within the rectangle. If the start piont can be inside the rectangle, then the correct solution can be unclear. If you just want to begin at the start point and go in the direction of the line until you hit one of the sides of the rectangle, then what you want to do is reject negative time solutions by adding this just after the _t5 computation:
if (_t4 < 0) { _t4 = _t5; }

_sx,_sy is the start of the line. _dx, _dy is its direction, which can just be its end point minus its start point. Note: if line's direction is end minus start points, then _t > 1 means the intercept point is not within the line segment.

Code:
    if (_dx == 0) {
        var _t0 =  10000000000000000000000;
        var _t1 = -10000000000000000000000;
    } else {
        var _t0 = (_left - _sx) / _dx;
        var _t1 = (_right - _sx) / _dx;
    }
    if (_dy == 0) {
        var _t2 =  10000000000000000000000;
        var _t3 = -10000000000000000000000;
    } else {
        var _t2 = (_top - _sy) / _dy;
        var _t3 = (_bottom - _sy) / _dy;
    }
    var _t4 = max(min(_t0, _t1), min( _t2, _t3 ) );
    var _t5 = min(max(_t0, _t1), max( _t2, _t3 ) );
    if (_t5 < 0 || _t4 > _t5) {
        _t = -1; //no collision
    } else {
        _t = _t4;  //intercept time
        ///collision point:
        intercept_x = _sx + _dx * _t;
        intercept_y = _sy + _dy * _t;
    }
--------------
However, if the rectangle is rotated, then you have to take that into account. Here, I'm assuming the rectangle is based on an instance sprite. c, s are dcos(image_angle) and dsin(image_angle), or in other words, the cosine and sine of the rectangle's orientation angle. x,y is the origin of the instance representing the rectangle. The width and height of the rectangle are sprite_width and sprite_height. -sprite_xoffset, -sprite_yoffset is the location of what would be the top-left vertex of the rectangle in the rectangle's space, i.e., if the rectangle was not rotated and if it was located at 0,0.

Code:
var _sx1 = (_sx-x) * c + (_sy-y) * -s + sprite_xoffset;
var _sy1 = (_sx-x) * s + (_sy-y) *  c + sprite_yoffset;
var _dx1 = _dx * c + _dy * -s;
var _dy1 = _dx * s + _dy *  c;
if (_dx1 == 0) {
    var _t0 =  10000000000000000000000;
    var _t1 = -10000000000000000000000;
} else {
    var _t0 = (0-_sx1) / _dx1;
    var _t1 = (sprite_width - _sx1) / _dx1;
}
if (_dy1 == 0) {
    var _t2 =  10000000000000000000000;
    var _t3 = -10000000000000000000000;
} else {
    var _t2 = (0-_sy1) / _dy1;
    var _t3 = (sprite_height - _sy1) / _dy1;
}
var _t4 = max(min(_t0, _t1), min( _t2, _t3 ) );
var _t5 = min(max(_t0, _t1), max( _t2, _t3 ) );
if (_t5 < 0 || _t4 > _t5) {
    _t = -1; //no collision
} else {
    _t = _t4;  //intercept time
    //intercept location:
    intercept_x = _sx + _dx * _t;
    intercept_y = _sy + _dy * _t;
}
 
Last edited:

TheSnidr

Heavy metal viking dentist
GMC Elder
Here's a general exact solution to your problem, as long as the block isn't rotated

Code:
/// @description cast_ray_rectangle(rectX, rectY, rectWidth, rectHeight, x1, y1, x2, y2)
/// @param rectX
/// @param rectY
/// @param rectWidth
/// @param rectHeight
/// @param x1
/// @param y1
/// @param x2
/// @param y2
/*
    Finds the intersection between a line segment going from [x1, y1] to [x2, y2], and a rectangle
    Returns the intersection as an array of the following format:
        [x, y]

    Script made by TheSnidr 2019
*/
var bX, bY, bW, bH;
bX = argument0;
bY = argument1;
bW = argument2;
bH = argument3;

//Convert from world coordinates to rectangle normalized coordinates
var bx1, by1;
bx1 = (argument4 - bX) * 2 / bW;
by1 = (argument5 - bY) * 2 / bH;

var bx2, by2;
bx2 = (argument6 - bX) * 2 / bW;
by2 = (argument7 - bY) * 2 / bH;

var s, t, itsX, itsY;

//Check X dimension
if (bx2 != bx1)
{
    s = abs(bx1) < 1 ? sign(bx2 - bx1) : sign(bx1);
    t = (s - bx1) / (bx2 - bx1);
    if (t >= 0 && t <= 1)
    {
        itsY = lerp(by1, by2, t);
        if (abs(itsY) <= 1)
        {
            bx2 = s;
            by2 = itsY;
        }
    }
}

//Check Y dimension
if (by2 != by1)
{
    s = abs(by1) < 1 ? sign(by2 - by1) : sign(by1);
    t = (s - by1) / (by2 - by1);
    if (t >= 0 && t <= 1)
    {
        itsX = lerp(bx1, bx2, t);
        if (abs(itsX) <= 1)
        {
            bx2 = itsX;
            by2 = s;
        }
    }
}

//Find the point of intersection in world space
return [bX + bx2 * bW / 2, bY + by2 * bH / 2];
It returns the position of the first intersection with the rectangle as an array, regardless of where the start and end points are.

Edit:
Also, here's the 3D equivalent, casting a ray at a cube (which, since it's given as a matrix, can be rotated as well):
Code:
/// @description cast_ray_block(blockMatrix, x1, y1, z1, x2, y2, z2)
/// @param blockMatrix
/// @param x1
/// @param y1
/// @param z1
/// @param x2
/// @param y2
/// @param z2
/*
Finds the intersection between a line segment going from [x1, y1, z1] to [x2, y2, z2], and a block with the given matrix
The block matrix can be created with matrix_build(x, y, z, xrot, yrot, zrot, xscale, yscale, zscale), where:
    (x, y, z) are the center coordinates of the cube,
    (xrot, yrot, zrot) are the euler angles of the cube, and
    (xscale, yscale, zscale) are half the side lengths of the cube (so the cube is actually twice as large as these values)

Returns the intersection as an array of the following format:
[x, y, z, nx, ny, nz, intersection (true or false)]

Script made by TheSnidr 2018
www.TheSnidr.com
*/
var bM;
bM = argument0;

var x1, y1, z1;
x1 = argument1 - bM[12];
y1 = argument2 - bM[13];
z1 = argument3 - bM[14];

var x2, y2, z2;
x2 = argument4 - bM[12];
y2 = argument5 - bM[13];
z2 = argument6 - bM[14];

//Convert from world coordinates to block normalized coordinates
var lx, ly, lz;
lx = 1 / (sqr(bM[0]) + sqr(bM[1]) + sqr(bM[2]));
ly = 1 / (sqr(bM[4]) + sqr(bM[5]) + sqr(bM[6]));
lz = 1 / (sqr(bM[8]) + sqr(bM[9]) + sqr(bM[10]));

var bx1, by1, bz1;
bx1 = (x1 * bM[0] + y1 * bM[1] + z1 * bM[2])  * lx;
by1 = (x1 * bM[4] + y1 * bM[5] + z1 * bM[6])  * ly;
bz1 = (x1 * bM[8] + y1 * bM[9] + z1 * bM[10]) * lz;

var bx2, by2, bz2;
bx2 = (x2 * bM[0] + y2 * bM[1] + z2 * bM[2])  * lx;
by2 = (x2 * bM[4] + y2 * bM[5] + z2 * bM[6])  * ly;
bz2 = (x2 * bM[8] + y2 * bM[9] + z2 * bM[10]) * lz;

var intersection, s, t, itsX, itsY, itsZ, d, nx, ny, nz;
intersection = false

//Check X dimension
if (bx2 != bx1)
{
    s = abs(bx1) < 1 ? sign(bx2 - bx1) : sign(bx1);
    t = (s - bx1) / (bx2 - bx1);
    if (t >= 0 && t <= 1)
    {
        itsY = lerp(by1, by2, t);
        itsZ = lerp(bz1, bz2, t);
        if (abs(itsY) <= 1 && abs(itsZ) <= 1)
        {
            bx2 = s;
            by2 = itsY;
            bz2 = itsZ;
            d = sqrt(lx);
            nx = bM[0] * d;
            ny = bM[1] * d;
            nz = bM[2] * d;
            intersection = true;
        }
    }
}

//Check Y dimension
if (by2 != by1)
{
    s = abs(by1) < 1 ? sign(by2 - by1) : sign(by1);
    t = (s - by1) / (by2 - by1);
    if (t >= 0 && t <= 1)
    {
        itsX = lerp(bx1, bx2, t);
        itsZ = lerp(bz1, bz2, t);
        if (abs(itsX) <= 1 && abs(itsZ) <= 1)
        {
            bx2 = itsX;
            by2 = s;
            bz2 = itsZ;
            d = sqrt(ly);
            nx = bM[4] * d;
            ny = bM[5] * d;
            nz = bM[6] * d;
            intersection = true;
        }
    }
}

//Check Z dimension
if (bz2 != bz1)
{
    s = abs(bz1) < 1 ? sign(bz2 - bz1) : sign(bz1);
    t = (s - bz1) / (bz2 - bz1);
    if (t >= 0 && t <= 1)
    {
        itsX = lerp(bx1, bx2, t);
        itsY = lerp(by1, by2, t);
        if (abs(itsX) <= 1 && abs(itsY) <= 1)
        {
            bx2 = itsX;
            by2 = itsY;
            bz2 = s;
            d = sqrt(lz);
            nx = bM[8] * d;
            ny = bM[9] * d;
            nz = bM[10] * d;
            intersection = true;
        }
    }
}

if (!intersection)
{
    return [argument4, argument5, argument6, 0, 0, 1, false]; 
}

//Find the point of intersection in world space
var px, py, pz;
px = bM[12] + bx2 * bM[0] + by2 * bM[1] + bz2 * bM[2];
py = bM[13] + bx2 * bM[4] + by2 * bM[5] + bz2 * bM[6];
pz = bM[14] + bx2 * bM[8] + by2 * bM[9] + bz2 * bM[10];
return [px, py, pz, nx, ny, nz, true];
 
Last edited:

GMWolf

aka fel666
Here's a general exact solution to your problem, as long as the block isn't rotated
Generally you will find a lot of solutions that only work for axis aligned things.
Generally, the solution for the rotated version involves transforming the wholse system into the objects local space. essentailly rotating and translating your ray, and then using the axis-aligned algorithm. you then re-transform the results back into world space.
 

TheSnidr

Heavy metal viking dentist
GMC Elder
Generally you will find a lot of solutions that only work for axis aligned things.
Generally, the solution for the rotated version involves transforming the wholse system into the objects local space. essentailly rotating and translating your ray, and then using the axis-aligned algorithm. you then re-transform the results back into world space.
Oh I know, have a look at the 3D version in the spoiler ;D It does precisely that!
 

TheSnidr

Heavy metal viking dentist
GMC Elder
I guess "general solution" was a bit of an overstatement though, I guess it's more like a solution to the specific problem xD
 

Maa2007

Member
Here's a general exact solution to your problem, as long as the block isn't rotated
im eager to apply it, but im not sure how to do so,
i think this is supposed to be a script that you call from an object step event or somthing ?

i never used script_execute before, so im not sure how to use the script, can you provide a simple test file please
 

TsukaYuriko

☄️
Forum Staff
Moderator
A "test file" will not provide you with the learning experience you would have figuring this out on your own - which is the point of this topic - so there's no need for that.

If you're unfamiliar with scripts, I suggest reading up on them in the manual: https://docs2.yoyogames.com/source/_build/3_scripting/3_gml_overview/3_scripts.html
script_execute has nothing to do with any of this, so you can focus wholly on learning how to use scripts and not at all on how to use that function.
 

luvsuper

Member
The first code segment is for a rectangle which is not rotated. See second code segment for a solution involving rotated rectangles.

Both of these solutions assume the line's start point is NOT within the rectangle. If the start piont can be inside the rectangle, then the correct solution can be unclear. If you just want to begin at the start point and go in the direction of the line until you hit one of the sides of the rectangle, then what you want to do is reject negative time solutions by adding this just after the _t5 computation:
if (_t4 < 0) { _t4 = _t5; }

_sx,_sy is the start of the line. _dx, _dy is its direction, which can just be its end point minus its start point. Note: if line's direction is end minus start points, then _t > 1 means the intercept point is not within the line segment.

Code:
    if (_dx == 0) {
        var _t0 =  10000000000000000000000;
        var _t1 = -10000000000000000000000;
    } else {
        var _t0 = (_left - _sx) / _dx;
        var _t1 = (_right - _sx) / _dx;
    }
    if (_dy == 0) {
        var _t2 =  10000000000000000000000;
        var _t3 = -10000000000000000000000;
    } else {
        var _t2 = (_top - _sy) / _dy;
        var _t3 = (_bottom - _sy) / _dy;
    }
    var _t4 = max(min(_t0, _t1), min( _t2, _t3 ) );
    var _t5 = min(max(_t0, _t1), max( _t2, _t3 ) );
    if (_t5 < 0 || _t4 > _t5) {
        _t = -1; //no collision
    } else {
        _t = _t4;  //intercept time
        ///collision point:
        intercept_x = _sx + _dx * _t;
        intercept_y = _sy + _dy * _t;
    }
--------------
However, if the rectangle is rotated, then you have to take that into account. Here, I'm assuming the rectangle is based on an instance sprite. c, s are dcos(image_angle) and dsin(image_angle), or in other words, the cosine and sine of the rectangle's orientation angle. x,y is the origin of the instance representing the rectangle. The width and height of the rectangle are sprite_width and sprite_height. -sprite_xoffset, -sprite_yoffset is the location of what would be the top-left vertex of the rectangle in the rectangle's space, i.e., if the rectangle was not rotated and if it was located at 0,0.

Code:
var _sx1 = (_sx-x) * c + (_sy-y) * -s + sprite_xoffset;
var _sy1 = (_sx-x) * s + (_sy-y) *  c + sprite_yoffset;
var _dx1 = _dx * c + _dy * -s;
var _dy1 = _dx * s + _dy *  c;
if (_dx1 == 0) {
    var _t0 =  10000000000000000000000;
    var _t1 = -10000000000000000000000;
} else {
    var _t0 = (0-_sx1) / _dx1;
    var _t1 = (sprite_width - _sx1) / _dx1;
}
if (_dy1 == 0) {
    var _t2 =  10000000000000000000000;
    var _t3 = -10000000000000000000000;
} else {
    var _t2 = (0-_sy1) / _dy1;
    var _t3 = (sprite_height - _sy1) / _dy1;
}
var _t4 = max(min(_t0, _t1), min( _t2, _t3 ) );
var _t5 = min(max(_t0, _t1), max( _t2, _t3 ) );
if (_t5 < 0 || _t4 > _t5) {
    _t = -1; //no collision
} else {
    _t = _t4;  //intercept time
    //intercept location:
    intercept_x = _sx + _dx * _t;
    intercept_y = _sy + _dy * _t;
}
I love this solving. But this is kinda dirty and sloppy. I had do little refactoring on it and now this is more readable and beauty variant. Thanks to the author for solving "rotated" problem! Cheers!

GML:
// Doing into o_rect object's draw event (for simplicity)
function calculate_intersection_coords(
    outter_point_x,
    outter_point_y,
    rect_angle,
    rect_width,
    rect_height,
    rect_offset_x,
    rect_offset_y,
    rect_center_x,
    rect_center_y
  ) {
  var angle_cos = dcos(rect_angle)
  var angle_sin = dsin(rect_angle)
  var dx = rect_center_x - outter_point_x
  var dy = rect_center_y - outter_point_y
  var sx1 = (outter_point_x - rect_center_x) * angle_cos +
            (outter_point_y - rect_center_y) * -angle_sin +
            rect_offset_x
  var sy1 = (outter_point_x - rect_center_x) * angle_sin +
            (outter_point_y - rect_center_y) * angle_cos +
            rect_offset_y
  var dx1 = dx * angle_cos + dy * -angle_sin
  var dy1 = dx * angle_sin + dy * angle_cos
  var normalized_distance = max(
    min(
      (0 - sx1) / dx1,
      (rect_width - sx1) / dx1
    ),
    min(
      (0 - sy1) / dy1,
      (rect_height - sy1) / dy1
    )
  )

  return [
    outter_point_x + dx * normalized_distance,
    outter_point_y + dy * normalized_distance,
  ]

// Let's check!
var coords = calculate_intersection_coords(mouse_x, mouse_y, image_angle, sprite_width, sprite_height, sprite_xoffset, sprite_yoffset, x, y)
draw_line(mouse_x, mouse_y, x, y)
draw_circle(coords[0], coords[1], 10, false)
}
 
Top