[Lua] Polygons

[Beckx]

I was looking for simple solution of point IN polygon detection logic and eventually managed to create something like this, it works perfectly fine, leak resistant, so maybe if anyone will struggle with somethin similar in the future this can be helpful.

function Point(x,y)
    return {x = x, y = y}
end

function Polygon(...)
    local points,polygon = {...},{}
    for i,p in ipairs(points) do
        if type(p) == "table" and p.x and p.y then
            table.insert(polygon,p)
        end
    end
    return polygon
end

function IsInPolygon(p,polygon)

    -- Part 1, checking wheter point is not inside the bounding box of the polygon. (optional)
    local minX,minY,maxX,maxY = polygon[1].x,polygon[1].y,polygon[1].x,polygon[1].y
    for i,q in ipairs(polygon) do
        minX,maxX,minY,maxY = math.min(q.x,minX),math.max(q.x,maxX),math.min(q.y,minY),math.max(q.y,maxY)
    end
    if p.x < minX or p.x > maxX or p.y < minY or p.y > maxY then
        return false
    end
    -- If the point is not inside the bounding box of the polygon. it can't be in the polygon.
    -- You can delete this first part if you want, it's here just to improve performance.

    -- Part 2, logic behind this is explained here https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html
    -- it supports multiple components, concave components and holes in polygons as well
    local inside = false
    local j = #polygon
    for i,q in ipairs(polygon) do
        if (q.y > p.y) ~= (polygon[j].y > p.y) and p.x < (polygon[j].x - q.x) * (p.y - q.y) / (polygon[j].y - q.y) + q.x then
            inside = not(inside)
        end
        j = i
    end

    return inside
end

function test() -- Example of creating pentagon with triangle hole and detecting if unit stands within
    local pol = Polygon(Point(0,0)
    ,Point(-13408.0, -14240.0) -- Here we create simple pentagon passing 5 points
    ,Point(-13920.0, -14688.0)
    ,Point(-13664.0, -15200.0)
    ,Point(-13088.0, -15136.0)
    ,Point(-12960.0, -14624.0)
    ,Point(-13408.0, -14240.0)
    ,Point(0,0)                -- if you are passing holes or multiple components you always need to start every part (component, hole) with (0,0) vertex and finish it with its first Point(x,y) + additional (0,0) vertex
    ,Point(-13440.0, -14592.0) -- here the definition of triangle hole starts
    ,Point(-13248.0, -14848.0)
    ,Point(-13568.0, -14912.0)
    ,Point(-13440.0, -14592.0)
    ,Point(0,0))
    local p = Point(GetUnitX(MY_UNIT),GetUnitY(MY_UNIT))
    print(IsInPolygon(p,pol))
end

 

[Eikonium]

Cool stuff! Can definitely be a huge timesaver. The math seems simple, but isn't.

You might consider

• using emmy annotation to show the intended use of your snippet, like input and output arguments of functions. E.g.:
  

  ---@class Polygon
  Polygon = {}
  
  ---@vararg table<string, number> any number of tables with keys 'x' and 'y', whose values define a Polygon point.
  ---@return Polygon
  function Polygon.create(...)
  ...
  end
  
  ---@param p table<string, number> a table with keys 'x' and 'y', whose values define a point.
  ---@param polygon Polygon
  ---@return boolean
  function Polygon.contains(polygon,p) --sure, we might use colon notation here, if we are going for a proper class. But that's not my point here ;=)
  ...
  end

• also including nil value check into your Polygon function (because using ipairs stops at first nil value).
  

  function Polygon(...)
  local points,polygon,point = table.pack(...),{},nil --using table.pack allows you to iterate from 1 to n instead of using ipairs.
  for i = 1,points.n do
  point = points[i]
  if type(point) == "table" and point.x and point.y then
  table.insert(polygon,point)
  end
  end
  return polygon
  end

Edit: Am I right that polygon points are considered to be connected, if and only if they were stated adjacently in the create function? I.e. for Polygon(p1,p2,p3,p4,p1), p1 would be considered connected to p2 and p4, but not to p3? If so, you may want to include that fact in the description as well
Also, it would be a thing to know, whether writing Polygon(p1,p2,p3,p4) makes p1 connected to p4 or not.

 

