判断多边形与多边形是否相交的方法，代码来自于OpenLayers。

by · 2019-04-03

在做GIS开发时，常常需要用到空间判断的算法。比如：判断地图中的多边形与多边形是否相交。我在项目中具体的需求就是如此，需要过滤某个区域的瓦片地图。先把瓦片地图反向解析成Envolope，然后和该区域进行比对，再做其他处理。

　　其实在已经有开源的东西GDAL+GEOS可以使用，由于编译(nmake)GEOS对于C#程序员是一件不容易的事情。因为GEOS是C++实现的，网上虽然有别人已经编译好的DLL和LIB，但是始终不能引入到ASP.NET的项目中。没时间继续研究怎么把GEOS应用到C#项目中了，就选择了开源的JS框架OpenLayers。

　　OpenLayers中确实有我需要的几何判断的方法，所以就把它的代码剥离成一个JavaScript的函数。发博，以供有类似需求的童鞋使用。

复制代码
<!DOCTYPE html>
<html>
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
        <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
        <meta name="apple-mobile-web-app-capable" content="yes">
        <title>Polygon intersect Polygon validate Example</title>
        
        <link rel="stylesheet" href="http://openlayers.org/dev/theme/default/style.css" type="text/css">
        <link rel="stylesheet" href="http://openlayers.org/dev/examples/style.css" type="text/css">
        <script src="http://openlayers.org/dev/OpenLayers.js"></script>
        <script src="intersectPolygon.js"></script>
        <script type="text/javascript">
            var map, vectors, controls;
            function init(){
                map = new OpenLayers.Map('map');
                var wms = new OpenLayers.Layer.WMS( "OpenLayers WMS",
                    "http://vmap0.tiles.osgeo.org/wms/vmap0?", {layers: 'basic'});
    
                // allow testing of specific renderers via "?renderer=Canvas", etc
                var renderer = OpenLayers.Util.getParameters(window.location.href).renderer;
                renderer = (renderer) ? [renderer] : OpenLayers.Layer.Vector.prototype.renderers;

                vectors = new OpenLayers.Layer.Vector("Vector Layer", {
                    renderers: renderer
                });

                map.addLayers([wms, vectors]);
                map.addControl(new OpenLayers.Control.LayerSwitcher());
                map.addControl(new OpenLayers.Control.MousePosition());

                controls = {
                    point: new OpenLayers.Control.DrawFeature(vectors,
                                OpenLayers.Handler.Point),
                    line: new OpenLayers.Control.DrawFeature(vectors,
                                OpenLayers.Handler.Path),
                    polygon: new OpenLayers.Control.DrawFeature(vectors,
                                OpenLayers.Handler.Polygon),
                    drag: new OpenLayers.Control.DragFeature(vectors)
                };

                for(var key in controls) {
                    map.addControl(controls[key]);
                }

                map.setCenter(new OpenLayers.LonLat(0, 0), 3); 

                controls.polygon.activate();
            }
 
 

            // get polygon rings
            function getRings (index) {
                var features = map.layers[1].features;
                var polygon1 = features[index];
                var cpts = polygon1.geometry.components;
                var ret=[];
                for (var i = 0; i < cpts.length; i++) {
                    var linearRings = cpts[i].components;
                    for (var j = 0; j < linearRings.length; j++) {
                        var point = linearRings[j];
                        ret.push({x:point.x, y:point.y});
                    };
                };
                return ret;
            }

            function clearPolygon () {
                var features = map.layers[1].features;
                for (var i = features.length - 1; i >= 0; i--) {
                    features[i].destroy();
                };
            }


            function main(){ 
                try{
                    var r1 = getRings(0);
                    var r2 = getRings(1);
                    var flag = intersectsPolygonAndPolygon(r1, r2);
                    alert("两个面的相交情况为："+flag);
                }catch(ex){
                    alert('请先绘制两个面，点击test按钮，验证是否相交！');
                }
            }
        </script>
    </head>
    <body onload="init()">
        <h1 id="title">Polygon intersect Polygon validate Example</h1>


        <div id="map" class="smallmap"></div>
        
        <div id="controls"> 
            <input type="button" value="clear" onclick="clearPolygon();">
            <input type="button" value="test" onclick="main();">
        </div>

    </body>
</html>
复制代码

