Trig Collision Detection Using a Rotated Rectangle

ID:156173
 
Dec 13 2010, 4:32 pm
I can't seem to figure out how to make a function to determine if one point is inside the rectangle when the rectangle is at a specific angle. Any help would be grateful.

Here is my rectangle and point datum and how the rectangle is setup:
point
    var
        x
        y
    New(_x, _y)
        x = _x
        y = _y

trig_rect
    var
        angle
        point
            tl//top left
            tr//top right
            br//bottom right
            bl//bottom left
            width
            height
    proc/pointInRect(_x, _y)
        return [If the point is inside the rectangle return TRUE]

world/New()
    ..()
    var/trig_rect/rect = loadGraphics(40, 110, 140)

proc/loadGraphics(angle, x, y, trig_rect/rectangle = null)
    var
        base_width = 40
        base_height = 30
        base_x = x
        base_y = y
        
        trig_rect/rect = new
        
    rect.tl = new((angle + 90 == 90  || angle + 90 == 270 ? base_x : base_x + base_height * cos(angle + 90)), (angle + 90 == 180 || angle + 90 == 360 ? base_y : base_y + base_height * sin(angle + 90)))
    rect.tr = new((angle == 90  || angle == 270 ? base_x : base_x + base_width * cos(angle)), (angle == 180 || angle == 360 ? base_y : base_y + base_width * sin(angle)))
    rect.br = new((angle == 90  || angle == 270 ? base_x : base_x + base_width * cos(angle)), (angle == 180 || angle == 360 ? base_y : base_y + base_width * sin(angle)))
    rect.bl = new(base_x, base_y)
    rect.width = base_width
    rect.height = base_height
    rect.angle = angle

    [code]
    return rect


All the points for the rectangle are known when the rectangle is at any given angle.
Dec 13 2010, 5:18 pm (Edited on Dec 13 2010, 5:55 pm)
Hi Zaltron,

If I understood your question correctly... to check if any pt is inside any convex polygon, consider this calculation:

|x1 y1 1|
|x2 y2 1|
|x3 y3 1|

Where the lines mean determinant. Given point P, if we feed it the following point sets: {tl, tr, P}, {tr, br, P}, {br, bl, P} and {bl, tl, P}, we know P is inside the body if all results are either positive or negative (to generalise for a polygon with a different amount of points, simply create these sets by choosing a point in the polygon and progressing clockwise). At least I'm pretty sure we do. Make sure you check!

edit: I should really double-check what I'm writing! In any case this should work.


Dec 13 2010, 5:18 pm
This should do it:

    proc/pointInRect(_x, _y)
        var
            leftX = tl.x-bl.x
            leftY = tl.y-bl.y
            leftNormalX = -leftY
            leftNormalY = leftX
            bottomX = br.x-bl.x
            bottomY = br.y-bl.y
            bottomNormalX = -bottomY
            bottomNormalY = bottomX
        
        // If the dot-product between the vector to the point being tested and the
        //   normal of each side is <= 0, then the point is "behind" the side and 
        //   within the rectangle.
        
        // Test left side
        if(leftNormalX*(_x-bl.x) + leftNormalY*(_y-bl.y) > 0) return 0
        // Test bottom side
        if(bottomNormalX*(_x-bl.x) + bottomNormalY*(_y-bl.y) > 0) return 0
        // Test right side (in opposite direction of left side)
        if(-leftNormalX*(_x-tr.x) + -leftNormalY*(_y-tr.y) > 0) return 0
        // Test top side (in opposite direction of bottom side)
        if(-bottomNormalX*(_x-tr.x) + -bottomNormalY*(_y-tr.y) > 0) return 0
        
        return 1


It creates the normals for the four planes of the rectangle, and then dot-products them with the vector pointing towards the point. If the dot-product is <=0, the point is "on" or "behind" the plane being tested. If it is behind all four planes, the point is inside the rectangle.
Dec 13 2010, 5:32 pm
In response to DarkCampainger
Something is a bit off. The whole rectangle in the picture is the rectangle in which I'm trying to not let any points be drawn in. There is something wrong with the checks on the upper left corner. Also I change the 2nd check to a < sign. Otherwise it didn't work at all and showed all the rectangles. I haven't been able to figure out why the rest is messing up yet. Also, thanks for your help. I really appreciate it.

if(bottomNormalX*(_x-bl.x) + bottomNormalY*(_y-bl.y) < 0) return 0


Dec 13 2010, 5:44 pm
In response to Toadfish
I forgot to mention, if you don't know what a determinant is, the calculation is simply:

proc/calc(point/p1, point/p2, point/p3)
    return (p2.x*p3.y - p2.y*p3.x -p1.x*p3.y + p1.y*p3.x + p1.x*p2.y - p1.y*p2.x)
Dec 13 2010, 7:26 pm (Edited on Dec 13 2010, 7:32 pm)
In response to Zaltron
Turns out we both made a mistake! :)

My bottom and top normals were flipped, because the vectors were calculated going CCW rather than CW.

