Algorithm for finding a location inside a polygon area

Hi Guys,

As we all know google map provide us API’s to customise maps according to our needs. There is also an option for creating polygons for defining specific area on the map.

What if we define a boundary on the map and wants to find out that if a marker is inside that polygon or not? For this problem google map provides a method containsLocation() which will be accessed via google.maps.geometry.poly.

But my requirement is little different i have to filter list of citizen which fall under some area boundary, so for filtering I have only one option which is, to create google map then create polygon on that map and then using containsLocation() method on polygon i’ll know that the citizen lies on that area or not. According to me this is not a good solution and also its make our application slow and our code base large.

So I searched for the best solution using math geometry to find point in a polygon, and I came across an algorithm known as Ray Casting algorithm, according to which, to find whether a point is inside or outside a polygon is to create a line from the point in any fixed direction which intersects the edges of the polygon. If the number of intersection of the edges is odd then the point is inside the polygon and if the number of intersection is even then the point is outside the polygon.

So using this algorithm I wrote a function in js to find out the solution to my problem

pointInPolygon(polygonPath, coordinates) {
        let numberOfVertexs = polygonPath.length - 1;
        let inPoly = false;
        let { lat, lng } = coordinates;

        let lastVertex = polygonPath[numberOfVertexs];
        let vertex1, vertex2;

        let x = lat, y = lng;

        let inside = false;
        for (var i = 0, j = polygonPath.length - 1; i < polygonPath.length; j = i++) {
            let xi = polygonPath[i].lat, yi = polygonPath[i].lng;
            let xj = polygonPath[j].lat, yj = polygonPath[j].lng;

            let intersect = ((yi > y) != (yj > y))
                && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
            if (intersect) inside = !inside;
        }

        return inside;
}            

The above function takes coordinates array of all the vertexes of polygon as a first argument and an object of coordinates of the point as a second argument and returns a boolean value, if it gives true then the point is inside the polygon otherwise outside.