复制代码
//#region 验证两个面是否相交的算法
function intersectsPolygonAndPolygon (polygon1LinearRings, polygon2LinearRings) {
     
    // polygon1LinearRings : array[LinearRing,...]
    function intersectsByPolygon (polygon1LinearRings, polygon2LinearRings) {
        var intersect = false;

        intersect = intersectsByLinearRings(polygon1LinearRings, polygon2LinearRings);

        if(!intersect) {
            // check if this poly contains points of the ring/linestring
            for(i=0, len=polygon2LinearRings.length; i<len; ++i) {
                var point = polygon2LinearRings[i];
                intersect = containsPointByLinearRing(point, polygon1LinearRings);
                if(intersect) {
                    break;
                }
            }
        }
     
        return intersect;
    }

    // LinearRings
    function containsPointByPolygon (point, LinearRings) {
        var numRings = LinearRings.length;
        var contained = false;
        if(numRings > 0) {
            contained = containsPointByLinearRing(point, LinearRings[0]);
            if( numRings > 1) {
                // check interior rings
                var hole;
                for(var i=1; i<numRings; ++i) {
                    hole = containsPointByLinearRing(point, LinearRings[i]);
                    if(hole) {
                        if(hole === 1) {
                            // on edge
                            contained = 1;
                        } else {
                            // in hole
                            contained = false;
                        }                            
                        break;
                    }
                }
            }
        }
        return contained;
    }

    // LinearRing : array[pt]
    // point : {x:1,y:2}
    function containsPointByLinearRing (point, LinearRing) {

        //limitSigDigs
        function approx(num, sig) {
            var fig = 0;
            if (sig > 0) {
                fig = parseFloat(num.toPrecision(sig));
            }
            return fig;
        } 

        var digs = 14;
        var px = approx(point.x, digs);
        var py = approx(point.y, digs);
        function getX(y, x1, y1, x2, y2) {
            return (y - y2) * ((x2 - x1) / (y2 - y1)) + x2;
        }

        var numSeg = LinearRing.length - 1;
        var start, end, x1, y1, x2, y2, cx, cy;
        var crosses = 0;

        for(var i=0; i<numSeg; ++i) {
            start = LinearRing[i];
            x1 = approx(start.x, digs);
            y1 = approx(start.y, digs);
            end = LinearRing[i + 1];
            x2 = approx(end.x, digs);
            y2 = approx(end.y, digs);
            
            if(y1 == y2) {
                // horizontal edge
                if(py == y1) {
                    // point on horizontal line
                    if(x1 <= x2 && (px >= x1 && px <= x2) || // right or vert
                       x1 >= x2 && (px <= x1 && px >= x2)) { // left or vert
                        // point on edge
                        crosses = -1;
                        break;
                    }
                }
                // ignore other horizontal edges
                continue;
            }
            cx = approx(getX(py, x1, y1, x2, y2), digs);
            if(cx == px) {
                // point on line
                if(y1 < y2 && (py >= y1 && py <= y2) || // upward
                   y1 > y2 && (py <= y1 && py >= y2)) { // downward
                    // point on edge
                    crosses = -1;
                    break;
                }
            }
            if(cx <= px) {
                // no crossing to the right
                continue;
            }
            if(x1 != x2 && (cx < Math.min(x1, x2) || cx > Math.max(x1, x2))) {
                // no crossing
                continue;
            }
            if(y1 < y2 && (py >= y1 && py < y2) || // upward
               y1 > y2 && (py < y1 && py >= y2)) { // downward
                ++crosses;
            }
        }

        var contained = (crosses == -1) ?
            // on edge
            1 :
            // even (out) or odd (in)
            !!(crosses & 1);

        return contained;
    }


    function intersectsByLinearRings (LinearRing1, LinearRings2) {
        var intersect = false;
            var segs1 = getSortedSegments(LinearRing1); 
            var segs2 = getSortedSegments(LinearRings2); 
     
            var seg1, seg1x1, seg1x2, seg1y1, seg1y2,
                seg2, seg2y1, seg2y2;
            // sweep right
            outer: for(var i=0, len=segs1.length; i<len; ++i) {
                seg1 = segs1[i];
                seg1x1 = seg1.x1;
                seg1x2 = seg1.x2;
                seg1y1 = seg1.y1;
                seg1y2 = seg1.y2;
                inner: for(var j=0, jlen=segs2.length; j<jlen; ++j) {
                    seg2 = segs2[j];
                    if(seg2.x1 > seg1x2) {
                        // seg1 still left of seg2
                        break;
                    }
                    if(seg2.x2 < seg1x1) {
                        // seg2 still left of seg1
                        continue;
                    }
                    seg2y1 = seg2.y1;
                    seg2y2 = seg2.y2;
                    if(Math.min(seg2y1, seg2y2) > Math.max(seg1y1, seg1y2)) {
                        // seg2 above seg1
                        continue;
                    }
                    if(Math.max(seg2y1, seg2y2) < Math.min(seg1y1, seg1y2)) {
                        // seg2 below seg1
                        continue;
                    }
                    if(segmentsIntersect(seg1, seg2)) {
                        intersect = true;
                        break outer;
                    }
                }
            } 
        return intersect;
    }

    function getSortedSegments(points) {
        var numSeg = points.length - 1;
        var segments = new Array(numSeg), point1, point2;
        for(var i=0; i<numSeg; ++i) {
            point1 = points[i];
            point2 = points[i + 1];
            if(point1.x < point2.x) {
                segments[i] = {
                    x1: point1.x,
                    y1: point1.y,
                    x2: point2.x,
                    y2: point2.y
                };
            } else {
                segments[i] = {
                    x1: point2.x,
                    y1: point2.y,
                    x2: point1.x,
                    y2: point1.y
                };
            }
        }
        // more efficient to define this somewhere static
        function byX1(seg1, seg2) {
            return seg1.x1 - seg2.x1;
        }
        return segments.sort(byX1);
    }

     function segmentsIntersect(seg1, seg2, options) {
        var point = options && options.point;
        var tolerance = options && options.tolerance;
        var intersection = false;
        var x11_21 = seg1.x1 - seg2.x1;
        var y11_21 = seg1.y1 - seg2.y1;
        var x12_11 = seg1.x2 - seg1.x1;
        var y12_11 = seg1.y2 - seg1.y1;
        var y22_21 = seg2.y2 - seg2.y1;
        var x22_21 = seg2.x2 - seg2.x1;
        var d = (y22_21 * x12_11) - (x22_21 * y12_11);
        var n1 = (x22_21 * y11_21) - (y22_21 * x11_21);
        var n2 = (x12_11 * y11_21) - (y12_11 * x11_21);
        if(d == 0) {
            // parallel
            if(n1 == 0 && n2 == 0) {
                // coincident
                intersection = true;
            }
        } else {
            var along1 = n1 / d;
            var along2 = n2 / d;
            if(along1 >= 0 && along1 <= 1 && along2 >=0 && along2 <= 1) {
                // intersect
                if(!point) {
                    intersection = true;
                } else {
                    // calculate the intersection point
                    var x = seg1.x1 + (along1 * x12_11);
                    var y = seg1.y1 + (along1 * y12_11);
                    intersection = { 'x':x, 'y':y };
                }
            }
        }
        if(tolerance) {
            var dist;
            if(intersection) {
                if(point) {
                    var segs = [seg1, seg2];
                    var seg, x, y;
                    // check segment endpoints for proximity to intersection
                    // set intersection to first endpoint within the tolerance
                    outer: for(var i=0; i<2; ++i) {
                        seg = segs[i];
                        for(var j=1; j<3; ++j) {
                            x = seg["x" + j];
                            y = seg["y" + j];
                            dist = Math.sqrt(
                                Math.pow(x - intersection.x, 2) +
                                Math.pow(y - intersection.y, 2)
                            );
                            if(dist < tolerance) {
                                intersection.x = x;
                                intersection.y = y;
                                break outer;
                            }
                        }
                    }
                    
                }
            } else {
                // no calculated intersection, but segments could be within
                // the tolerance of one another
                var segs = [seg1, seg2];
                var source, target, x, y, p, result;
                // check segment endpoints for proximity to intersection
                // set intersection to first endpoint within the tolerance
                outer: for(var i=0; i<2; ++i) {
                    source = segs[i];
                    target = segs[(i+1)%2];
                    for(var j=1; j<3; ++j) {
                        p = {x: source["x"+j], y: source["y"+j]};
                        result = distanceToSegment(p, target);
                        if(result.distance < tolerance) {
                            if(point) {
                                intersection = { 'x':p.x, 'y':p.y }; 
                            } else {
                                intersection = true;
                            }
                            break outer;
                        }
                    }
                }
            }
        }
        return intersection;
    };

    function distanceToSegment(point, segment) {
        var result = distanceSquaredToSegment(point, segment);
        result.distance = Math.sqrt(result.distance);
        return result;
    };

    function distanceSquaredToSegment(point, segment) {
        var x0 = point.x;
        var y0 = point.y;
        var x1 = segment.x1;
        var y1 = segment.y1;
        var x2 = segment.x2;
        var y2 = segment.y2;
        var dx = x2 - x1;
        var dy = y2 - y1;
        var along = ((dx * (x0 - x1)) + (dy * (y0 - y1))) /
                    (Math.pow(dx, 2) + Math.pow(dy, 2));
        var x, y;
        if(along <= 0.0) {
            x = x1;
            y = y1;
        } else if(along >= 1.0) {
            x = x2;
            y = y2;
        } else {
            x = x1 + along * dx;
            y = y1 + along * dy;
        }
        return {
            distance: Math.pow(x - x0, 2) + Math.pow(y - y0, 2),
            x: x, y: y,
            along: along
        };
    }

    return intersectsByPolygon(polygon1LinearRings, polygon2LinearRings);
}
//#endregion
复制代码

　　　　　　　　　　　　　　　　[图1] 相交的情况。

　　　　　　　　　　　　　　　　[图2] 不相交的情况。

 

本示例采用HTML+JAVASCRIPT编写，如需要源码请点击 例子 下载。

转载自：https://blog.csdn.net/u011001084/article/details/53336106

相关推荐

Tags:

You may also like...

公众号

微信群

人数过多只能拉人进群;

加我好友yu389741

微信小程序