util.polygon = {}
util.polygon.known = {}

--- extracts the corner index and its polygon name out of a given triggerZone
--- @param zName string name of zone
--- @return string, number @polygon name, corner index
function util.polygon.zoneToNameIndex(zName)
    if type(zName) ~= "string" then error(util.error.argErr(zName, "string", 1)) end

    -- retrieve all delimiters and then retrieve information (pattern def[del]+<name>[del]+<index>)
    local delims = util.naming.getDelIndices(zName)

    local polyName = zName:sub(delims[1] + 1, delims[2] - 1)
    local polyIndex = zName:sub(delims[2] + 1, #zName)

    return polyName, tonumber(polyIndex)
end

--- generates polygon tables out of trigger zones placed in the mission editor.
--- @param name? string name of the polygon to generate. If not supplied all available polygons are returned
--- @return any[] @all polygons in form {[polyName] = { [1] = {x = x, y = y} ... }}
function util.polygon.generateFromTriggers(name)
    if type(name) ~= "string" then error(util.error.argErr(name, "string", 1)) end

    -- automatically returns all zones if name is nil (wich we want)
    local polygons = {}
    local zones = util.trigger.getPolyZones(name)

    -- go through all trigger zones placewd in ME
    for _i, z in ipairs(zones) do
        local pName, pIndex = util.polygon.zoneToNameIndex(z.name)

        -- polygon table (name as index)
        polygons[pName] = polygons[pName] or {}

        -- add index to polygon table (as nth corner)
        polygons[pName][pIndex] = { x = z.point.x, y = z.point.z }
    end

    return polygons
end

--- checks if the rays r1 (P1 <=> P2) and r2 (P3 <=> P4) intersect at any point
--- @param P1 table (vec2)
--- @param P2 table (vec2)
--- @param P3 table (vec2)
--- @param P4 table (vec2)
--- @return boolean @true if intersect false if not
function util.polygon.doIntersect(P1, P2, P3, P4)
    if type(P1) ~= "table" then error(util.error.argErr(P1, "table", 1)) end
    if type(P2) ~= "table" then error(util.error.argErr(P2, "table", 2)) end
    if type(P3) ~= "table" then error(util.error.argErr(P3, "table", 3)) end
    if type(P4) ~= "table" then error(util.error.argErr(P4, "table", 4)) end

    local M = { x1 = P2.x-P1.x, x2 = P3.x-P4.x,
                y1 = P2.y-P1.y, y2 = P3.y-P4.y, }

    local s = { x1 = P3.x-P1.x, y1 = P3.y-P1.y, }

    -- solve intersection system
    local res = util.math.solve2x2(M, s)

    -- system not solvable so there is two options
    -- lines are parallel => no intersection => false
    -- lines are equal => no intersection either => false
    if res == nil then return false end

    return (res.x1 <= 1.0 and res.x1 >= 0.0) and (res.y1 <= 1.0 and res.y1 >= 0.0)
end

--- checks if a point (vec2) is inside a given polygon
--- @param point table point you want to check
--- @param polyName string name of the polygon you want to check
--- @param reference? table MUST be known to be outside the polygon. Defaults to x = -1e10, y = -1e10 since this should be outside most polygons anyways.
--- @return boolean
function util.polygon.pointInPolygon(point, polyName, reference)
    if type(point) ~= "table" then error(util.error.argErr(point, "table", 1)) end
    if type(polyName) ~= "string" then error(util.error.argErr(polyName, "string", 2)) end

    -- pick 0, 0 as a reference if there is no referece
    reference = reference or { x = -1e10, y = -1e10 }

    -- retrieve polygon (save once it was used once)
    local polygon = util.polygon.known[polyName]
                    or util.misc.flat(util.polygon.generateFromTriggers(polyName), function(pk, ck) return ck end, 1)

    --  if no polygon with this name could be found return false (not in)
    if not polygon then return false end

    util.polygon.known[polyName] = util.polygon.known[polyName] or polygon

    -- go through the polygon and check if the ray from 0 to point intersects with its individual edges
    local prevCorner, intersects = polygon[1], 0

    for i=2, #polygon do
        local doInter = util.polygon.doIntersect(reference, point, prevCorner, polygon[i])

        prevCorner, intersects = polygon[i], intersects + (doInter and 1 or 0)
    end

    -- for loop doesnt close polygon so we have to manually check last one
    local doInter = util.polygon.doIntersect(reference, point, polygon[#polygon], polygon[1])
    intersects = intersects + (doInter and 1 or 0)

    -- if the amount of intersects is even, the point is outside the polygon else inside
    return (intersects % 2) ~= 0
end