Grid-Based Geographic Search Coverage

When searching for data across a large geographic area, a single search point won't give you complete coverage. The solution is grid-based geographic search coverage — a systematic approach that divides large areas into smaller searchable cells.

This article explains how the grid system works and how we use OpenStreetMap's Nominatim API to fetch area boundaries.

---

Why Use a Grid System?

Location-based searches return results within a radius of a single point. If you search from one location, you'll only get results near that point — not the entire area you're interested in.

The grid-based approach solves this by:

1. Fetching the exact boundary of your target area using Nominatim
2. Dividing that boundary into a grid of smaller cells
3. Using each cell's center as an independent search point

---

Fetching Area Boundaries with Nominatim

Before generating a grid, you need the exact geographic boundaries of your target area. OpenStreetMap's Nominatim API provides this for free.

What is Nominatim?

Nominatim is OpenStreetMap's geocoding service. Given a place name like "Manhattan, New York," it returns:

• Geographic coordinates (latitude/longitude)
• Bounding box (north, south, east, west boundaries)
• Administrative details (country, state, city)

Implementation

import httpx
from dataclasses import dataclass

@dataclass
class AreaBoundary:
    name: str
    north: float  # Maximum latitude
    south: float  # Minimum latitude
    east: float   # Maximum longitude
    west: float   # Minimum longitude


def get_area_boundary(area_name: str):
    """
    Fetch area boundary from Nominatim API.
    """
    url = "https://nominatim.openstreetmap.org/search"
    params = {
        "q": area_name,
        "format": "json",
        "limit": 1,
    }
    headers = {"User-Agent": "MyApp/1.0"}

    with httpx.Client(timeout=30.0) as client:
        response = client.get(
            url,
            params=params,
            headers=headers
        )
        response.raise_for_status()
        data = response.json()

    if not data:
        raise ValueError(f"No results for: {area_name}")

    bbox = data[0]["boundingbox"]

    return AreaBoundary(
        name=area_name.split(",")[0],
        north=float(bbox[1]),
        south=float(bbox[0]),
        east=float(bbox[3]),
        west=float(bbox[2]),
    )

Example Usage

boundary = get_area_boundary("Manhattan, New York")

print(f"Area: {boundary.name}")
print(f"North: {boundary.north:.4f}")  # ~40.8820
print(f"South: {boundary.south:.4f}")  # ~40.6803
print(f"East: {boundary.east:.4f}")    # ~-73.9070
print(f"West: {boundary.west:.4f}")    # ~-74.0479

This tells us Manhattan spans roughly:

• 22km north-to-south
• 12km east-to-west

---

Grid Generation

With boundaries in hand, the next step is dividing the area into cells.

Core Concepts

Grid Cell — A square geographic area defined by its center point (latitude, longitude) and radius.

Cell Size — The width/height of each cell in meters. Smaller cells = more thorough coverage. Larger cells = fewer cells to process.

Coordinate Math — Converting between meters and degrees requires accounting for Earth's geometry. Longitude degrees are smaller near the poles than at the equator.

Implementation

import math
from dataclasses import dataclass
from typing import List

METERS_PER_LAT_DEGREE = 111320


@dataclass
class GridCell:
    cell_id: int
    center_lat: float
    center_lng: float
    radius_meters: int


def meters_to_lat_degrees(meters: float) -> float:
    """Convert meters to latitude degrees."""
    return meters / METERS_PER_LAT_DEGREE


def meters_to_lng_degrees(
    meters: float,
    latitude: float
) -> float:
    """
    Convert meters to longitude degrees.
    Varies by latitude (Earth is a sphere).
    """
    return meters / (
        METERS_PER_LAT_DEGREE *
        math.cos(math.radians(latitude))
    )


def generate_grid(
    boundary: AreaBoundary,
    cell_size_meters: int
) -> List[GridCell]:
    """
    Generate grid cells covering the area.
    """
    lat_step = meters_to_lat_degrees(cell_size_meters)

    cells = []
    cell_id = 0

    # Start half a cell inside the boundary
    current_lat = boundary.south + (lat_step / 2)

    while current_lat <= boundary.north:
        lng_step = meters_to_lng_degrees(
            cell_size_meters,
            current_lat
        )
        current_lng = boundary.west + (lng_step / 2)

        while current_lng <= boundary.east:
            cells.append(GridCell(
                cell_id=cell_id,
                center_lat=round(current_lat, 6),
                center_lng=round(current_lng, 6),
                radius_meters=cell_size_meters // 2,
            ))
            cell_id += 1
            current_lng += lng_step

        current_lat += lat_step

    return cells

Understanding the Math

Latitude degrees are constant — 1 degree of latitude is approximately 111.32 km everywhere on Earth.

Longitude degrees vary — 1 degree of longitude = 111.32 km x cos(latitude). At the equator, it's 111km. At 45° latitude, it's about 79km. At 60° latitude, it's only 56km.

This is why the code recalculates the longitude step for each row of cells.

Example Usage

boundary = get_area_boundary("Manhattan, New York")
cells = generate_grid(boundary, cell_size_meters=1000)

print(f"Total cells: {len(cells)}")  # ~264

for cell in cells[:3]:
    print(f"Cell {cell.cell_id}: "
          f"({cell.center_lat}, {cell.center_lng})")

For Manhattan (roughly 22km x 12km) with 1km cells:

• 22 rows (north-south)
• 12 columns (east-west)
• ~264 total cells

---

Dynamic Cell Sizing

The cell size should adapt based on the area's dimensions:

Area Dimensions	Cell Size	Use Case
< 10km	1,000m	Neighborhoods
10-30km	2,000m	Cities
30-100km	5,000m	Metro areas
100-500km	50,000m	States
> 500km	100,000m	Countries

Implementation

def calculate_cell_size(boundary: AreaBoundary) -> int:
    """
    Auto-select cell size based on area dimensions.
    """
    height_km = (boundary.north - boundary.south) * 111
    width_km = (
        (boundary.east - boundary.west) *
        111 *
        math.cos(math.radians(boundary.south))
    )

    if height_km < 10 or width_km < 10:
        return 1000   # 1km
    elif height_km < 30 or width_km < 30:
        return 2000   # 2km
    elif height_km < 100 or width_km < 100:
        return 5000   # 5km
    elif height_km < 500 or width_km < 500:
        return 50000  # 50km
    else:
        return 100000 # 100km

---

Summary

The grid system combined with Nominatim provides a powerful way to systematically cover any geographic area:

1. Nominatim fetches accurate boundaries for any named location
2. Grid generation divides the area into manageable cells
3. Dynamic sizing adapts cell size based on area dimensions
4. Coordinate math handles Earth's spherical geometry

This approach scales from small neighborhoods to entire countries, ensuring complete geographic coverage for any location-based task.