是凸多边形 Lua 中的点

Question

我正在尝试检查点 x, y 是否在多边形内部

poly = {x1,y1, x2,y2, x3,y3 ...}

但是出了问题：

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)
        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

有时顺时针方向是对的，但有时却说方向错误。

Answer 1

三角形符号面积的正确公式是

(x1*y2 - x2*y1)/2

假设第三个顶点位于

(0,0)

当所有点-边-三角形区域具有相同符号时，点位于凸多边形内部。

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