[Beckx]

Yeah you are right ... but it wasn't my intention, i just wanted to share this idea since it took hour or two of my time and maybe save it for someone who knows what he's doin.

To the point connecting part ... well that's why i've mentioned source of this logic "PNPOLY - Point Inclusion in Polygon Test - WR Franklin (WRF)"

If you are passing only one polygon ... without holes then u can pass points in order which they are connected and you do not need to finish it with p1 in the end... so in that scenario Polygon(p1,p2,p3,p4) works, however when you want to define multiple components or holes inside them you need to follow instructions in the source

 

[Eikonium]

Ah well, just sharing an idea is totally legit.
I personally like systems that don't require the user to read the code, but if that wasn't your intention, don't bother with it
Thanks again for sharing!

 

[Bribe]

The name "Point" as a function name is too generic. Yes, the function looks like "yeah, Point, what else would I call it?".

I would recommend looking at Anitarf's Vector library for reference. Since wc3c is offline, here's @AGD 's VectorMath library (for an API demonstration): [vJASS] - [Snippet] VectorMath

 

[Bribe]

This completely strips-down the syntax and eliminates the OOP approach. This instead benefits in performance more for static polygons, as their performance will be significantly faster (as they can minimize array lookups). It also returns the bounding box, so users can assign a rect (or other things) to it if they so choose to.

This uses far fewer table indices. I am not sure if it is faster if one has to constantly re-create a polygon as it moves using this approach, or to update the polygon's points in the original approach. The speed is probably the same.

---@param ... takes 3 or more pairs of x,y points
---@return fun(x,y) call this function with a pair of x,y values to check if they are within the polygon.
---@return number minX
---@return number minY
---@return number maxX
---@return number maxY --return a bounding box for the polygon so a user can assign a rect to it that enumerates units within.
function Polygon(...)
    local polygon, n = {...}, 0
    local points = #polygon
    local minX, minY, maxX, maxY = polygon[1], polygon[2], polygon[1], polygon[2]
    local min, max = math.min, math.max
    for i=1, points, 2 do
        n = n + 1
        local x,y = polygon[i], polygon[i+1]
        if n > 1 then
            minX, maxX, minY, maxY = min(x, minX), max(x, maxX), min(y, minY), max(y, maxY)
        end
    end
    return n > 2 and function(x, y)
        
        if x < minX or x > maxX or y < minY or y > maxY then
            return false -- If the point is outside of the bounding box of the polygon, we don't need to check the rest.
        end
        
        -- Logic behind this next part is explained here https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html
        -- it supports multiple components, concave components and holes in polygons as well
        local inside = false
        local j = n - 1
        for i = 1, points, 2 do
            local py = polygon[j+1]
            local qx, qy = polygon[i], polygon[i+1]
            if (qy > y) ~= (py > y) and x < (polygon[j] - qx) * (y - qy) / (py - qy) + qx then
                inside = not inside
            end
            j = i
        end
        return inside
    end, minX, minY, maxX, maxY
end

 

[Bribe]

Approved; the current implementation is fine, and if the user doesn't want to use the Point syntax then they can use the alternative API that I provided.

 

[maddeem]

Here is a memory friendly version

function IsInPolygon(x,y,...)
    local j = select("#",...)
    -- Part 1, checking wheter point is not inside the bounding box of the polygon. (optional)
    local minX,minY,maxX,maxY = select(1,...),select(2,...),select(1,...),select(2,...)
    for i = 1, j, 2 do
        local qx = select(i,...)
        local qy = select(i+1,...)
        minX,maxX,minY,maxY = math.min(qx,minX),math.max(qx,maxX),math.min(qy,minY),math.max(qy,maxY)
    end
    if x < minX or x > maxX or y < minY or y > maxY then
        return false
    end
    -- If the point is not inside the bounding box of the polygon. it can't be in the polygon.
    -- You can delete this first part if you want, it's here just to improve performance.

    -- Part 2, logic behind this is explained here https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html
    -- it supports multiple components, concave components and holes in polygons as well
    local inside = false
    local l = j -1
    for i = 1, j, 2 do
        local qx = select(i,...)
        local qy = select(i+1,...)
        local ay = select(l+1,...)
        if (qy > y) ~= (ay > y) and x < (select(l,...) - qx) * (y - qy) / (ay - qy) + qx then
            inside = not(inside)
        end
        l = i
    end

    return inside