Here's the corrected version:
trig_rect
    var
        angle
        point
            tl//top left
            tr//top right
            br//bottom right
            bl//bottom left
            width
            height
    proc/pointInRect(_x, _y)
        var
            leftX = tl.x-bl.x // Vectors pointing in CW dir
            leftY = tl.y-bl.y
            leftNormalX = -leftY // Normal is vector rotated 90 Deg CCW
            leftNormalY = leftX
            bottomX = bl.x-br.x // Vectors pointing in CW dir
            bottomY = bl.y-br.y
            bottomNormalX = -bottomY // Normal is vector rotated 90 Deg CCW
            bottomNormalY = bottomX

        // If the dot-product between the vector to the point being tested and the
        //   normal of each side is <= 0, then the point is "behind" the side and
        //   within the rectangle.

        // Test left side
        if(leftNormalX*(_x-bl.x) + leftNormalY*(_y-bl.y) > 0) return 0
        // Test bottom side
        if(bottomNormalX*(_x-br.x) + bottomNormalY*(_y-br.y) > 0) return 0
        // Test right side (in opposite direction of left side)
        if(-leftNormalX*(_x-tr.x) + -leftNormalY*(_y-tr.y) > 0) return 0
        // Test top side (in opposite direction of bottom side)
        if(-bottomNormalX*(_x-tl.x) + -bottomNormalY*(_y-tl.y) > 0) return 0

        return 1


You also weren't calculating the Top-Right corner point, but were instead setting it to the same value as the Bottom-Right. I moved some things around trying to make sense of it, but it's still the same basic process you had before:

proc/loadGraphics(angle, x, y, trig_rect/rectangle = null)
    var
        base_width = 40
        base_height = 30
        base_x = x
        base_y = y
        Cos = cos(angle)
        Sin = sin(angle)

        trig_rect/rect = new

    // Calculate rotated vectors
    // Top-left (Note: cos(a+90) == -sin(a)  and   sin(a+90) == cos(a)  )
    rect.tl = new( (angle + 90 == 90  || angle + 90 == 270) ? 0 : (base_height * -Sin), \
            (angle + 90 == 180 || angle + 90 == 360) ? 0 : (base_height * Cos) )
    // Bottom-right
    rect.br = new( (angle == 90  || angle == 270) ? 0 : (base_width * Cos), \
            (angle == 180 || angle == 360) ? 0 : (base_width * Sin) )

    // Top-right is sum of Top-left and Bottom-right
    rect.tr = new(rect.tl.x+rect.br.x, rect.tl.y+rect.br.y)

    // Transpose to base coordinates
    rect.bl = new(base_x, base_y)
    rect.tl.x += base_x
    rect.tl.y += base_y
    rect.tr.x += base_x
    rect.tr.y += base_y
    rect.br.x += base_x
    rect.br.y += base_y

    rect.width = base_width
    rect.height = base_height
    rect.angle = angle

    return rect


I've tested it and it appears to be working right now. However, keep in mind that if you're using this to do rect-rect collisions, you'll run into issues when the rectangles intersect in their centers, but their corners are outside one another, such as with a cross.

Dec 13 2010, 7:28 pm
In response to DarkCampainger
haha, I actually just figured out that I did taht with the top right corner. I was trying to fix things up but you beat me to it. :) Thanks again!
Dec 13 2010, 7:34 pm
In response to DarkCampainger
Your way looks much neater than mine. Also, I thought you'd like to know I got ToadFish's way to work as well. That's how I stumbled upon my error.

    proc/pointInRect(_x, _y)
        var/point/p = new(_x, _y)
        if(calc(tl, tr, p) > 0) return 0
        if(calc(br, tr, p) < 0) return 0
        if(calc(bl, br, p) < 0) return 0
        if(calc(bl, tl, p) > 0) return 0
        return 1
    proc/calc(point/p1, point/p2, point/p3)
        return (p2.x*p3.y - p2.y*p3.x -p1.x*p3.y + p1.y*p3.x + p1.x*p2.y - p1.y*p2.x)
Dec 13 2010, 7:36 pm
In response to Toadfish
Thanks for your help. When trying to figure out how to do it your way I stumbled upon an error I made which DarkCampainger caught as well. I wasn't calculating the top right corner correctly. Here is a link to a post listing how I used your code to get it to work. Now I have two solutions to this problem. :)

http://www.byond.com/developer/forum/?id=768301
Dec 13 2010, 7:39 pm
In response to Zaltron
Good to hear it's working.

ToadFish's method is definitely more powerful, and could be reused for any convex polygon shape. If you got it working, you might want to keep it, as the performance difference is only a few multiplication operations.
Dec 13 2010, 7:46 pm
In response to DarkCampainger
I got my method working too. Messing up on the top right corner really made things difficult. Here is how I did it:

    proc/pointInRect(_x, _y)
        var
            bottom = _y - bl.y - ((br.y - bl.y)/(br.x - bl.x)) * (_x - bl.x)
            top = _y - tl.y - ((tr.y - tl.y)/(tr.x - tl.x)) * (_x - tl.x)
            right = _y - tr.y - ((br.y - tr.y)/(br.x - tr.x)) * (_x - tr.x)
            left = _y - bl.y - ((tl.y - bl.y)/(tl.x - bl.x)) * (_x - bl.x)
        return (bottom >= 0 && top <= 0 && right <= 0 && left >= 0)
Dec 15 2010, 2:23 am (Edited on Dec 15 2010, 3:10 am)
In response to DarkCampainger
Unless I'm under analyzing it, it's probably easily generalisable for 3D, or really X-dimensional shapes, too. But don't take my word for it.

Incidentally 'toadfish' is the name given to a variety of horribly cute fish from the Batrachoididae fish family. :P
Dec 15 2010, 3:37 am
In response to Zaltron
Now I have two solutions to this problem. :)

Some people, when confronted with a problem, think
"I know, I'll post on the Developer How-To Forum". Now they have two solutions.
(with apologies to Jamie Zawinski)
Dec 15 2010, 3:59 am
In response to Jp
Jp wrote:
Now I have two solutions to this problem. :)

Some people, when confronted with a problem, think
"I know, I'll post on the Developer How-To Forum". Now they have two solutions.
(with apologies to Jamie Zawinski)

Three. :)
http://www.byond.com/developer/forum/?id=768304