Square and Triangle collision

[Resike]

As the title says, i would like to detect collision between the mentioned polygons. I can provide the coordinates of the objects in real time.

[semlar]

You might look into ray casting, not sure what you're looking to accomplish.

[Resike]

Found this nasty little monster:

local triangle = {
    [1] = {x = 0, y = 0},
    [2] = {x = 1, y = 0},
    [3] = {x = 0, y = 1}
}
 
local function PointInPolynom(p, x, y)
    local c = false
    for i = 1, #p do
        local j = i + 1
        if j > #p then
            j = 1
        end
        if ((p[i].y > y) ~= (p[j].y > y)) and (x < (p[j].x - p[i].x) * (y - p[i].y) / (p[j].y - p[i].y) + p[i].x) then
            c = not c
        end
    end
    return c
end
 
print(PointInPolynom(triangle, 0.5, 0.5)) -- false
print(PointInPolynom(triangle, 0.5, 0.49)) -- true

Should work with every polynom.

Edit: Some fixes.

[semlar]

Should probably be "polygon", but your code won't work since you call the function "PointInPolynom" and call it via "PointInPoly".

I'm sure it's just a typo from copying it into this.

[Resike]

Originally Posted by semlar Should probably be "polygon", but your code won't work since you call the function "PointInPolynom" and call it via "PointInPoly". I'm sure it's just a typo from copying it into this.

Yeah made some last minute changes.

Actually i'm not entierely sure how the hell it is working, but its superfast and clean. Working on it to convert it to square vs polynom.

[semlar]

I think it loops through all of the points of one shape and checks whether any of them fall within the boundaries of the other shape (might only work on convex polygons, but that won't matter with squares and triangles).

[Resike]

Polynom in Polynom version:

local triangle = {
    [1] = {x = 0, y = 0},
    [2] = {x = 1, y = 0},
    [3] = {x = 0, y = 1}
}
 
local square = {
    [1] = {x = -1, y = 0},
    [2] = {x = -2, y = 0},
    [3] = {x = -1, y = 1},
    [4] = {x = -2, y = 1}
}
 
local function PolynomInPolynom(p1, p2)
    local c = { }
    for i = 1, #p2 do
        c[i] = false
        for j = 1, #p1 do
            local k = j + 1
            if k > #p1 then
                k = 1
            end
            if ((p1[j].y > p2[i].y) ~= (p1[k].y > p2[i].y)) and (p2[i].x < (p1[k].x - p1[j].x) * (p2[i].y - p1[j].y) / (p1[k].y - p1[j].y) + p1[j].x) then
                c[i] = not c[i]
            end
        end
        if c[i] then
            return true
        end
    end
    return false
end
 
print(PolynomInPolynom(triangle, square)) -- false

It's not perfect, but it's pretty accurate.

[Resike]

Originally Posted by semlar I think it loops through all of the points of one shape and checks whether any of them fall within the boundaries of the other shape (might only work on convex polygons, but that won't matter with squares and triangles).

I think it should work with concaves too, gotta test it.

[Duugu]

Originally Posted by semlar I think it loops through all of the points of one shape and checks whether any of them fall within the boundaries of the other shape (might only work on convex polygons, but that won't matter with squares and triangles).

I would say it takes all lines from p1 and uses a horizontal line to test if and how many time the line intersects with a line of p2 (http://www.alienryderflex.com/polygon/). It can be used for convex and concave polygons.

There are other ways to test for polygon collisions. Like the separating axis approach (eg. http://www.codeproject.com/Articles/...sion-Detection). It's not that much more work, and it provides you with more options. Like using a velocity vector to detect collisions before they occure or to separate two overlapping polygons from each other. The drawback is that this approach works with convex polygons only. Concave polygons must be separated into triangles. Which is not that funny.

I've never used it. But it looks fascinating. If you're interested I could try to set up a lua implementation (for convex polygons *g*) next week.

[Resike]

Originally Posted by Duugu I would say it takes all lines from p1 and uses a horizontal line to test if and how many time the line intersects with a line of p2 (http://www.alienryderflex.com/polygon/). It can be used for convex and concave polygons. There are other ways to test for polygon collisions. Like the separating axis approach (eg. http://www.codeproject.com/Articles/...sion-Detection). It's not that much more work, and it provides you with more options. Like using a velocity vector to detect collisions before they occure or to separate two overlapping polygons from each other. The drawback is that this approach works with convex polygons only. Concave polygons must be separated into triangles. Which is not that funny. I've never used it. But it looks fascinating. If you're interested I could try to set up a lua implementation (for convex polygons *g*) next week.

Thats looks intresting too, could be used in the future, but for my current project i want to kill the player as soon as the collision occours, so this code is perfect for me.