GMLscripts.com

Discuss and collaborate on GML scripts
Invert

You are not logged in.

#1 2016-07-03 19:37:20

Juju
Member
Registered: 2015-10-01
Posts: 45

rectangle_on_line

Expand///rectangle_on_line( left, top, right, bottom, x1, y1, x2, y2 )
//
//  Returns TRUE if the rectangle is intersected by the line
//  segment, FALSE otherwise.
//
//      left,top,right,bottom       rectangle's bounding box
//      x1,y1,x2,y2                 line segment
//
/// GMLscripts.com/license

var _dx, _xmin, _xmax, _ymin, _ymax;
var _m, _x, _yl, _yr;

var _bl = argument0;
var _bt = argument1;
var _br = argument2;
var _bb = argument3;
var _x1 = argument4;
var _y1 = argument5;
var _x2 = argument6;
var _y2 = argument7;

if ( _y1 >= _y2 ) {
    _ymax = _y1;
    _ymin = _y2;
} else {
    _ymax = _y2;
    _ymin = _y1;
}

_dx = _x2 - _x1;

//Special case/early-out for vertical lines
if ( _dx == 0 ) {
    return ( ( _bl <= _x1 ) && ( _bt <= _ymax ) && ( _br >= _x1 ) && ( _bb >= _ymin ) );
}

if ( _x1 >= _x2 ) {
    _xmax = _x1;
    _xmin = _x2;
} else {
    _xmax = _x2;
    _xmin = _x1;
}

//Early-out using rectangle-rectangle check
if ( _bl > _xmax ) || ( _bt > _ymax ) || ( _br < _xmin ) || ( _bb < _ymin ) return false;

_m = ( _y2 - _y1 ) / _dx;
_c = _y1 - _m * _x1;

_yl = _m * _bl + _c;
_yr = _m * _br + _c;

return ( ( _bt <= _yl ) || ( _bt <= _yr ) ) && ( ( _bb >= _yl ) || ( _bb >= _yr ) );

Simple one this time round. Optimal?

Last edited by Juju (2016-07-03 19:39:45)

Offline

#2 2016-07-04 02:23:15

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: rectangle_on_line

Seems pretty tight to me. I was working on a vector-base alternative and I discovered that GM:Studio gracefully handles divide-by-zero, apparently respecting the IEEE 754 standard. Sort of blew my mind. I thought I was going crazy.

When implemented with two functions and vector data types, this algorithm looks nicer and can handle any number of dimensions. It can also return the nearest intersection (the line defines a vector with an origin so there is only one solution).

Expand/// line_box_intersection(x0,y0,x1,y1,left,top,right,bottom)
{
    var x0 = argument0;
    var y0 = argument1;
    var x1 = argument2;
    var y1 = argument3;
    var left = argument4;
    var top = argument5;
    var right = argument6;
    var bottom = argument7;

    var flo = 0;
    var fhi = 1;
    
    var f0x = (left - x0) / (x1 - x0);
    var f1x = (right - x0) / (x1 - x0);
    
    if (f0x > f1x) { var temp = f0x; f0x = f1x; f1x = temp; }
    
    if (f1x > flo) {
        if (f0x < fhi) {
    
            flo = max(flo, f0x);
            fhi = min(fhi, f1x);
    
            if (flo < fhi) {
                    
                var f0y = (top - y0) / (y1 - y0);
                var f1y = (bottom - y0) / (y1 - y0);
                
                if (f0y > f1y) { var temp = f0y; f0y = f1y; f1y = temp; }
                
                if (f1y > flo) {
                    if (f0y < fhi) {
                                        
                        flo = max(flo, f0y);
                        fhi = min(fhi, f1y);
                        
                        if (flo < fhi) {
                            // Nearest intersection
                            var ix = x0+flo*(x1-x0);
                            var iy = y0+flo*(y1-y0);
                            return true;
                        }
                    }
                }
            }
        }
    }
    return false;
}

HTML5 Demo: https://xotmatrix.github.io/demos/line_box/index.html
Project: https://xotmatrix.github.io/demos/line_box/line_box.gmz

Indebted to:

Last edited by xot (2016-07-04 04:10:03)


Abusing forum power since 1986.

Offline

#3 2016-07-04 02:23:21

omar
Member
Registered: 2016-06-23
Posts: 8

Re: rectangle_on_line

but if you reverse the rectangle this script will not work fine !
for example , this rectangle (50,50,-50,-50) will return 0 every time

maybe you should do something like:

Expandif argument0>argument2 
{
    _bl=argument2
    _br=argument0
}
if argument1>argument3 
{
    _bt=argument3
    _bb=argument1
}

Offline

#4 2016-07-04 02:26:42

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: rectangle_on_line

That's a fair point, although the variable names clearly imply the order of the coordinates. Setting left to 50 and right to -50 doesn't make sense.

I do like flexibility though. My version doesn't care about the order of the coordinates, despite the argument names, as long as they are opposite corners.


