Find pushpin in ploygons

Question

 

Hi Team,

 We have stored a collection of coordinates (latitude/longitude) for polygons in a specific field (column). These coordinates are associated with multiple polygons spread across various records, totaling approximately 100 rows. Now, we have a requirement to search for pushpins based on their latitude and longitude coordinates to determine if they reside within any of the polygons. Currently, our approach involves fetching all polygons and individually checking if each pushpin lies within any of the polygons. While this method does work, it is time-consuming. We are seeking to optimize the solution for this requirement.

Here is the format of the coordinates.

 Does anyone have a solution or ideas for optimizing this.

Thanks!

Answer 1

Thanks for your reply.

We store coordinates in an SQL database, and since we do not have direct access to the database, we use a Web API to retrieve those coordinates. After fetching those coordinates using the web API, we loop through each coordinate and check if pushpins (with the following latitude and longitude 44.3043, -86.01501)  lie within those coordinates. We store coordinates in text format, as shown below.

43.955648661089114,-86.46308800835779||43.95540158970585,-86.45055896877852||43.95552512552589,-86.43717177580342||43.95614280077381,-86.43288100882422||43.95638986907524,-86.41503141819075||43.955278053629016,-86.39838324231145||43.956266335052945,-86.37864571420714||43.95542780312437,-86.33896260854519

We have used the code below to determine if the pushpin lies within a polygon of coordinates.

 

int i = 0;

int j = points.Count - 1;

bool inPoly = false;

 

for (i = 0; i < points.Count; i++)

{

if (points[i].Longitude < lon && points[j].Longitude >= lon || points[j].Longitude < lon && points[i].Longitude >= lon)

{

if (points[i].Latitude + (lon - points[i].Longitude) / (points[j].Longitude - points[i].Longitude) * (points[j].Latitude - points[i].Latitude) < lat)

{

inPoly = !inPoly;

 

}

}

j = i;

}

return inPoly;

Hope this information helps. Please let us know your response.

Thanks!

Answer 2

> Data is stored in a SQL database, but don't have direct access to it. You use a Web API to retrieve the coordinates, then loop through them to see if they are within each polygon. There is a large collection of coordinates. You are using **Bing Maps.**


If you had access to the database, the data could be stored using geometry or geography objects, and a point in polygon query could be done on millions of points in a very quickly as all data in the database would be spatially indexed. Besides being faster at processing, it would also mean less data being sent through a web API which would provide additional performance. If you have an API you could do this filtering on the server side using an intermediate web service. This would be faster than filtering the data on the client and would also limit the amount of data being sent to the client, but there would be added costs associated with hosting a service for this. Depending on the size of the polygon data, the download time when that information isn't cache may end up being longer than the time it takes to filter the points, so it's worth considering the balance of cost and performance you are willing to make. 

If you must do this processing in JavaScript, you won't have a spatial index to speed things up. Since you have a lot of points and polygons, implementing some sort of method to quickly check if a polygon is even remotely close to your point can help speed things up. A common method is to first calculate bounding boxes for each polygon, then checking to see if the point is in the bounding box. This is a simple set of comparisons that doesn't require a loop and will allow you to skip the deeper intersection test of each polygon for each point.  

In the little bit of code you provided it appears that you have already parsed the polygon into an array of `Location` objects. I'm assuming that you may be displaying the polygons on the map, and thus you need the coordinates as these objects. If not, these polygons coordinate could be simply parsed into a 2D array to make things slightly faster (may not make much of difference, but may reduce memory usage). 

Below is a code sample that uses the bounding box filtering method to improve performance. Since I don't know what you plan to do after checking if the point is in the polygon the code below simply does a count of the points in each polygon (this could be used to power a [choropleth like display](https://samples.bingmapsportal.com/?search=choropleth&sample=choropleth-map))

