[SOLVED] Point in polygon collision

[Bigfoot71]

Hi there !

I'm trying to detect if a point is inside a mesh.
The point is the player and the mesh corresponds to a circle at the start and will change shape as the execution progresses.
So I wrote a function that looks like this:

Code: Select all

function pointInPolygon(pos, mesh) -- vc : current vertice | vn : next vertice

    local inPolygon = false
    local countVerts = mesh:getVertexCount()

    for ivc= 1, countVerts do

        local ivn = ivc + 1

        local xc, yc = mesh:getVertex(ivc) -- current

        if ivn > countVerts then ivn = 1 end
        local xn, yn = mesh:getVertex(ivn)

        if (yc <= pos.y and pos.y < yn) or (yn <= pos.y and pos.y < yc)
        and (pos.x < (xn - xc) * (pos.y - yc) / (yn - yc) + xc) then
            inPolygon = not inPolygon
        end

    end

    return inPolygon

end

But unfortunately it does not work, do you have another solution to achieve this ?

[marclurr]

I wrote this quite some time ago, it's in C++ but it does what you're trying to do

Code: Select all

auto isClockwise = [&](const Tri& tri) -> bool {
	float x = cross(tri.p1, tri.p2);
	x += cross(tri.p2, tri.p3);
	x += cross(tri.p3, tri.p1);
	return x > 0;
};

auto isPointInTriangle = [&isClockwise](const glm::vec2& p, const Tri& tri) -> bool {
	return isClockwise({ p, tri.p1, tri.p2 })
		&& isClockwise({ p, tri.p2, tri.p3 })
		&& isClockwise({ p, tri.p3, tri.p1 });
};

Basically it creates an imaginary triangle between the point you're checking and each line segment of the triangle, then checks that the winding of that imaginary triangle is clockwise. If all of the imaginary triangles have clockwise winding order the point is inside the triangle. If any are not clockwise the point is not. Here it's only checking against a triangle but it should work fine for any convex polygon. You need to make sure your polygon is ordered clockwise for this to work. "cross" is the vector cross product, the vector module of the hump library has an implementation of this.

[Bigfoot71]

Thank you very much for your help it will surely help me in the future but I have just solved my problem, after modifying the little algorithm several times I finally understood and it's quite stupid, when I generate my mesh I don't pass no real coordinates given that I put them in 'love.graphics.draw()'... It's very very stupid of me, excuse me...

As a bonus here is the function that I have just made and which works, we can pass additional coordinates, otherwise the calculation is done on 0.0 (logical...)

Code: Select all

local pointInPolygon = function(pos, mesh, mpos)
    if mpos then xp, yp = mpos.x, mpos.y else xp, yp = 0, 0 end

    local inPolygon = false
    local countVerts = mesh:getVertexCount()

    for ivc= 1, countVerts do

        local ivn = ivc + 1
        if ivn > countVerts then ivn = 1 end

        local xc, yc = mesh:getVertex(ivc)
        local xn, yn = mesh:getVertex(ivn)

        xc, xn = xc + xp, xn + xp
        yc, yn = yc + yp, yn + yp

        if ((yn > pos.y) ~= (yc > pos.y)) and (pos.x < (pos.y - yn) * (xc - xn)/(yc - yn) + xn) then
            inPolygon = not inPolygon
        end

        --lg.line(xc,yc,xn,yn)

    end

    return inPolygon

end

It works perfectly now

[darkfrei]

Very nice solution:
https://2dengine.com/?p=polygons#Point_in_polygon