多边形相交判断算法

一、规则

判断两多边形是否相交，排除边边重合、以及断点与边重合的情况

二、示意图

三、算法代码（js）

/**
     * 判断两个多边形是否相交（边边重合，点边重合除外）
     * 核心算法：1-快速排除算法 2-矢量叉乘跨立算法 3-射线算法
     *
     * @param polygon1
     * @param polygon2
     */
    function intersectsPolygonAndPolygonNew(polygon1, polygon2) {
        // 两多边形是否相交标记
        var _ifIntersect;
        // 经纬度转换成平面坐标
        var polygon1Points = pathConvert(polygon1);
        var polygon2Points = pathConvert(polygon2);
        // 快速排除法判断是否相交
        _ifIntersect = fastExclude(polygon1Points, polygon2Points);
        if (_ifIntersect == false) {
            return _ifIntersect;
        }
        // 获取线段集合
        var _polygon1Segs = getSegs(polygon1Points);
        var _polygon2Segs = getSegs(polygon2Points);

        // 跨立法判断相交
        _ifIntersect = judgeIntersect(_polygon1Segs, _polygon2Segs);
        if(_ifIntersect) {
            return _ifIntersect;
        }else {
            // 判断是否包含
            var _containPointNum = 0;
            for (var i = 0; i < polygon1Points.length - 1; i++) {
                var _ifContain = judgePointInPolygon(polygon1Points[i], _polygon2Segs);
                if (_ifContain) {
                    _containPointNum++;
                }
            }
            if (_containPointNum == polygon1Points.length - 1) {
                return _ifIntersect = true;
            } else {
                return _ifIntersect = false;
            }
        }

        // 获取多边形线段集合
        function getSegs(points) {
            var _segs = [];
            for (var i = 0; i < points.length - 1; i++) {
                var _element1 = points[i];
                var _element2 = points[i + 1];
                _segs.push({x1: _element1.x, y1: _element1.y, x2: _element2.x, y2: _element2.y});
            }
            return _segs;
        }
    }

    /**
     * 快速排除算法：初步判断多边形是否相交
     *
     * @param polygon1Points
     * @param polygon2Points
     */
    function fastExclude(polygon1Points, polygon2Points) {
        // 多边形1最大X坐标
        var _polygon1MaxX;
        // 多边形1最大Y坐标
        var _polygon1MaxY;
        // 多边形1最小X坐标
        var _polygon1MinX;
        // 多边形1最小Y坐标
        var _polygon1MinY;

        // 多边形2最大X坐标
        var _polygon2MaxX;
        // 多边形2最大Y坐标
        var _polygon2MaxY;
        // 多边形2最小X坐标
        var _polygon2MinX;
        // 多边形2最小Y坐标
        var _polygon2MinY;

        for (var i = 0; i < polygon1Points.length; i++) {
            var _polygon1Point = polygon1Points[i];
            _polygon1MaxX = _polygon1MaxX > _polygon1Point.x ? _polygon1MaxX : _polygon1Point.x;
            _polygon1MinX = _polygon1MinX < _polygon1Point.x ? _polygon1MinX : _polygon1Point.x;
            _polygon1MaxY = _polygon1MaxY > _polygon1Point.y ? _polygon1MaxY : _polygon1Point.y;
            _polygon1MinY = _polygon1MinY < _polygon1Point.y ? _polygon1MinY : _polygon1Point.y;
        }

        for (var i = 0; i < polygon2Points.length; i++) {
            var _polygon2Point = polygon2Points[i];
            _polygon2MaxX = _polygon2MaxX > _polygon2Point.x ? _polygon2MaxX : _polygon2Point.x;
            _polygon2MinX = _polygon2MinX < _polygon2Point.x ? _polygon2MinX : _polygon2Point.x;
            _polygon2MaxY = _polygon2MaxY > _polygon2Point.y ? _polygon2MaxY : _polygon2Point.y;
            _polygon2MinY = _polygon2MinY < _polygon2Point.y ? _polygon2MinY : _polygon2Point.y;
        }

        if (_polygon1MaxX <= _polygon2MinX || _polygon2MaxX <= _polygon1MinX || _polygon1MinY >= _polygon2MaxY || _polygon2MinY >= _polygon1MaxY) {
            return false;
        } else {
            return true;
        }
    }

    /**
     * 跨立算法：
     * 利用矢量叉乘的物理意义判断两线段是否相交
     *
     * 有向量 a，b，c
     * 若 (a*b)*(b*c) = 0 则两线段重合
     * 若 (a*b)*(b*c) < 0 则两线段相交
     * 若 (a*b)*(b*c) > 0 则两线段不相交
     *
     * @param polygon1Segs
     * @param polygon2Segs
     */
    function judgeIntersect(polygon1Segs, polygon2Segs) {
        var _ifIntersect;
        math.config({
            number: 'BigNumber'
        });
        for (var i = 0; i < polygon1Segs.length; i++) {
            var polygon1Seg = polygon1Segs[i];
            for (var j = 0; j < polygon2Segs.length; j++) {
                var polygon2Seg = polygon2Segs[j];
                // 向量1
                var _vector1 = new vector(math.parser().eval(polygon2Seg.x2 + "-" + polygon2Seg.x1), math.parser().eval(polygon2Seg.y2 + "-" + polygon2Seg.y1));
                // 向量2
                var _vector2 = new vector(math.parser().eval(polygon1Seg.x1 + "-" + polygon2Seg.x1), math.parser().eval(polygon1Seg.y1 + "-" + polygon2Seg.y1));
                // 向量3
                var _vector3 = new vector(math.parser().eval(polygon1Seg.x2 + "-" + polygon2Seg.x1), math.parser().eval(polygon1Seg.y2 + "-" + polygon2Seg.y1));
                // 向量_vector2与_vector1叉乘的解
                var _calculationVal1 = math.parser().eval(_vector2.x + "*" + _vector1.y + "-" + _vector1.x + "*" + _vector2.y);
                // 向量_vector3与_vector1叉乘的解
                var _calculationVal2 = math.parser().eval(_vector3.x + "*" + _vector1.y + "-" + _vector1.x + "*" + _vector3.y);

                // 向量4
                var _vector4 = new vector(math.parser().eval(polygon1Seg.x2 + "-" + polygon1Seg.x1), math.parser().eval(polygon1Seg.y2 + "-" + polygon1Seg.y1));
                // 向量5
                var _vector5 = new vector(math.parser().eval(polygon2Seg.x1 + "-" + polygon1Seg.x1), math.parser().eval(polygon2Seg.y1 + "-" + polygon1Seg.y1));
                // 向量6
                var _vector6 = new vector(math.parser().eval(polygon2Seg.x2 + "-" + polygon1Seg.x1), math.parser().eval(polygon2Seg.y2 + "-" + polygon1Seg.y1));
                // 向量_vector5与_vector4叉乘的解
                var _calculationVal3 = math.parser().eval(_vector5.x + "*" + _vector4.y + "-" + _vector4.x + "*" + _vector5.y);
                // 向量_vector6与_vector4叉乘的解
                var _calculationVal4 = math.parser().eval(_vector6.x + "*" + _vector4.y + "-" + _vector4.x + "*" + _vector6.y);

                if (_calculationVal1 * _calculationVal2 < 0 && _calculationVal3 * _calculationVal4 < 0) {
                    return _ifIntersect = true;
                }
            }
        }
        return _ifIntersect = false;

        // 向量对象，因为是同一平面线段，所以省略Z坐标
        function vector(x, y) {
            this.x = x;
            this.y = y;
        }
    }

    /**
     * 射线法判断点是否在多边形内
     * 点射线（向右水平）与多边形相交点的个数为奇数则认为该点在多边形内
     * 点射线（向右水平）与多边形相交点的个数为偶数则认为该点不在多边形内
     *
     * @param point
     * @param polygonSegs
     */
    function judgePointInPolygon(point, polygonSegs) {
        debugger
        // 是否在多边形内
        var _ifContain;
        // 点坐标
        var _X = point.x;
        var _Y = point.y;
        // 交点个数
        var _intersecNum = 0;
        // 判断射线与多边形的交点个数
        for (var i = 0; i < polygonSegs.length; i++) {
            var _seg = polygonSegs[i];
            var _maxY = _seg.y1 < _seg.y2 ? _seg.y2 : _seg.y1;
            var _minY = _seg.y1 < _seg.y2 ? _seg.y1 : _seg.y2;
            if (_Y > _minY && _Y < _maxY) {
                math.config({
                    number: 'BigNumber'
                });
                // 计算交点X坐标
                var intersecPointX = math.parser().eval("(" + _seg.x1 + "*" + _seg.y2 + "-" + _seg.x2 + "*" + _seg.y1 + "-" + "(" + _seg.x1 + "-" + _seg.x2 + ")" + "*" + _Y + ")" + "/" + "(" + _seg.y2 + "-" + _seg.y1 + ")");
                _X <= intersecPointX ? _intersecNum++ : _intersecNum + 0;
            }
        }
        return _intersecNum % 2 == 0 ? _ifContain = false : _ifContain = true;
    }