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).
well there might be an easier way but here is how I do it. Back to algebra class 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 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
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; }
You can just check this script 4 times. This kind of problem is routine enough to have a stock solution.
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): Spoiler 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];
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.
I guess "general solution" was a bit of an overstatement though, I guess it's more like a solution to the specific problem xD
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
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.