Abusing forum power since 1986.

Offline

#5 2016-07-04 05:59:39

Juju
Member
Registered: 2015-10-01
Posts: 45

Re: rectangle_on_line

Coordinate agnosticism is a nice bonus! I'll do some performance tests later to see if there's any significant difference between the two.

Offline

#6 2016-07-04 15:54:26

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: rectangle_on_line

I updated my example with a new, more general version of the script that can return more info. It uses arrays and the pass by reference ability of accessors to do this. It can be easily extended to more dimensions as well, either explicitly or implicitly. This also works slightly better since it will correctly intersect with a one-dimensional bounding box.

It might be worth altering the arguments to be more user-friendly.

HTLM5: https://xotmatrix.github.io/demos/line_box/index.html
Project: https://xotmatrix.github.io/demos/line_box/line_box.gmz

Expand/// line_bbox_intersection(v0, v1, aabb [, int])
//
//  Returns true if a given line intersects a given axis-aligned bounding 
//  box, false otherwise. Optionally sets the point of intersection.
//
//      v0          origin vector of the line segment, array
//      v1          destination vector of the line, array
//      aabb        box given by two vectors, 2D array
//      int         point of intersection, array
//
//  Notes:
//      v0[0],v0[1]     x0,y0 line origin point
//      v1[0],v1[1]     x1,y1 line destination point
//      aabb[0,0]       left edge of aabb
//      aabb[0,1]       top edge of aabb
//      aabb[1,0]       right edge of aabb
//      aabb[1,1]       bottom edge of aabb
//      int[0],int[1]   x,y intersection point
//      int[2]          fraction of line at intersection
//
/// GMLscripts.com/license
{
    var v0 = argument[0];
    var v1 = argument[1];
    var aabb = argument[2];

    var f;
    f[1] = 1;
    f[0] = 0;

    if (!line_bbox_intersection_clip(0, aabb, v0, v1, f))
        return false;
        
    if (!line_bbox_intersection_clip(1, aabb, v0, v1, f))
        return false;
    
    if (argument_count == 4) {
        var intersection = argument[3];
        intersection[@ 0] = v0[0] + f[0] * (v1[0] - v0[0]);
        intersection[@ 1] = v0[1] + f[0] * (v1[1] - v0[1]);
        intersection[@ 2] = f[0];
    }
    
    return true;
}
Expand/// line_box_intersection_clip(d, aabb, v0, v1, f)
//
//  This is a helper function for line_bbox_intersection().
//
/// GMLscripts.com/license
{
    d = argument0;
    aabb = argument1;
    v0 = argument2;
    v1 = argument3;
    f = argument4;
    
    var f0, f1;
    
    f0 = (aabb[0,d] - v0[d]) / (v1[d] - v0[d]);
    f1 = (aabb[1,d] - v0[d]) / (v1[d] - v0[d]);
    
    if (f1 < f0) { 
        var temp = f0; f0 = f1; f1 = temp; 
    }
    
    if (f1 < f[0]) {
        return false;
    }
    
    if (f0 > f[1]) {
        return false;
    }
    
    f[@ 0] = max(f[0], f0);
    f[@ 1] = min(f[1], f1);
    
    if (f[0] > f[1]) {
        return false;
    }
    
    return true;
}

Last edited by xot (2016-07-23 06:40:12)


Abusing forum power since 1986.

Offline

#7 2016-07-04 19:14:32

iFredQC
Member
Registered: 2015-06-05
Posts: 6

Re: rectangle_on_line

Not taking credits for myself but I had the need for a very optimised version of this once and someone gave me this, which seems pretty good. I'm not very good at maths so I'll just put it here and you guys can analyse it. I remember wanting as many early-outs as possible, but I don't know if it's the best approach to achieve best performance.

Expand///line_cross_rectangle(line_x1,line_y1,line_x2,line_y2,rect_x1,rect_y1,rect_x2,rect_y2)
var lx1, ly1, lx2, ly2, rx1, ry1, rx2, ry2, a, t;
// make sure it goes from low to high
lx1 = min(argument0, argument2);
ly1 = min(argument1, argument3);
lx2 = max(argument0, argument2);
ly2 = max(argument1, argument3);
rx1 = min(argument4, argument6);
ry1 = min(argument5, argument7);
rx2 = max(argument4, argument6);
ry2 = max(argument5, argument7);
// checks if the vertical projection overlaps
if(lx1 < rx1 && lx2 < rx1) {
    return 0;
}
if(lx1 > rx2 && lx2 > rx2) {
    return 0;
}
// collision check for a vertical line or point
if(lx1 == lx2) {
    return !((ly1 < ry1 && ly2 < ry1) || (ly1 > ry2 && ly2 > ry2));
}
// collision check for other lines
a = (ly1 - ly2) / (lx1 - lx2);
t = a * (max(lx1, rx1) - lx1) + ly1;
if(t > ry1 && t < ry2) {
    return 1;
}
t = a * (min(lx2, rx2) - lx1) + ly1;
if(t > ry1 && t < ry2) {
    return 1;
}
return 0;

