JS implementation determines whether the point is within the polygon range

One 、 explain

stay GIS field , It is a basic method to judge whether the point is within the polygon range , Here we mainly talk about the implementation principle .

The principle is simple , There is one GIS theory , A point sends rays in one direction , If the intersection point of the ray and each edge of the polygon is odd, it means that the point is within the scope of the polygon .

 

( The picture is quoted from ：https://blog.csdn.net/qq_27161673/article/details/52973866)

 

Two 、 Implementation code

So the implementation code is very clear , Any point creates a ray to the right , Why is the right side , Because the horizontal line can be maintained y unchanged , This situation is the simplest and better understood . The implementation code is as follows ：

        // Determine whether the point is within the polygon range 
        function queryPtInPolygon(point, polygon) {
            var p1, p2, p3, p4;

            p1 = point;
            p2 = { x: 1000000000000, y: point.y };

            var count = 0;
            // Compare each edge to the ray 
            for (var i = 0; i < polygon.length - 1; i++) {
                p3 = polygon[i];

                p4 = polygon[i + 1];
                if (checkCross(p1, p2, p3, p4) == true) {
                    count++;
                }
            }
            p3 = polygon[polygon.length - 1];

            p4 = polygon[0];
            if (checkCross(p1, p2, p3, p4) == true) {
                count++;
            }

            return (count % 2 == 0) ? false : true;

            // Judge whether two line segments intersect 
            function checkCross(p1, p2, p3, p4) {
                var v1 = { x: p1.x - p3.x, y: p1.y - p3.y },
                v2 = { x: p2.x - p3.x, y: p2.y - p3.y },

                v3 = { x: p4.x - p3.x, y: p4.y - p3.y },
                v = crossMul(v1, v3) * crossMul(v2, v3);

                v1 = { x: p3.x - p1.x, y: p3.y - p1.y };
                v2 = { x: p4.x - p1.x, y: p4.y - p1.y };

                v3 = { x: p2.x - p1.x, y: p2.y - p1.y };
                return (v <= 0 && crossMul(v1, v3) * crossMul(v2, v3) <= 0) ? true : false;

            }

            // Calculate the vector cross product 
            function crossMul(v1, v2) {
                return v1.x * v2.y - v1.y * v2.x;
            }
        }
    }

Examples of use

var point={x:10,y:10};
var polygon=[{x:0,y:0},{x:100,y:0},{x:100,y:100},{x:0,y:100},{x:0,y:0}];
	
var pts=queryPtInPolygon(points,polygon); //pts That is, the set of points intersecting the polygon , If it is judged as an odd number, it means that it is within the polygon range 

　　

Test case download address ：https://download.csdn.net/download/jiangfei200809/9213835