Find latitude/longitude from collection

Balasaheb Molawade 136 Reputation points
2024-08-31T12:59:59.2433333+00:00

Hi,

We have developed an application to identify a location that falls within specific boundaries.

To achieve this, we have stored all US postal codes, and to represent boundaries, we use a collection of latitude/longitude coordinates, similar to the format shown below:

38.9014,-76.9653|38.90146,-76.9651|38.90155,-76.9649|38.9020,-76.96442 .....

The application includes a text box where users can input an address or latitude/longitude. They want to see which US postal code this address or coordinate belongs to. To determine this, we read all postal code boundaries and check if the provided location lies within any of them. However, this process can sometimes take longer because we loop through each postal code boundary one by one.

Is there a more efficient way to determine if a latitude/longitude pair belongs to a specific area, allowing us to narrow the search instead of checking against all US postal codes? For example, when we enter an address in New York, we want some logic based on our above format that identifies it as belonging to the Eastern region. If possible, could you provide sample code for this?

Thanks!

Azure Maps
Azure Maps
An Azure service that provides geospatial APIs to add maps, spatial analytics, and mobility solutions to apps.
700 questions
0 comments

1 answer

Sort by: Most helpful
Most helpful Newest Oldest
  1. rbrundritt 17,491 Reputation points Microsoft Employee
    2024-08-31T17:45:53+00:00

    There are many different ways to achieve this.

    1. The simplest is to use the existing services in Azure Maps. If the user searches for a postal code or lower entity (e.g. address), the response from the search service will likely include the postal code already. If the user passes in a coordinate, then use the reverse geocoding service and it will return the street address (if the coordinate is near a road) and include the postal code. This will likely be the fastest option and use the least amount of memory, but would mean that if your app doesn't already do reverse geocoding, it would generate new costs. If you then want the boundary, you can either get it from the Azure Maps boundary service, or you could do a simple text match on the postal code, assuming you have that in the data with your boundary data.
    2. A common approach to quickly filtering through polygon data is to have the bounding box of those polygons precalculated. Then a simple test to see if a coordinate is within a bounding box can be done quickly and then you would end up with a small subset of polygons that you would need to fully parse and test for intersection.
    3. If all you have is an array of delimited polygon boundary strings like what you provided and no bounding box info, and don't want to modify your data, a similar filtering approach would be to only parse out the first coordinate of each polygon (substring), then calculate the distance from your search coordinate to this coordinate. This would do a radial search. If the distance is less than longest cross-sectional distance of any US postal code (our max required radius), the polygon that does intersect will be in the filtered polygon list. In the US, the largest zip code is 89049 and has a cross-sectional distance of about 190 miles. If we round this up to 200 miles to be same, then this should filter down the list of polygons fairly quickly, however on the east cost you will likely still have a decent number of polygons (maybe a couple hundred), but this will still be a lot faster than parsing and testing all polygons. Below is a simple example of how to do this (assuming your polygons are simple and have a single ring). It uses no external library so you can bring this into any web app you want. To run this, simply save as html file, open in browser, and look open dev console to see the test output:
    <html>
<head>
<title></title>
</head>
<body>
<script>
var earthRadiusMiles = 3959;
var searchRadiusMiles = 200;

//Polygon boundary strings with format like 38.9014,-76.9653|38.90146,-76.9651|38.90155,-76.9649|38.9020,-76.96442 
var polygons = [
	"40.80367,-74.03819|40.78481,-74.04684|40.78231,-74.02345|40.79867,-74.00083|40.81252,-74.00006|40.82003,-74.01888|40.80367,-74.03819",
	"40.78308,-74.04607|40.76768,-74.05065|40.77711,-74.07251|40.74727,-74.07658|40.74727,-74.04862|40.75016,-74.02116|40.76499,-74.03336|40.78135,-74.01786|40.78308,-74.04607"
];

//Filter the polygons, only capture the index of the polygon rather than the polygon string. This will keep memory usage low as we will only have one copy of the polygon data in memory.
function radialFilter(latitude, longitude){
	var filtered = [];
	
	//Loop through all polygons, parse the first coordinate out and calculate the distance to determine if the polygon is within the search radius.
	for(var i = 0;i<polygons.length;i++){
		var coordString = polygons[i].substr(0, polygons[i].indexOf('|'));
		var parts = coordString.split(',');
		
		var d = haversine(latitude, longitude, parseFloat(parts[0]), parseFloat(parts[1]));
		
		if(d <= searchRadiusMiles) {
			filtered.push(i);
		}
	}
	
	return filtered;
}

//Calculate straight line distance using Haversine formula.
function haversine(lat1, lon1, lat2, lon2) {
	//Convert to radians;
    lat1 = lat1 * Math.PI / 180;
	lon1 = lon1 * Math.PI / 180;
	lat2 = lat2 * Math.PI / 180;
	lon2 = lon2 * Math.PI / 180;
	
	var dLat = lat2 - lat1;
	var dLon = lon2 - lon1;
	var a = Math.sin(dLat / 2) * Math.sin(dLat /2) + Math.sin(dLon / 2) * Math.sin(dLon /2) * Math.cos(lat1) * Math.cos(lat2);
	var c = 2 * Math.asin(Math.sqrt(a));
	return earthRadiusMiles * c;
}

//Simply point in polygon function to test if a coordinate is within a single polygon ring.
function isPointInPolygon(lat, lon, polygon) {
    let isInside = false;

    for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
        const [lat1, lon1] = polygon[i];
        const [lat2, lon2] = polygon[j];

        const intersects = (lon1 > lon) !== (lon2 > lon) &&
            lat < (lat2 - lat1) * (lon - lon1) / (lon2 - lon1) + lat1;

        if (intersects) isInside = !isInside;
    }

    return isInside;
}

function Test(searchLat, searchLon) {	
	//Figure out which polygons are near our search location.
	var filteredIndices = radialFilter(searchLat, searchLon);
	
	console.log(`Found ${filteredIndices.length} polygons when filtering.`);
	
	var foundMath = false;
	
	//Now, loop through the filtered indices, parse the polygon, and do an intersection test.
	for(var i = 0; i < filteredIndices.length; i++){
		var polygon = polygons[filteredIndices[i]];
		
		//Add your parsing and intersection test logic here. Throwing in placeholders here.
		var coords = polygon.split('|').map(c => c.split(',')).map(p => [parseFloat(p[0]), parseFloat(p[1])])
		
		var intersects = isPointInPolygon(searchLat, searchLon, coords);
		
		//We only need to find the first one that intersects.
		if(intersects){
			console.log(`Found intersecting polygon at index ${filteredIndices[i]}`);
		
			//Do something with the polygon result.
			
			foundMath = true;
			
			//Break out of the loop as we don't need to search anymore.
			break;
		}
	}
	
	if(!foundMath){
		console.log(`No intersecting polygon found`);
	}
}

console.log('First test: 40.78077, -74.05751 (should not intersect with any polygon)');
Test(40.78077, -74.05751);

console.log('Second test: 40.765376, -74.0504 (should intersect with second polygon (index 1)');
Test(40.765376, -74.0504);
</script>
</body>
</html>

    Side note, zip codes are often not simply polygons, but multi-polygons (represent multiple disconnected areas). Not sure if there is more to your data format than just pipe delimited, but that is something you might want to think about if you don't handle this already.

    1 person found this answer helpful.

Your answer

Answers can be marked as Accepted Answers by the question author, which helps users to know the answer solved the author's problem.