Last edited by iFredQC (2016-07-04 19:18:12)

Offline

#8 2016-07-05 01:24:38

Juju
Member
Registered: 2015-10-01
Posts: 45

Re: rectangle_on_line

xot, why not return the intersection data as a new array? Seems odd to have to create an array to pass as an argument that actually contains some output.

I didn't get round to performance testing yesterday (was having too much fun with other stuff) so I'll do it now. I'm betting on xot's first script being the fastest!

Offline

#9 2016-07-05 01:47:11

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: rectangle_on_line

I did not return the intersection as an array because I wanted it to return a Boolean — just like everybody else. wink

Passing an argument as reference is a pretty common way to facilitate the return of more than one data type. GML is loose enough to allow functions to optionally return different data types, so you could possibly select what you wanted to return (Boolean or intersection array) using an argument.

Not suggesting this is the best way to do things. This is just a way to do things I'd never tried before.


Abusing forum power since 1986.

Offline

#10 2016-07-05 02:49:27

Juju
Member
Registered: 2015-10-01
Posts: 45

Re: rectangle_on_line

line_intersects_box_test.gmz

This example test four different orientations of line and box to poke at the different early-outs in each script.

xot's array code doesn't appear in this test because it was way slower. Arrays in GM are a bit sluggish, I guess. It's a shame, I would have liked to be able to use arrays as a kind of vec2 datatype.

Under VM, all three scripts compare favourably. xot's code appears to be consistently slightly faster but there's a degree of variance which muddies things a bit. Given that you can get the intersection coordinates (though commented out so it's a fair test), xot's script gets the Double Bacon Cheeseburger Award for tastiest code.

What happens under YYC is altogether different. Juju's code is faster in each of the four tests by a significant margin. Fred's script, which shares a startling similarity to Juju's, is slower than xot's by a small but definite margin. If we open up the Profiler and take a look (bearing in mind that the Profiler only works under VM), we can see where the difference is coming from: it's the use of min and max and that's likely slowing Fred's code down in YYC.

Edit: Thinking about this a bit - why does xot's script not see the same benefits as Juju's under YYC? Are function calls that expensive?

Edit 2: Swapping min and max for simple if branches is a big improvement but, still, xot's code is slower under YYC. The only thing that's left to potentially slow things down are the division operations. Is it possible to multiply through to remove the division operations? Possibly... I'll have a look later (if xot doesn't get to it first).

Last edited by Juju (2016-07-05 03:30:52)

Offline

#11 2016-07-05 04:04:15

Juju
Member
Registered: 2015-10-01
Posts: 45

Re: rectangle_on_line

...Ok, I couldn't resist. There's still a couple of divisions left that I can't seem to take out. This performs better than all other code so far in VM and YYC. I haven't exhaustively tested this by the way, it might not work in 100% of cases.

No, ignore this code. Broken.

Expand///line_box_intersection( x0, y0, x1, y1, left, top, right, bottom )

var x0     = argument0;
var y0     = argument1;
var x1     = argument2;
var y1     = argument3;
var left   = argument4;
var top    = argument5;
var right  = argument6;
var bottom = argument7;

var dx = x1 - x0;
var f0x = left - x0;
var f1x = right - x0;

if ( f0x > f1x ) { var temp = f0x; f0x = f1x; f1x = temp; }

if ( f1x <= 0 ) || ( f0x >= dx ) return false;
    
if ( f0x >  0 ) var flo = f0x / dx else var flo = 0;
if ( f1x < dx ) var fhi = f1x / dx else var fhi = 1;

if ( flo >= fhi ) return false;
        
var dy = y1 - y0;
flo *= dy;
fhi *= dy;

var f0y = top - y0;
var f1y = bottom - y0;

if ( f0y > f1y ) { var temp = f0y; f0y = f1y; f1y = temp; }

if ( f1y <= flo ) || ( f0y >= fhi ) return false;
    
if ( f0y > flo ) flo = f0y;
if ( f1y < fhi ) fhi = f1y;

// Nearest intersection
//var ix = x0+flo*dx/dy;
//var iy = y0+flo;

return ( flo < fhi );

Last edited by Juju (2016-07-05 11:08:04)

Offline

#12 2016-07-05 12:40:01

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: rectangle_on_line

I figured Juju's would be fastest. smile


Abusing forum power since 1986.

Offline

#13 2016-07-05 18:17:41

Juju
Member
Registered: 2015-10-01
Posts: 45

Re: rectangle_on_line

Hah! We were both right happy

The issue with my suggested changes is that multiplying through by dx and dy loses sign information. It's possible to fudge it a bit with abs() calls but... eh. The speed improvement is then lost. Certainly replacing min/max makes things faster but the ultimate prize eludes me...

Offline

Board footer

Powered by FluxBB