PointInConcavePolygon at this website is not correct, it gives a incorrect true

General discussion about LÖVE, Lua, game development, puns, and unicorns.
Post Reply
gcmartijn
Prole
Posts: 47
Joined: Sat Dec 28, 2019 6:35 pm

PointInConcavePolygon at this website is not correct, it gives a incorrect true

Post by gcmartijn »

Hi,

I'm write a unittest and using this function to detect if a point is inside a polygon.
https://love2d.org/wiki/PointInConcavePolygon

Code: Select all

poly = {
        0,
        0,
        10,
        0,
        10,
        10,
        0,
        10
    }

pointInPolygon(poly, 10, 10) -- returns false , correct
pointInPolygon(poly, 10, 0) -- returns false , correct
pointInPolygon(poly, 0, 10) -- returns false , correct
pointInPolygon(poly, 10, 10) -- returns true but that is incorrect.
 

Code: Select all

  -- detect all lines in the polygon
    for y = 1, 9 do
        for x = 1, 9 do
            lu.assertEquals(Polygon.pointInPolygon(poly, x, y), true, "point x: " .. x .. "point y: " .. y)
        end
    end

    -- the outer line is not included
    -- here I was working to scan the outline that returns false

I don't know if someone has a fix or a correct function that I can use ?
And maybe with an optional function argument to include the border in the collision detection.

Thanks
User avatar
ivan
Party member
Posts: 1719
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: PointInConcavePolygon at this website is not correct, it gives a incorrect true

Post by ivan »

There is no such thing as the "border" of a polygon since the edges are lines which are in theory infinitely thin.
Floating point math has a hardware limit to the precision so forget about it.
Also, check out my tutorial for more info:
https://2dengine.com/?p=polygons
gcmartijn
Prole
Posts: 47
Joined: Sat Dec 28, 2019 6:35 pm

Re: PointInConcavePolygon at this website is not correct, it gives a incorrect true

Post by gcmartijn »

Ow I did know that, thanks for the information.
I will unittest only the inside points and not the 'border'.
User avatar
pgimeno
Party member
Posts: 2548
Joined: Sun Oct 18, 2015 2:58 pm

Re: PointInConcavePolygon at this website is not correct, it gives a incorrect true

Post by pgimeno »

Technically (mathematically speaking), the border may be included or not, generating "open" or "closed" rectangles; however, as Ivan said, floating point precision renders that distinction useless, and you have to settle for "a point in the polygon's border, or very close to it, may or may not be included as part of the polygon", and that distinction may even vary depending on the position or width/height of the polygon.
Post Reply

Who is online

Users browsing this forum: No registered users and 10 guests