check if point lies in polygon lua

Question

How to check if a point lies inside a polygon or some other shapes like star? Anything with multiple vertices but they are connected. After googling for straight 2 hours. This is the code I came up with so far. It's not working the way I want it to work. Sometimes it returns true even if the point does not lie inside polygon. Here's the code.

function isPlayerinBounds (point, vertices)
    local len = #vertices
    local j = 0
    for i=1, len do
        if i == 1 then
            j = len -1
        end

        local result = false
        local ix, iy, jx, jy = vertices[i][1], vertices[i][2], vertices[j][1], vertices[j][2]

        local tx, ty = point[1], point[2]

        if(((iy< ty and jy>=ty) or (jy< ty and iy>=ty) and (ix<=tx or jx<=tx)) then

            j = i
            return true

        end

    end


    return false

end

It can be something like this

Be more specific which type of polygon you want to check. There's a difference in difficulty between a simple triangle and a shape with multiple concave polygons + holes. — Youka, Jul 30 '15 at 19:56
Yes, triangles and recangles are easy. I'm actually working on a project where my script load maps made by mappers ( MTA:SA editor ) . They can place these vertices anywhere. That's the main the problem. I want to make a script which can find whether if point is inside those vertices. I'm really confused. Shape can be something like this: http://i.stack.imgur.com/bxa3b.png — Ðanish Khan, Jul 30 '15 at 21:07
You could [triangulate](https://en.wikipedia.org/wiki/Polygon_triangulation) your polygon, f.e. with **ear clipping**, then it becomes some simple point-in-triangle checks. — Youka, Jul 30 '15 at 21:27

score 2 · Accepted Answer · answered Jul 31 '15 at 11:12

2

Your code is wrong. It tries to implement the ray casting algorithm that counts how many times a horizontal ray crosses the polygon, but your code returns as soon as it finds a crossing.

You need to replace return true with result = not result and return result at the bottom

Check the code in Determining Whether A Point Is Inside A Complex Polygon, on which your code seems to be based.

answered Jul 31 '15 at 11:12

lhf

70,581
9
108
149

This helped me. Thank you :) – Ðanish Khan Sep 23 '15 at 10:15

Peter Gilmour · Answer 2 · 2018-07-26T14:45:51.720

Finally got it working for you. This works the same as yours except takes a list of vertices with .x and .y properties instead of the [1] and [2].

local function insidePolygon(polygon, point)
    local oddNodes = false
    local j = #polygon
    for i = 1, #polygon do
        if (polygon[i].y < point.y and polygon[j].y >= point.y or polygon[j].y < point.y and polygon[i].y >= point.y) then
            if (polygon[i].x + ( point.y - polygon[i].y ) / (polygon[j].y - polygon[i].y) * (polygon[j].x - polygon[i].x) < point.x) then
                oddNodes = not oddNodes;
            end
        end
        j = i;
    end
    return oddNodes 
end

score 1 · Answer 3 · edited May 23 '17 at 11:48

You may wish to take the standard way out, and just force someone else to do it for you. Switching your physics over to a library like the Hardon Collider or LÖVE's physics module (built on Box2D, and so is much more complex than HC's very barebones approach). I'm not an expert on either of them, but I'm fairly sure that it's possible to use HC without it, although it was designed to run on top of LÖVE.
If you do want to solve it yourself, there are quite a few helpful links over at this SO question based around polygon triangulation, including source for a C and JS complex polygon collider implementation.

score 1 · Answer 4 · answered Jul 06 '22 at 20:57

From here: https://love2d.org/forums/viewtopic.php?t=89699

-- By Pedro Gimeno, donated to the public domain
function isPointInPolygon(x, y, poly)
-- poly is a Lua list of pairs like {x1, y1, x2, y2, ... xn, yn}
  local x1, y1, x2, y2
  local len = #poly
  x2, y2 = poly[len - 1], poly[len]
  local wn = 0
  for idx = 1, len, 2 do
    x1, y1 = x2, y2
    x2, y2 = poly[idx], poly[idx + 1]

    if y1 > y then
      if (y2 <= y) and (x1 - x) * (y2 - y) < (x2 - x) * (y1 - y) then
        wn = wn + 1
      end
    else
      if (y2 > y) and (x1 - x) * (y2 - y) > (x2 - x) * (y1 - y) then
        wn = wn - 1
      end
    end
  end
  return wn % 2 ~= 0 -- even/odd rule
end

check if point lies in polygon lua

4 Answers4