2D SAT 碰撞的 Lua 实现

example.lua

--- 两张牌的重叠检测，使用 SAT
function GamePlayUtils.OverlapCheckUseCardData(cb, ct)
    local dtX = CellCardDef.Width / 2
    local dtY = CellCardDef.Height / 2
    local polygonCb = SAT.Polygon("polygonCb", {0, 0}, {{dtX, dtY}, {-dtX, dtY}, {-dtX, -dtY}, {dtX, -dtY}}, 0)
    SAT.SetPolygon(polygonCb, cb.posX, -cb.posY, -cb.rotation)
    local polygonCt = SAT.Polygon("polygonCt", {0, 0}, {{dtX, dtY}, {-dtX, dtY}, {-dtX, -dtY}, {dtX, -dtY}}, 0)
    SAT.SetPolygon(polygonCt, ct.posX, -ct.posY, -ct.rotation)
    return SAT.DetectPolygonAndPolygon(polygonCb, polygonCt)
end

SAT.lua

local MathUtil = {}

---获取两点的距离
function MathUtil.GetDis(vec1, vec2)
    local x1 = vec1.x or vec1[1]
    local y1 = vec1.y or vec1[2]
    local x2 = vec2.x or vec2[1]
    local y2 = vec2.y or vec2[2]

    local disX = x1 - x2
    local disY = y1 - y2
    local dis = math.sqrt(disX * disX + disY * disY)
    return dis
end

---向量归一化
function MathUtil.Normalize(vec)
    local x = vec[1] or vec.x
    local y = vec[2] or vec.y
    local mag = math.sqrt(x * x + y * y)
    if type(vec) == "table" then
        vec[1] = x / mag
        vec[2] = y / mag
    end
    vec.x = x / mag
    vec.y = y / mag
end

---点乘
function MathUtil.Dot(vec1, vec2)
    local x1 = vec1.x or vec1[1]
    local y1 = vec1.y or vec1[2]
    local x2 = vec2.x or vec2[1]
    local y2 = vec2.y or vec2[2]
    return x1 * x2 + y1 * y2
end

---精确到小数点后n位
---num 浮点数
---n 浮点数精确位数
function MathUtil.FloatAccurateN(num, n)
    if type(num) ~= "number" then
        return num;
    end
    n = n or 0;
    n = math.floor(n)
    if n < 0 then
        n = 0;
    end
    local nDecimal = 10 ^ n
    local nTemp = math.floor(num * nDecimal);
    local nRet = nTemp / nDecimal;
    return nRet;
end

---二维向量的向量积
---大小的绝对值表示两个向量构成的三角形的面积的2倍
---正负表示与两个向量构成的平面的法线的方向
function MathUtil.VectorProduct(vec1, vec2)
    local vec1X = vec1.x or vec1[1]
    local vec1Y = vec1.y or vec1[2]
    local vec2X = vec2.x or vec2[1]
    local vec2Y = vec2.y or vec2[2]
    return vec1X * vec2Y - vec2X * vec1Y
end

function MathUtil.Add(pt1, pt2)
    return { x = pt1.x + pt2.x, y = pt1.y + pt2.y }
end

function MathUtil.Sub(pt1, pt2)
    return { x = pt1.x - pt2.x, y = pt1.y - pt2.y }
end

-- 计算圆周上的点位置
function MathUtil.CalCirclePos(centerPos, radius, angleRadians)
    return MathUtil.Add(centerPos, { x = math.cos(angleRadians) * radius, y = math.sin(angleRadians) * radius }), MathUtil.Sub(centerPos, { x = math.cos(angleRadians) * radius, y = math.sin(angleRadians) * radius })
end


--[[
    --- SAT 开始 ---
--]]

---将角度转换为逆时针角度
---rotation (0 ~ 180逆时针,0 ~ -180顺时针)
local function ChangeRotationToInverse(rotation)
    rotation = rotation or 0
    if rotation < 0 then
        rotation = rotation + 360
    end
    return rotation or 0
end

---多边形的边
---vertex1
---vertex2
local function CreateSegment(vertex1, vertex2)
    local segment = { pointA = vertex1, pointB = vertex2, dir = { vertex2.x - vertex1.x, vertex2.y - vertex1.y } }
    return segment
end