end

Also after some consideration you could easily make polygons have an origin point and apply points as offsets to the origin point. That way you can move the entire polygon by getting the offset from the original origin point to the new origin point. Then you can apply this offset to the sampler x,y without needing to apply to to every point in the array. So the speed at which you could move a polygon would be O(1).

 

[maddeem]

Okay here is such a system...

do
    Polygon = {}
    Polygon.__index = Polygon
    
    function Polygon.new(origin_x,origin_y,...)
        local points = {}
        for i = 1, select("#",...), 2 do
            points[i] = select(i,...) + origin_x
            points[i+1] = select(i+1,...) + origin_y
        end
        return setmetatable({
            origin_x = origin_x,
            origin_y = origin_y,
            offset_x = 0.0,
            offset_y = 0.0,
            points = points,
        }, Polygon)
    end
    
    function Polygon.move_to(self,x,y)
        self.offset_x = self.origin_x - x
        self.offset_y = self.origin_y - y
    end
    
    function Polygon.inside(self,x,y)
        local points = self.points
        local j = #points
        x = x + self.offset_x
        y = y + self.offset_y
        -- Part 1, checking wheter point is not inside the bounding box of the polygon. (optional)
        local minX,minY,maxX,maxY = points[1],points[2],points[1],points[2]
        for i = 1, j, 2 do
            local qx = points[i]
            local qy = points[i+1]
            minX,maxX,minY,maxY = math.min(qx,minX),math.max(qx,maxX),math.min(qy,minY),math.max(qy,maxY)
        end
        if x < minX or x > maxX or y < minY or y > maxY then
            return false
        end
        -- If the point is not inside the bounding box of the polygon. it can't be in the polygon.
        -- You can delete this first part if you want, it's here just to improve performance.
        -- Part 2, logic behind this is explained here https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html
        -- it supports multiple components, concave components and holes in polygons as well.
        local inside = false
        local l = j -1
        for i = 1, j, 2 do
            local qx = points[i]
            local qy = points[i+1]
            local ay = points[l+1]
            if (qy > y) ~= (ay > y) and x < (points[l] - qx) * (y - qy) / (ay - qy) + qx then
                inside = not(inside)
            end
            l = i
        end
        return inside
    end
end

Here is an example:

local poly = Polygon.new(0,0,
    3,3,
    3,-3,
    -3,-3,
    -3,3
)
print(poly:inside(2.9,1))
poly:move_to(0,5)
print(poly:inside(2.9,6))

 

[Eikonium]

local minX,minY,maxX,maxY = select(1,...),select(2,...),select(1,...),select(2,...)

This won't work
select(i, ...) returns all elements starting from the i-th element, not just a single one. That also implies select(1, ...) is just the same as ... itself.

You can do this instead:

local minX, minY = ...
local maxX, maxY = minX, minY

You are using a lot of select-statements in your code, though, each taking all arguments from the original function (potentially many). Are you sure that saving one single closure (function plus table) from Bribe's version is worth this performance overhead?

Edit: Bribe's closure is very efficient on continuous checks on the same single polygon, as it only needs to be created once in the game.

 

[maddeem]

This won't work
select(i, ...) returns all elements starting from the i-th element, not just a single one. That also implies select(1, ...) is just the same as ... itself.

You can do this instead:

local minX, minY = ...
local maxX, maxY = minX, minY

You are using a lot of select-statements in your code, though, each taking all arguments from the original function (potentially many). Are you sure that saving one single closure (function plus table) from Bribe's version is worth this performance overhead?

Edit: Bribe's closure is very efficient on continuous checks on the same single polygon, as it only needs to be created once in the game.

Oh yeah I forgot I would have to reverse iterate. I was wondering why old code of mine did that...