```javascript
function analyze() {

    var start = Date.now();

        //Loop through each polygon, create bounding boxes the first time, and compare with each point.
    for (let i = 0, len = polygons.length; i < len; i++) {
        const polygon = polygons[i];

        //Calculate the bounding box of the polygon.
        const bbox = Microsoft.Maps.LocationRect.fromShapes(polygon);

        const polygonPoints = polygon.getRings()[0];

        let numPoints = 0;

        for (let j = 0, cnt = pushpins.length; j < cnt; j++) {
            const loc = pushpins[j].getLocation();

            //Check to see if the pushpin intersects the bounding box.
            if (bbox.contains(loc)) {
                //Point is within the bounding box of the polygon, do a deeper check and see if it is within the polygon.
                if (pointInPolygon(polygonPoints, loc.latitude, loc.longitude)) {
                    //Point is in polygon, apply custom logic. In this case just counting the point.
                    numPoints++;
                }
            }
        }

        //Add the count of intersecting points to the polygon metadata.
        polygon.metadata = { numPoints: numPoints };

        //Set the color of the polygon based on the count.
        let color = 'blue';

        if (numPoints < 2) {
            color = 'green';
        } else if (numPoints < 4) {
            color = 'yellow';
        } else if (numPoints < 6) {
            color = 'orange';
        } else if (numPoints < 8) {
            color = 'red';
        } else {
            color = 'purple';
        }

        polygon.setOptions({ fillColor: color });
    }

    var end = Date.now();

    console.log('Time to analyze: ' + (end - start) + 'ms');

    //Add the polygons to the map.
    map.entities.push(polygons);

}

function pointInPolygon(points, lat, lon) {
    var i;
    var j = points.length - 1;
    var inPoly = false;

    for (i = 0; i < points.length; i++) {
        if (points[i].longitude < lon && points[j].longitude >= lon
            || points[j].longitude < lon && points[i].longitude >= lon) {
            if (points[i].latitude + (lon - points[i].longitude) /
                (points[j].longitude - points[i].longitude) * (points[j].latitude - points[i].latitude) < lat) {
                inPoly = !inPoly;
            }
        }
        j = i;
    }
    return inPoly;
}

Here is a running version of this code where I use GeoJSON files of US counties (3429 polygons with 99K+ coordinates) and a set of US point of interests (3532 points). Note that the data is about 4MB in size, so there is some download time. I think this is a bit more data than you are using but thought it would be good to push the limits here. I know you are using string coordinates and parsing them, but that makes little difference here as the focus here is the point in polygon logic on large datasets. In terms of performance, when testing on my computer, the bounding box filtering takes less than 1.2 seconds to process, without the bounding box it takes well over 4 seconds. So, it makes it 3 to 4 times faster.

Depending on what you plan to display, you could skip the conversion of the data to Bing Maps objects initially and process the data directly (2D array of numbers for the polygon, and simply lat/lon value for points), and then inflate the results into Bing Maps shape objects once you have on the objects you need.

The Bing Maps spatial math module could be used, but since you have simple polygons (single ring), it's not really needed and not worth the extra time it would take to download it.

If you are not going to display the polygons on the map, I highly recommend using a web worker. You can call the Web API directly from the web worker, parse the polygons are a 2D array of numbers, slightly modify the logic above to work with these arrays, and do the filtering in the web worker. This would make this filtering process occur off the UI thread and provide a bit more performance and not lock up the UI thread.```

Answer 3

> Data is stored in a SQL database, but don't have direct access to it. You use a Web API to retrieve the coordinates, then loop through them to see if they are within each polygon. There is a large collection of coordinates. You are using **Bing Maps.**


If you had access to the database, the data could be stored using geometry or geography objects, and a point in polygon query could be done on millions of points in a very quickly as all data in the database would be spatially indexed. Besides being faster at processing, it would also mean less data being sent through a web API which would provide additional performance. If you have an API you could do this filtering on the server side using an intermediate web service. This would be faster than filtering the data on the client and would also limit the amount of data being sent to the client, but there would be added costs associated with hosting a service for this. Depending on the size of the polygon data, the download time when that information isn't cache may end up being longer than the time it takes to filter the points, so it's worth considering the balance of cost and performance you are willing to make. 

If you must do this processing in JavaScript, you won't have a spatial index to speed things up. Since you have a lot of points and polygons, implementing some sort of method to quickly check if a polygon is even remotely close to your point can help speed things up. A common method is to first calculate bounding boxes for each polygon, then checking to see if the point is in the bounding box. This is a simple set of comparisons that doesn't require a loop and will allow you to skip the deeper intersection test of each polygon for each point.  

In the little bit of code you provided it appears that you have already parsed the polygon into an array of `Location` objects. I'm assuming that you may be displaying the polygons on the map, and thus you need the coordinates as these objects. If not, these polygons coordinate could be simply parsed into a 2D array to make things slightly faster (may not make much of difference, but may reduce memory usage). 

