凹多边形的判别与分割

[phenomLi]

分离轴算法只能检测圆形和凸多边形。对于凹多边形，要先将其分割为凸多边形。这里便涉及凹多边形判断和凹多边形分割算法。

凹多边形判别

对于多边形的判别，可以利用向量叉积来判断。

假设有两向量a，b。当aXb<0时（X就表示叉乘），b对应的线段在a的顺时针方向；当aX\b=0时，a、b共线；当aXb>0时，b在a的逆时针方向。

根据凸多边形的定义，凸多边形的每条邻边的必定具有相同的时针方向，因此，我们可以为多边形的每一条边建立一个向量，通过相邻边向量叉积运算来判断多边形凹凸性，凸多边形的所有边的向量叉积均同号，因此一个多边形的所有边向量的叉积结果不同号,则可判定其为凹多边形。

有了思路后要实现代码就很简单了：

/**
 * // 判断是否为凹多边形
 * @param vexs 多边形顶点数组
 */
function isConcavePoly(vexs: polygonVex): boolean {
    // prev: 上两邻边间叉乘结果；cur当前两邻边叉乘结果
    let prev: number, cur: number;

    // 遍历所有顶点
    for(let i = 1, len = vexs.length; i < len - 1; i++) {
            // 向量v1 = 当前顶点 - 上一顶点
        let v1 = Vector.sub(vexs[i], vexs[i - 1]),
            // 向量v2 = 下一顶点 - 当前顶点
            v2 = Vector.sub(vexs[i + 1], vexs[i]);

        // 计算两邻边向量叉积：若不为负则记为1，为负则记为-1
        cur = Vector.cor(v1, v2) >= 0? 1: -1;

        // 若当前两邻边叉积结果与上两邻边结果不同号，即可判断为凹多边形
        if(prev !== undefined && prev !== cur) {
            return true;
        }
        
        prev = cur;
    }

    // 不是凹多边形
    return false;
}   

凹多边形分割

多边形的分割要比判别要难一些。判断到一个多边形为凹多边形后，则要将凹多边形分割为多个凸多边形。分割凹多边形可以利用旋转分割法。


旋转分割法的思想是沿多边形边的逆时针方向，逐一将顶点V移动到坐标系原点，然后顺时针旋转多边形，使下一个顶点V落在X轴上,如果再下一个顶点V位于X轴下面,则多边形为凹，然后我们利用X轴将多边形分割成两个新多边形，并且对着两个新多边形重复测试，一直重复到所有顶点均经过测试。

上面提到过，向量叉积可以判断两线的相对位置，因此，我们同样也可以利用向量叉积判断点与x轴的位置关系。下面放代码：

/**
 * 将凹多边形分割为多个凸多边形(旋转分割法)
 * @param vexs 多边形顶点
 */ 
export function divideConcavePoly(vexs: polygonVex): polygonVex[] {
    // 分割多边形结果集，将拆分出来的多边形保存到这个数组
    let polygonList: polygonVex[] = [];

    let i, j, len = vexs.length,
        flag = false;

    // polygon1和polygon2分别保存分割出来的两个多边形，polygon1初始化为原多边形，polygon2为空
    let polygon1 = <polygonVex>arrayDeepCopy(vexs), polygon2 = [];

    // 遍历所有顶点
    for(i = 0, len = vexs.length; i < len - 2; i++) {
            // 将当前顶点和下一个顶点的连线向量作为x轴
        let vAxis = Vector.sub(vexs[i + 1], vexs[i]), 
            // 当前顶点和下下顶点的连线向量
            v = Vector.sub(vexs[i + 2], vexs[i]);

        // 若发现下下个顶点在x轴下方
        if(Vector.cor(vAxis, v) < 0) {
            // 遍历余下的顶点
            for(j = i + 3; j < len; j++) {
                // 找到余下的第一个不在x轴下方的顶点
                v = Vector.sub(vexs[j], vexs[i]);
                if(Vector.cor(vAxis, v) > 0) {
                    // 该点即为分割点。找到分割点即跳出循环
                    flag = true;
                    break;
                }
            }

            if(flag) break;
        }
    }


    // 此时分割多边形的两个点分别为vexs[i + 1]和vexs[j]


    // 保存两个分割点
    let dp1 = polygon1[i + 1],
        dp2 = polygon1[j];

    // 从原来的多边形按照分割点分割出另一个子多边形保存到polygon2
    polygon2 = polygon1.splice(i + 2, j - (i + 2));
    // 子多边形也要补上分割点
    polygon2.unshift(dp1);
    polygon2.push(dp2);

    // 将两个子多边形加入到分割多边形结果集
    polygonList.push(polygon1);
    polygonList.push(polygon2);

    // 检测拆分出来的两个子多边形是否是凹多边形，若果是，继续递归拆分
    if(isConcavePoly(polygon1)) {
        polygonList = polygonList.concat(divideConcavePoly(polygon1));
    }
    if(isConcavePoly(polygon2)) {
        polygonList = polygonList.concat(divideConcavePoly(polygon2));
    }

    // 返回结果集
    return polygonList;
}



// 数组深拷贝
export function arrayDeepCopy<T>(arr): T {
    return arr.map(item => Array.isArray(item)? arrayDeepCopy(item): item);
}

