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

 

[Uncle]

Good work, but I think you want to move this thread to somewhere like: Submissions

 

[Beckx]

Yeah i've moved it to another thread, this can be removed.