Below is a code sample that uses the bounding box filtering method to improve performance. Since I don't know what you plan to do after checking if the point is in the polygon the code below simply does a count of the points in each polygon (this could be used to power a [choropleth like display](https://samples.bingmapsportal.com/?search=choropleth&sample=choropleth-map))

```javascript
function analyze() {

    var start = Date.now();

        //Loop through each polygon, create bounding boxes the first time, and compare with each point.
    for (let i = 0, len = polygons.length; i < len; i++) {
        const polygon = polygons[i];

        //Calculate the bounding box of the polygon.
        const bbox = Microsoft.Maps.LocationRect.fromShapes(polygon);

        const polygonPoints = polygon.getRings()[0];

        let numPoints = 0;

        for (let j = 0, cnt = pushpins.length; j < cnt; j++) {
            const loc = pushpins[j].getLocation();

            //Check to see if the pushpin intersects the bounding box.
            if (bbox.contains(loc)) {
                //Point is within the bounding box of the polygon, do a deeper check and see if it is within the polygon.
                if (pointInPolygon(polygonPoints, loc.latitude, loc.longitude)) {
                    //Point is in polygon, apply custom logic. In this case just counting the point.
                    numPoints++;
                }
            }
        }

        //Add the count of intersecting points to the polygon metadata.
        polygon.metadata = { numPoints: numPoints };

        //Set the color of the polygon based on the count.
        let color = 'blue';

        if (numPoints < 2) {
            color = 'green';
        } else if (numPoints < 4) {
            color = 'yellow';
        } else if (numPoints < 6) {
            color = 'orange';
        } else if (numPoints < 8) {
            color = 'red';
        } else {
            color = 'purple';
        }

        polygon.setOptions({ fillColor: color });
    }

    var end = Date.now();

    console.log('Time to analyze: ' + (end - start) + 'ms');

    //Add the polygons to the map.
    map.entities.push(polygons);

}

function pointInPolygon(points, lat, lon) {
    var i;
    var j = points.length - 1;
    var inPoly = false;

    for (i = 0; i < points.length; i++) {
        if (points[i].longitude < lon && points[j].longitude >= lon
            || points[j].longitude < lon && points[i].longitude >= lon) {
            if (points[i].latitude + (lon - points[i].longitude) /
                (points[j].longitude - points[i].longitude) * (points[j].latitude - points[i].latitude) < lat) {
                inPoly = !inPoly;
            }
        }
        j = i;
    }
    return inPoly;
}

Here is a running version of this code where I use GeoJSON files of US counties (3429 polygons with 99K+ coordinates) and a set of US point of interests (3532 points). Note that the data is about 4MB in size, so there is some download time. I think this is a bit more data than you are using but thought it would be good to push the limits here. I know you are using string coordinates and parsing them, but that makes little difference here as the focus here is the point in polygon logic on large datasets. In terms of performance, when testing on my computer, the bounding box filtering takes less than 1.2 seconds to process, without the bounding box it takes well over 4 seconds. So, it makes it 3 to 4 times faster.

Depending on what you plan to display, you could skip the conversion of the data to Bing Maps objects initially and process the data directly (2D array of numbers for the polygon, and simply lat/lon value for points), and then inflate the results into Bing Maps shape objects once you have on the objects you need.

The Bing Maps spatial math module could be used, but since you have simple polygons (single ring), it's not really needed and not worth the extra time it would take to download it.

If you are not going to display the polygons on the map, I highly recommend using a web worker. You can call the Web API directly from the web worker, parse the polygons are a 2D array of numbers, slightly modify the logic above to work with these arrays, and do the filtering in the web worker. This would make this filtering process occur off the UI thread and provide a bit more performance and not lock up the UI thread.

Answer 4

> Data is stored in a SQL database, but don't have direct access to it. You use a Web API to retrieve the coordinates, then loop through them to see if they are within each polygon. There is a large collection of coordinates. You are using **Bing Maps.**


If you had access to the database, the data could be stored using geometry or geography objects, and a point in polygon query could be done on millions of points in a very quickly as all data in the database would be spatially indexed. Besides being faster at processing, it would also mean less data being sent through a web API which would provide additional performance. If you have an API you could do this filtering on the server side using an intermediate web service. This would be faster than filtering the data on the client and would also limit the amount of data being sent to the client, but there would be added costs associated with hosting a service for this. Depending on the size of the polygon data, the download time when that information isn't cache may end up being longer than the time it takes to filter the points, so it's worth considering the balance of cost and performance you are willing to make. 

If you must do this processing in JavaScript, you won't have a spatial index to speed things up. Since you have a lot of points and polygons, implementing some sort of method to quickly check if a polygon is even remotely close to your point can help speed things up. A common method is to first calculate bounding boxes for each polygon, then checking to see if the point is in the bounding box. This is a simple set of comparisons that doesn't require a loop and will allow you to skip the deeper intersection test of each polygon for each point.  

In the little bit of code you provided it appears that you have already parsed the polygon into an array of `Location` objects. I'm assuming that you may be displaying the polygons on the map, and thus you need the coordinates as these objects. If not, these polygons coordinate could be simply parsed into a 2D array to make things slightly faster (may not make much of difference, but may reduce memory usage). 

Below is a code sample that uses the bounding box filtering method to improve performance. Since I don't know what you plan to do after checking if the point is in the polygon the code below simply does a count of the points in each polygon (this could be used to power a [choropleth like display](https://samples.bingmapsportal.com/?search=choropleth&sample=choropleth-map))

```javascript
function analyze() {

    var start = Date.now();

        //Loop through each polygon, create bounding boxes the first time, and compare with each point.
    for (let i = 0, len = polygons.length; i < len; i++) {
        const polygon = polygons[i];

        //Calculate the bounding box of the polygon.
        const bbox = Microsoft.Maps.LocationRect.fromShapes(polygon);

        const polygonPoints = polygon.getRings()[0];

        let numPoints = 0;

        for (let j = 0, cnt = pushpins.length; j < cnt; j++) {
            const loc = pushpins[j].getLocation();

            //Check to see if the pushpin intersects the bounding box.
            if (bbox.contains(loc)) {
                //Point is within the bounding box of the polygon, do a deeper check and see if it is within the polygon.
                if (pointInPolygon(polygonPoints, loc.latitude, loc.longitude)) {
                    //Point is in polygon, apply custom logic. In this case just counting the point.
                    numPoints++;
                }
            }
        }

        //Add the count of intersecting points to the polygon metadata.
        polygon.metadata = { numPoints: numPoints };

        //Set the color of the polygon based on the count.
        let color = 'blue';

        if (numPoints < 2) {
            color = 'green';
        } else if (numPoints < 4) {
            color = 'yellow';
        } else if (numPoints < 6) {
            color = 'orange';
        } else if (numPoints < 8) {
            color = 'red';
        } else {
            color = 'purple';
        }

        polygon.setOptions({ fillColor: color });
    }

    var end = Date.now();

    console.log('Time to analyze: ' + (end - start) + 'ms');

    //Add the polygons to the map.
    map.entities.push(polygons);

}

