mathluapolygoncontainsconvex

Check if point is in convex polygon


I'm trying to check if point x, y is inside of polygon poly = {x1,y1, x2,y2, x3,y3 ...}

But something goes wrong:

local function pointInConvexPolygon(x, y, poly)
    -- poly as {x1,y1, x2,y2, x3,y3, ...}
    local imax = #poly

    local function isVerticesClockwise(poly)
        local sum = 0
        local imax = #poly
        local x1, y1 = poly[imax-1], poly[imax]
        for i = 1, imax - 1, 2 do
            local x2, y2 = poly[i], poly[i + 1]
            sum = sum + (x2 - x1) * (y2 + y1)
            x1, y1 = x2, y2 -- fixed
        end
        local isClockwise = sum < 0
        love.window.setTitle(isClockwise and 'clockwise' or 'counterclockwise')
        return isClockwise
    end

    local sign = isVerticesClockwise(poly) and 1 or -1
    local x1, y1 = poly[imax-1], poly[imax]
    for i = 1, imax - 1, 2 do
        local x2, y2 = poly[i], poly[i + 1]
        local dotProduct = (x - x1) * (y1 - y2) + (y - y1) * (x2 - x1)
        if sign * dotProduct < 0 then
            return false
        end
        x1, y1 = x2, y2
    end
    return true
end

Sometimes clockwise direction is right, but sometimes it says wrong direction.


Solution

  • The correct formula of the triangle signed area is (x1*y2 - x2*y1)/2 assuming the third vertex is at (0,0)
    A point is inside a convex poly when all point-edge-traingle areas are of the same sign.

    local function polyEdgeIterator(poly)
       -- poly as {x1,y1, x2,y2, x3,y3, ...}
       local i, imax = 0, #poly
       local x2, y2 = poly[imax-1], poly[imax]
       return
          function()
             i = i + 2
             if i <= imax then
                local x1, y1 = x2, y2
                x2, y2 = poly[i - 1], poly[i]
                return x1, y1, x2, y2
             end
          end
    end
    
    local function getTriangleArea(x0,y0, x1,y1, x2,y2)
       -- area of the triangle, its sign is determined by the triangle vertices sequence direction (CW/CCW)
       return ((x1-x0) * (y2-y0) - (x2-x0) * (y1-y0)) * 0.5
    end
    
    local function pointInConvexPolygon(x, y, poly)
       local minArea, maxArea = 0, 0
       for x1,y1, x2,y2 in polyEdgeIterator(poly) do
          local area = getTriangleArea(x,y, x1,y1, x2,y2)
          minArea = math.min(minArea, area)
          maxArea = math.max(maxArea, area)
          if minArea * maxArea < 0 then
             return false
          end
       end
       return true
    end
    
    print(pointInConvexPolygon(2,1, {1,-1, 2,2, 4,1})) -- true
    print(pointInConvexPolygon(3,0, {1,-1, 2,2, 4,1})) -- false