--- 创建一个多边形
--- name:多边形名字
--- offset:实际点与多边形的偏移量，offset为多边形的原点，多边形的顶点位置都是相对于这个点的偏移量
--- vertices ： 多边形的顶点数组，位置相对于offset
--- rotation ： 旋转角度（角度不是弧度（0~180为逆时针，0~-180为顺时针）
local function Polygon(name, offset, vertices, rotation)
    local polygon = {}
    polygon.name = name or "polygon"
    polygon.offset = { offset.x or offset[1] or 0, offset.y or offset[2] or 0 }
    -- 弧度
    polygon.rotation = math.rad(ChangeRotationToInverse(rotation))
    --- 模板顶点，相对于offset为原点的顶点数组
    polygon._tempVertices = {}
    for i, vertex in ipairs(vertices) do
        local x = vertices[i][1]
        local y = vertices[i][2]
        table.insert(polygon._tempVertices, { x = x, y = y })
    end
    --顶点数组,实际顶点坐标
    polygon._vertices = {}
    -- 平面中，一个点(x,y)绕任意点(dx,dy)逆时针旋转a度后的坐标
    -- xx= (x - dx)*cos(a) - (y - dy)*sin(a) + dx ;
    -- yy= (x - dx)*sin(a) + (y - dy)*cos(a) +dy ;
    for i, vertex in ipairs(vertices or {}) do
        local x = (vertices[i][1] * math.cos(polygon.rotation)) - (vertices[i][2] * math.sin(polygon.rotation))
        local y = (vertices[i][1] * math.sin(polygon.rotation)) + (vertices[i][2] * math.cos(polygon.rotation))
        table.insert(polygon._vertices, { x = x, y = y })
    end

    ---边
    polygon._edges = {}
    for i = 1, #polygon._vertices do
        table.insert(polygon._edges, CreateSegment(polygon._vertices[i], polygon._vertices[1 + i % (#polygon._vertices)]))
    end

    polygon.centerPoint = { x = 0, y = 0 }

    --- 注册点到中心点的距离
    polygon._centerToAnchorDistance = MathUtil.GetDis({ 0, 0 }, polygon.offset)
    --- 中心点相对于注册点的旋转弧度
    polygon._centerToAnchorRadian = math.atan(polygon.offset[2], polygon.offset[1])

    return polygon
end

---设置多边形的实际位置，更新多边形的信息
---polygon 多边形
---x 碰撞体的实际位置X
---y 碰撞体的实际位置y
---rotation 是角度不是弧度
local function SetPolygon(polygon, x, y, rotation)
    rotation = ChangeRotationToInverse(rotation) or 0
    local r = math.rad(rotation)
    polygon.rotation = r
    ---相对于世界坐标系旋转的弧度
    local radian = polygon._centerToAnchorRadian + r
    local dx = polygon._centerToAnchorDistance * math.cos(radian)
    local dy = polygon._centerToAnchorDistance * math.sin(radian)
    ---中心点的世界坐标
    polygon.centerPoint.x = x + dx
    polygon.centerPoint.y = y + dy

    ---更新多边形顶点位置（相对于世界坐标的）
    for i, vertex in ipairs(polygon._vertices) do
        local _x = polygon._tempVertices[i].x
        local _y = polygon._tempVertices[i].y
        polygon._vertices[i].x = polygon.centerPoint.x + (_x * math.cos(polygon.rotation)) - (_y * math.sin(polygon.rotation))
        polygon._vertices[i].y = polygon.centerPoint.y + (_x * math.sin(polygon.rotation)) + (_y * math.cos(polygon.rotation))
    end

    ---更新边的信息
    for i = 1, #polygon._vertices do
        local pointA = polygon._vertices[i]
        local pointB = polygon._vertices[1 + i % (#polygon._vertices)]
        polygon._edges[i].pointA = pointA
        polygon._edges[i].pointB = pointB
        polygon._edges[i].dir[1] = pointB.x - pointA.x
        polygon._edges[i].dir[2] = pointB.y - pointA.y
    end
end

---计算多边形在轴上的投影
---polygon 多边形
---axis 投影的轴
---返回值为投影两端的最大值与最小值
local function GetProjectionWithAxis(polygon, axis)
    MathUtil.Normalize(axis)
    ---在轴上面的投影
    local min = MathUtil.Dot(polygon._vertices[1], axis)
    local max = min
    for i, v in ipairs(polygon._vertices) do
        local projection = MathUtil.Dot(v, axis)
        if projection < min then
            min = projection
        end
        if projection > max then
            max = projection
        end
    end
    return MathUtil.FloatAccurateN(min, 3), MathUtil.FloatAccurateN(max, 3)
end

local function CheckIsProjectionContains(a, b)
    local aMin = a[1]
    local aMax = a[2]
    local bMin = b[1]
    local bMax = b[2]
    if (aMax < aMin) then
        aMin = aMax
        aMax = a[1]
    end
    if (bMax < bMin) then
        bMin = bMax
        bMax = b[1]
    end
    return not (aMin > bMax or aMax < bMin)
end

---polygonA 多边形
---polygonB 多边形
---分离轴，以多边形的每条边的法向量为轴，将多边形投影到轴上，如有任意一个轴上的两个多边形的投影不相交，那么这两个多边形就是分离的
local function DetectPolygonAndPolygon(polygonA, polygonB)
    local aProjection = {}
    local bProjection = {}
    local segmentNormal = {}
    for i, segment in ipairs(polygonA._edges) do
        ---边的法线向量
        segmentNormal[1] = segment.dir[2]
        segmentNormal[2] = -segment.dir[1]
        ---两个多边形在当前轴上的投影
        aProjection[1], aProjection[2] = GetProjectionWithAxis(polygonA, segmentNormal)
        bProjection[1], bProjection[2] = GetProjectionWithAxis(polygonB, segmentNormal)
        if not CheckIsProjectionContains(aProjection, bProjection) then
            return false
        end
    end

    for i, segment in ipairs(polygonB._edges) do
        ---边的法线向量
        segmentNormal[1] = segment.dir[2]
        segmentNormal[2] = -segment.dir[1]
        ---两个多边形在当前轴上的投影
        aProjection[1], aProjection[2] = GetProjectionWithAxis(polygonA, segmentNormal)
        bProjection[1], bProjection[2] = GetProjectionWithAxis(polygonB, segmentNormal)
        if not CheckIsProjectionContains(aProjection, bProjection) then
            return false
        end
    end
    return true
end

---多边形与点的碰撞(判断一个点是在多边形内，还是在多边形上，还是在多边形外)
---polygon 多边形
---point 需要检测的点
---多边形可看做从某点出发的闭合回路，内部的点永远在回路的同一边。通过边与点的连线的向量积(叉积)的正负表示方向，
---顺时针方向，所有向量积数值均为负，逆时针方向，所有向量积数值均为正
local function DetectPolygonAndPoint(polygon, point)
    local pointX = point.x or point[1]
    local pointY = point.y or point[2]
    local firstVectorProduct = 0
    for i, edge in ipairs(polygon._edges) do
        local vertex = edge.pointA
        ---边的第一个顶点point的向量
        local vertex2point = { pointX - vertex.x, pointY - vertex.y }
        ---边与vertex2point的向量积
        local vectorProduct = MathUtil.FloatAccurateN(MathUtil.VectorProduct(edge.dir, vertex2point), 3)
        ---点在多边形的边上
        if vectorProduct == 0 then
            return true
        end
        if i == 1 then
            firstVectorProduct = vectorProduct
        else
            if firstVectorProduct * vectorProduct < 0 then
                return false
            end
        end
    end
    return true
end

local function PrintPolygon(polygon)
    print(polygon.name .. " offset ", polygon.offset[1], polygon.offset[2])
    print(polygon.name .. " centerPoint ", polygon.centerPoint.x, polygon.centerPoint.y)
    print(polygon.name .. "模板顶点信息：===========================================")
    for index, value in ipairs(polygon._tempVertices) do
        print(string.format("x = %f, y = %f", polygon._tempVertices[index].x, polygon._tempVertices[index].y))
    end
    print(polygon.name .. "模板顶点信息：===========================================")
    print(polygon.name .. "实际顶点信息：===========================================")
    for index, value in ipairs(polygon._vertices) do
        print(string.format("x = %f, y = %f", polygon._vertices[index].x, polygon._vertices[index].y))
    end
    print(polygon.name .. "实际顶点信息：=======================================")
    print(polygon.name .. "边信息：===========================================")
    for index, value in ipairs(polygon._edges) do
        print(string.format("dir = (%f,%f)", polygon._edges[index].dir[1], polygon._edges[index].dir[2]))
    end
    print(polygon.name .. "边信息：=======================================")
end

local function Circle(offset, radius)
    local circle = {}
    circle.radius = radius or 0
    circle.offset = { x = offset.x and offset[1] or 0, y = offset.y and offset[2] or 0 }
    circle.centerPoint = { x = 0, y = 0 }
    return circle
end

local function CircleSet(circle, x, y, radius)
    circle.centerPoint.x = x + circle.offset.x
    circle.centerPoint.y = y + circle.offset.y
    circle.radius = radius or circle.radius
end

---计算圆形在轴上的投影
---axis 投影的轴
---返回投影两端的最大值与最小值
local function GetCircleProjectionWithAxis(circle, axis)
    MathUtil.Normalize(axis)
    ---线段的夹角
    local rad = math.atan(axis.y, axis.x)
    ---经过圆心，线段与圆相交的两个点的位置
    local pointInCircle1, pointInCircle2 = MathUtil.CalCirclePos(circle.centerPoint, circle.radius, rad)
    ---分别两个点在轴上的投影
    local min = MathUtil.Dot(pointInCircle1, axis)
    local max = min
    local min2 = MathUtil.Dot(pointInCircle2, axis)
    if min2 < min then
        min = min2
    end
    if min2 > max then
        max = min2
    end
    return MathUtil.FloatAccurateN(min, 3), MathUtil.FloatAccurateN(max, 3)
end

---polygon 多边形
---circle 圆形
---原理与多边形判断一样
local function DetectPolygonAndCircle(polygon, circle)
    local aProjection = {}
    local bProjection = {}
    local circleCenter = circle.centerPoint
    for i, segment in ipairs(polygon._edges) do
        ---多边形的边的法线向量
        local axes = { segment.dir[2], -segment.dir[1] }
        ---多边形在当前轴上的投影
        aProjection[1], aProjection[2] = GetProjectionWithAxis(polygon, axes)
        ---圆在当前轴上的投影
        bProjection[1], bProjection[2] = GetCircleProjectionWithAxis(circle, axes)
        if not CheckIsProjectionContains(aProjection, bProjection) then
            return false
        end
    end
    return true
end

--[[
local polygonA = Polygon("polygonA",{ 0, 0},{ { 0, 1}, { -1, 0}, { -1, -1}, { 1, -1}, { 1, 0}},0)
SetPolygon(polygonA,0,0,60)
local polygonB = Polygon("polygonB",{ 0, 0},{ { 0, 1}, { -1, 0}, { -1, -1}, { 1, -1}, { 1, 0}},0)
SetPolygon(polygonB,0,0,-30)
print("多边形A,B碰撞 ： ", DetectPolygonAndPolygon(polygonA, polygonB))
--]]

--[[
local polygonA = Polygon("polygonA", { 1, 1 }, { { 0, 1 }, { -1, 0 }, { -1, -1 }, { 1, -1 }, { 1, 0 } }, 0)
SetPolygon(polygonA, 0, 0, -45)
local circleA = Circle({ 0, 0 }, 1)
CircleSet(circleA, 2, 0, 1)
print("多边形A与圆B碰撞 ： ", DetectPolygonAndCircle(polygonA, circleA))
--]]

--[[
local polygonA = Polygon("polygonA", { 0, 0 }, { { 0, 1 }, { -1, 0 }, { -1, -1 }, { 1, -1 }, { 1, 0 } }, 0)
SetPolygon(polygonA, 0, 0, 30)
local pointB = { x = 0, y = 1 }
print("多边形A与点B碰撞 ： ", DetectPolygonAndPoint(polygonA, pointB))
--]]

return {
    Polygon = Polygon,
    SetPolygon = SetPolygon,

    Circle = Circle,
    CircleSet = CircleSet,

    DetectPolygonAndPolygon = DetectPolygonAndPolygon,
    DetectPolygonAndPoint = DetectPolygonAndPoint,
    DetectPolygonAndCircle = DetectPolygonAndCircle,

    PrintPolygon = PrintPolygon
}