function pointInPolygon(points, lat, lon) {
    var i;
    var j = points.length - 1;
    var inPoly = false;

    for (i = 0; i < points.length; i++) {
        if (points[i].longitude < lon && points[j].longitude >= lon
            || points[j].longitude < lon && points[i].longitude >= lon) {
            if (points[i].latitude + (lon - points[i].longitude) /
                (points[j].longitude - points[i].longitude) * (points[j].latitude - points[i].latitude) < lat) {
                inPoly = !inPoly;
            }
        }
        j = i;
    }
    return inPoly;
}

Here is a running version of this code where I use GeoJSON files of US counties (3429 polygons with 99K+ coordinates) and a set of US point of interests (3532 points). Note that the data is about 4MB in size, so there is some download time. I think this is a bit more data than you are using but thought it would be good to push the limits here. I know you are using string coordinates and parsing them, but that makes little difference here as the focus here is the point in polygon logic on large datasets. In terms of performance, when testing on my computer, the bounding box filtering takes less than 1.2 seconds to process, without the bounding box it takes well over 4 seconds. So, it makes it 3 to 4 times faster.

Depending on what you plan to display, you could skip the conversion of the data to Bing Maps objects initially and process the data directly (2D array of numbers for the polygon, and simply lat/lon value for points), and then inflate the results into Bing Maps shape objects once you have on the objects you need.

The Bing Maps spatial math module could be used, but since you have simple polygons (single ring), it's not really needed and not worth the extra time it would take to download it.

If you are not going to display the polygons on the map, I highly recommend using a web worker. You can call the Web API directly from the web worker, parse the polygons are a 2D array of numbers, slightly modify the logic above to work with these arrays, and do the filtering in the web worker. This would make this filtering process occur off the UI thread and provide a bit more performance and not lock up the UI thread.```