点与任意凸多边形碰撞检测源码分享

昨天看到有朋友在群里问可以可以给对象加碰撞区域数组，写了一个点与任意凸多边形碰撞的例子，采用了向量积的二分查找法，核心算法只有二十几行，比较简单，算是抛砖引玉，欢迎讨论，大家如果有高效率的多边形之间碰撞解法，欢迎讨论~

效果演示：http://pointcollidepolyshape-47609.coding.io/

注释很详细，就不多说了，直接贴代码

[mw_shl_code=javascript,true]//点与任意凸多边形碰撞检测模块
module CollisionUtils {
    //===================================================碰撞检测核心代码部分==================================================
    //实现比较简单，除去注释部分，其实只有二十几行代码
    //参数依次为： 碰撞点，碰撞多边形的坐标，碰撞多边形各个顶点坐标(多边形的局部坐标系内，传进来的顶点数组必须为凸多边形的顺时针序列顶点)
    export function checkPointCollideShape(p: egret.Point, shppos: egret.Point, szpt: Array<egret.Point>): boolean {
        var n: number = szpt.length;
        if (n < 3) return false;
        var i: number = 0;
        var clonept: Array<egret.Point> = [];
        for (i = 0; i < szpt.length; i++) {
            var vp = new egret.Point(szpt.x, szpt.y);
            clonept.push(vp);
        }
        //把图形的顶点坐标转换到所在坐标系（如果坐标系不同需另处理，这里只是简单实例）
        for (i = 0; i < clonept.length; i++) {
            clonept.x += shppos.x;
            clonept.y += shppos.y;
        }
        //主要原理为右手法则，逆时针向量积为正，顺时针为负
        //首先判断起点、第二点与P向量积，如果大于零，说明在外面
        if (this.vectorCrossPoint(clonept[0], p, clonept[1]) > 0) return false;
        //首先判断起点、倒数第二点与P向量积，如果小于零，说明在外面
        if (this.vectorCrossPoint(clonept[0], p, clonept[n - 1]) < 0) return false;
        //以上两个判断通过了，说明检查点在多边形起点相邻两边的开口方向
        //从第二点和倒数第二点开始收缩
        i = 2;
        var j: number = n - 1;
        var line: number = -1;
        //这里采用二分法逐渐缩小范围来判定点的位置
        while (i <= j) {
            //找到当前等待队列中的点的中点
            var mid: number = (i + j) >> 1;
            //如果点在起点与中点之间，则把终点设为中点的前一点，否则把起点设置为中点的下一点
            if (this.vectorCrossPoint(clonept[0], p, clonept[mid]) > 0) {
                line = mid;
                j = mid - 1;
            }
            else i = mid + 1;
        }
        if (line < 0) return false;
        //找到了紧挨着点的两个夹边，此时，如果在多边形内，则与夹边的积必然小于零
        return this.vectorCrossPoint(clonept[line - 1], p, clonept[line]) < 0;
    }
    export function vectorCrossPoint(p0: egret.Point, p1: egret.Point, p2: egret.Point): number {
        return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
    }
}[/mw_shl_code]


附件中有完整的VS工程包

第一次发代码，昨天弄Coding弄了一个晚上，代码死活同步不上去，今天又好了，蛋疼

这好东西就不客气的收入囊中了！
coding就是git一样，应该不难弄吧。

向量真是博大精深。我一直没研究透！！

写的不错，学习了

我要代码！！！！

哈哈，必需品~~研究下

楼主，请教一下，png图片也能适用凸多边形碰撞吗？从spritesheet拿到的PNG

ztxxxx 发表于 2014-12-25 09:45
楼主，请教一下，png图片也能适用凸多边形碰撞吗？从spritesheet拿到的PNG

我现在只写了点与多边形碰撞，多边形与多边形的碰撞有点效率问题还在优化探索中，如果你想做点与png图片你的多边形碰撞的话，可以自己给图片加一个多边形包围盒的数组，然后就和例子一样了。
不过这种方法并不是很好，之前官方是说会做图片的精确碰撞检测部分，不过是否已经可以用了我还没有尝试

赞一个～～收藏～～～

学习下！