到此我们完成了凹多边形的判别与分割，有了这些基础，我们接下来可以对之前的一些代码进行改进。

分离轴算法的改进

首先，在多边形类Polygon中，我们在构造函数中加入多边形的判别，那么就可以在定义多边形对象时马上可以得出该多边形的类别：

// 多边形
class Polygon extends Shape {
    // 多边形的顶点
    private vexs: polygonVex;
    // 是否为凹多边形
    private isConcavePoly: boolean;
    // 子多边形列表
    private polygonList: polygonVex[];

    constructor(x: number, y: number, vexs: polygonVex) {
        super(x, y);

        this.vexs = vexs;
        // 判断多边形类型
        this.isConcavePoly = isConcavePoly(this.vexs);

        // 若是凹多边形，则进行分割
        if(this.isConcavePoly) {
            this.polygonList = divideConcavePoly(this.vexs);
        }
    }
}

到现在我们的分离轴算法可以支持凹多边形的碰撞检测了，由上面可知，凹多边形其实是由多个子凸多边形组成，那么只要在遇到凹多边形时遍历凹多边形的子多边形，对子多边形进行检测即可，只要有其中一个子多边形发生碰撞即可判断该多边形发生了碰撞。但是现在，我们的碰撞分类要分得更细。这里我们新加一个polygonContact函数，用作检测有多边形参与的碰撞。

// 检测有多边形参与的碰撞
function PolygonContact(obj1: Shape, obj2: Shape): boolean {
    let polygonList1 = [],
        polygonList2 = [];

    // 若obj1为多边形
    if(obj1 instanceof Polygon) {
        // 若obj1为凹多边形，则保存其子多边形列表到polygonList1
        if(obj1.isConcavePoly) {
            polygonList1 = obj1.polygonList;
        }
        // 若是凸多边形，为了方便运算，将其整个多边形视作一个子多边形，所以polygonList只有一个元素
        else {
            polygonList1 = [obj1.vexs];
        }
    }

    // 同上
    if(obj2 instanceof Polygon) {
        if(obj2.isConcavePoly) {
            polygonList2 = obj2.polygonList;
        }
        else {
            polygonList2 = [obj2.vexs];
        }
    }

    // 若obj1为圆形，obj2为多边形
    if(obj1 instanceof Circle && obj2 instanceof Polygon) {
        // 遍历obj2的子多边形，检测碰撞
        return polygonList2.some(polyItem => SAT(polyItem, obj1.circleInfo));
    }
    // 若obj2为圆形，obj1为多边形
    else if(obj1 instanceof Polygon && obj2 instanceof Circle) {
        // 遍历obj1的子多边形，检测碰撞
        return polygonList1.some(polyItem => SAT(polyItem, obj2.circleInfo));
    }
    // 若obj1和obj2都为多边形，则双重循环检测
    else {
        return polygonList1.some(polyItem1 => polygonList2.some(polyItem2 => SAT(polyItem1, polyItem2)));
    }
}

最后，我们修改SATDetection函数：

function SATDetection(obj1: Shape, obj2: Shape): boolean {
    // 若两个图形都是圆形，然后直接调用circleContact快速判断
    if(obj1 instanceof Circle && obj2 instanceof Cricle) {
        return circleContact(obj1, obj2);
    }
    // 至少一个为多边形
    else {
       return PolygonContact(obj1, obj2);
    }
}  

总结

至此，我们的碰撞检测系统便可以说是基本完成了。对于简单图形的输入，都可以输出一个布尔值代表碰撞与否。但是要真正达到达到商业级碰撞检测系统，还有很长一段的距离，还有很多工作需要完成。比如：

• 图形相交深度计算

• 图形相交的处理

• 碰撞边计算

• 碰撞法线计算

• 碰撞点的寻找

• 碰撞类型（边-边碰撞，边-角碰撞，角-角碰撞）分类

• 静态碰撞的判断和特殊处理

• 性能优化

• 更多图形支持

等等。现在的系统只能检测两个简单图形是否碰撞，但是想要获得真实的碰撞反馈还需要上述工作的支持。这个碰撞检测系统是我的毕业设计的其中一部分，并且为了分享我修改了一部分代码，而且上述提到的工作在我的毕设中也基本实现了，但最终仍达不到我想要的效果。我说这么多其实想表达的是，要实现一个’‘基本能用’‘的物理引擎，并不是一件简单的事情，这是我做完我的毕设的感受，我当时选题时低估了其难度。难在什么地方呢？1：数学基础不够；2：力学物理基础不够；3：冷门，相关的文献，书籍都太少，可参考的东西不多，遇到难题基本都要靠自己摸索。而且，我做的这只是2D环境，若要做3D环境难度还会指数级增长，一个2D图形只能绕Z轴旋转，但一个3D图形能有无数个旋转轴，这就涉及到四元数的相关知识。。。

说的这些，只为感慨。以后若有时候，我会再去继续完善我的这个项目，让其能达到’‘基本能用’‘吧。

[Sefur]

isConcavePoly函数里面，似乎少了第一个点前后两条边组成的向量叉积判断，这样会漏掉凹点是第一个点的情况

[h1063135843]

不太行，在某些情况下，两个割点形成的分割线会有部分在原始多边形外部，也就是说这种割法割出的多边形，面积总和会增加