A radius on a map becomes half degree cells, and the only hard parts are the pole and the antimeridian

Nakodo's business campaigns look for local businesses to partner with, which means a customer draws a circle: this town, within 20km, or this whole country. Somewhere under that is a dataset of places that has to be loaded into our database before anything can search it.

Loading "a circle" is not a thing you want to do twice. Two customers both looking around Manchester should cost one import, and a customer who widens from 15km to 25km should not re-import the middle. So the circle is not the unit of work. Grid cells are:

const CELL = 0.5; // degrees
const cellKey = (lat0: number, lng0: number) => `cell:${lat0},${lng0}`;

Half a degree is about 55km north to south, and the keys are shared by every campaign in the product. The whole design is one sentence: snap the request to a grid, and let the grid be the cache.

Longitude needs a cosine, and the cosine needs a clamp

Latitude is easy, because a degree of latitude is the same distance everywhere:

const KM_PER_DEGREE = 111.32;
const dLat = radiusKm / KM_PER_DEGREE;

Longitude is not. A degree of longitude is 111.32km at the equator and zero at the poles, scaled by the cosine of the latitude:

const dLng = radiusKm / (KM_PER_DEGREE * Math.max(0.05, Math.cos((lat * Math.PI) / 180)));

Without the cosine, a 20km radius in Oslo covers about half the longitude span it should, and the cells on the east and west of the circle are silently missing. With the cosine and nothing else, a campaign centred near a pole divides by a number approaching zero and asks for every cell on the planet.

Math.max(0.05, ...) caps the stretch at twenty times. It is not a correct model of anything. It is a statement that above about 87 degrees we would rather be wrong in a bounded way, and the business case for "every cafe within 20km of the North Pole" has not come up.

The latitude bound has its own small lie:

const north = Math.min(90 - CELL, lat + dLat);

90 is not a valid cell start, because a cell runs from its start to start plus 0.5. The last cell begins at 89.5.

The loop that crosses the antimeridian

This is the bit that looks over engineered until the first customer picks Fiji:

for (let lat0 = cellStart(south); lat0 <= north; lat0 += CELL) {
  for (let i = Math.floor((lng - dLng) / CELL); i * CELL <= lng + dLng; i++) {
    // Wrap across the antimeridian.
    const lng0 = ((((i * CELL + 180) % 360) + 360) % 360) - 180;
    out.push({ key: cellKey(lat0, lng0), bbox: [lng0, lat0, lng0 + CELL, lat0 + CELL] });
  }
}

The loop variable is an index, not a longitude. That is the whole trick. A circle around 179.8E runs from 179.5 to 180.3, which does not exist as a longitude, but does exist perfectly well as an index range. The value is only converted back to a real longitude inside the body, where the wrap happens.

The conversion itself is the usual dance for a language whose % is remainder rather than modulo: shift into 0 to 360, take the remainder, add 360 and take it again to make a negative result positive, shift back. (-190 + 180) % 360 is -10 in JavaScript, and ((-10) + 360) % 360 is 350, which maps back to 170. Without the second modulo, every campaign west of the Greenwich meridian would get keys that do not match the ones a campaign east of it produces for the same ground.

And a deliberate inaccuracy, written down in the comment:

// The cells a circle overlaps (its bounding box, so a few corners too).

This takes the bounding box of the circle, not the circle. Four corner cells per request contain ground outside the radius. That is fine, and trying to be exact would be worse: the corner cells are shared with the neighbouring campaigns, the actual distance filter happens later against real coordinates, and a cell loaded once is cheaper than a clever test run on every lookup.

Countries skip the grid entirely

export function areasFor(locations: CampaignLocation[]): Area[] {
  const areas = new Map<string, Area>();
  for (const l of locations) {
    if (l.lat !== null && l.lng !== null && l.radiusKm !== null) {
      for (const a of cellsAround(l.lat, l.lng, l.radiusKm)) areas.set(a.key, a);
    } else if (l.bbox) {
      areas.set(`country:${l.countryCode}`, { key: `country:${l.countryCode}`, bbox: l.bbox, countryCode: l.countryCode });
    }
  }
  return [...areas.values()];
}

A country is one area with one key, not several hundred cells. The area keeps a bounding box, because that is what the import query needs, but it also carries the country code, and the query adds a condition on the address country so places inside the box and over a border are left out. The key is the reason it is worth the special case: country:FR is shared by every campaign that says France, where a set of cells approximating France would be shared with nobody and re-derived slightly differently each time.

The Map keyed by area key is doing quiet work too. A campaign with three locations in the same metro area produces overlapping cell sets, and they collapse before anything is requested.

Cells are imported in blocks of sixteen

One import per half degree cell would be a lot of runs for a 50km radius. So missing cells are grouped:

const BLOCK = 4; // cells per side read in one import run (2 degrees)
const block = `${Math.floor(lat0 / (CELL * BLOCK))},${Math.floor(lng0 / (CELL * BLOCK))}`;

A block is a 2 degree square, up to sixteen cells, and the import request is the union bounding box of the cells actually missing in that block:

const bbox: Bbox = [
  Math.min(...cells.map((c) => c.bbox[0])),
  Math.min(...cells.map((c) => c.bbox[1])),
  Math.max(...cells.map((c) => c.bbox[2])),
  Math.max(...cells.map((c) => c.bbox[3])),
];

Not the block's own bounds. If three cells in a corner of a block are missing, the request covers those three, and the twelve cells already in the database are not fetched again.

Blocks are fixed to the grid rather than derived from the request, which is what makes them stable: the same ground always falls in the same block, however the customer drew their circle, so two campaigns that each need part of a block produce requests that overlap predictably rather than arbitrarily.

Freshness is a property of the source, not a guess:

const FRESH_DAYS = 35;

The dataset publishes monthly, so 35 days is one publication cycle plus slack. A shorter window would re-import identical data; a longer one would hold a stale month after a release.

What I would tell myself before starting

Three things, in the order I learned them:

1. Pick the unit of caching before the unit of request. Everything above follows from deciding that the grid cell is the thing that is stored, loaded and shared. The circle is only ever an input.
2. Write the inaccuracies down where the code is. The corner cells, the 0.05 cosine clamp and the 90 - CELL bound are all approximations, and all three read as bugs to anybody who has not been told they are not.
3. Wrap with indices, not values. Any time a coordinate has a seam, loop over something that has no seam and convert at the last moment.

If you want to see what sits on top of all this, the business campaigns section of how Nakodo works describes what a brand actually does with an area full of places, and our page for small businesses is the non technical version of why a brand would want the shop two towns over in the first place.