Yeah it is definitely the way to go for a static polygon. I guess my needs are bit more dynamic. I plan on adding rotation too

 

[maddeem]

Here it is with rotation

do
    Polygon = {}
    Polygon.__index = Polygon
    
    local function get_bouding_box(points,j)
        local minX,minY,maxX,maxY = points[1],points[2],points[1],points[2]
        for i = 1, j, 2 do
            local qx = points[i]
            local qy = points[i+1]
            minX,maxX,minY,maxY = math.min(qx,minX),math.max(qx,maxX),math.min(qy,minY),math.max(qy,maxY)
        end
        return minX,maxX,minY,maxY
    end
    
    function Polygon.get_bounding_box(self)
        self.minX, self.maxX, self.minY, self.maxY = get_bouding_box(self.points,#self.points)
        self.is_dirty = false
    end
    
    function Polygon.new(origin_x,origin_y,...)
        local self = setmetatable({
            origin_x = origin_x,
            origin_y = origin_y,
            points = {...},
        }, Polygon)
        self:get_bounding_box()
        return self
    end
    
    function Polygon.move_to(self,x,y)
        self.origin_x = x
        self.origin_y = y
    end
    
    function Polygon.rotate(self,angle)
        local cos_a = math.cos(angle)
        local sin_a = math.sin(angle)
        for i = 1, #self.points, 2 do
            local x = self.points[i]
            local y = self.points[i+1]
            self.points[i] = x * cos_a - y * sin_a
            self.points[i+1] = x * sin_a + y * cos_a
        end
        self.is_dirty = true
    end
    
    function Polygon.scale(self,scale_x,scale_y)
        for i = 1, #self.points, 2 do
            self.points[i] = self.points[i] * scale_x
            self.points[i+1] = self.points[i+1] * scale_y
        end
    end
    
    local function inside(x,y,points,j)
        local is_inside = false
        local l = j -1
        for i = 1, j, 2 do
            local qx = points[i]
            local qy = points[i+1]
            local ay = points[l+1]
            if (qy > y) ~= (ay > y) and x < (points[l] - qx) * (y - qy) / (ay - qy) + qx then
                is_inside = not(is_inside)
            end
            l = i
        end
        return is_inside
    end
    
    function Polygon.inside(self,x,y)
        x = x - self.origin_x
        y = y - self.origin_y
        if self.is_dirty then
            self:get_bounding_box()
        end
        if x < self.minX or x > self.maxX or y < self.minY or y > self.maxY then
            return false
        end
        return inside(x,y,self.points,#self.points)
    end
    
    local ex_tbl = {}
    function Polygon.insideEx(self,x,y,angle,scale_x,scale_y)
        x = x - self.origin_x
        y = y - self.origin_y
        local cos_a = math.cos(angle)
        local sin_a = math.sin(angle)
        for i = 1, #self.points, 2 do
            local x1 = self.points[i] * scale_x
            local y1 = self.points[i+1] * scale_y
            ex_tbl[i] = x1 * cos_a - y1 * sin_a
            ex_tbl[i+1] = x1 * sin_a + y1 * cos_a
        end
        local minX,maxX,minY,maxY = get_bouding_box(ex_tbl,#self.points)
        if x < minX or x > maxX or y < minY or y > maxY then
            return false
        end
        return inside(x,y,ex_tbl,#self.points)
    end
    
    function Polygon.debug(self,state)
        self.debug_data = self.debug_data or {}
        if state then
            local points = self.points
            local j = #points
            local l = j -1
            local ox = self.origin_x
            local oy = self.origin_y
            for i = 1, j, 2 do
                local qx = points[i] + ox
                local qy = points[i+1] + oy
                local ax = points[l] + ox
                local ay = points[l+1] + oy
                table.insert(self.debug_data,
                    AddLightningEx("FORK", false, qx, qy,0, ax, ay,0)
                )
                l = i
            end
        else
            for i = 1, #self.debug_data, 1 do
                DestroyLightning(self.debug_data[i])
                self.debug_data[i] = nil
            end
        end
    end

end

Edit: Added scaling, insideEx which can apply scaling and rotation without permanent alteration to the polygon, I also added a debug display