Improve algorithm to find the N closest cities to current location

[amaury1093]

Summary

The current algorithm for find the N closest cities to the current location is very naive. We could optimize it.

Problem Definition

If you go to the page of a city (example here), there's a ranking section, which shows the 6 closest cities to the current location, and their cigarettes information.

The current algorithm to calculate these closest cities is the following:

• We have a hardcoded list of 1000 cities, and their GPS, name and air quality information. This list can be found here: https://raw.githubusercontent.com/shootismoke/cities/master/all.json
• Gatsby loads these 1000 cities at build time:

  webapp/gatsby-node.js

  Lines 9 to 12 in dee5ac1

  	// Download cities data from our remote API.
  	const populatedCities = await fetch(
  	'https://raw.githubusercontent.com/shootismoke/cities/master/all.json'
  	).then((r) => r.json());

• The RankingSection loads all cities using useStaticQuery:

  webapp/src/components/RankingSection/RankingSection.tsx

  Line 54 in dee5ac1

  const worldCities = useStaticQuery(graphql`

• It then calculates the haversine distances between the current location and all the 1000 cities:

  webapp/src/components/RankingSection/RankingSection.tsx

  Lines 86 to 93 in dee5ac1

  	// We naively calculate the distance from our current city to all the
  	// other cities in the database.
  	const distances = worldCities
  	.map((city) => ({
  	city,
  	distance: haversine(currentCity.gps, city.gps),
  	}))
  	.filter(({ distance }) => distance !== 0) // Remove current city.

• We then sort these distances, and take the first N cities:
  

  webapp/src/components/RankingSection/RankingSection.tsx

  Lines 98 to 104 in dee5ac1

  	// We then sort the distances.
  	distances.sort((a, b) => a.distance - b.distance);
  	// We take the CITIES_TO_SHOW first cities.
  	const citiesToShow = distances
  	.slice(0, CITIES_TO_SHOW)
  	.map(({ city }) => city);

This algorithm is not optimal (O(n^2)). It's okay for 1000 cities, but there are surely better way to find the closest N cities around the current location.

Potential Solutions

• data structures such as r-tree, quad-tree or k-d tree

[marvinody]

This may not solve it for all cases, but if you want a quick solution, you could potentially add a filter right after calculating size to only include cities within X units ( 50 miles, 100 km, whatever you want). It doesn't "in theory" reduce it to a small amount, but in practice we know a set of coordinates is only going to be close to some small set of cities.
You may end up with less than 6 so I'm not sure if that's suitable for you but just another potential solution that goes a different way entirely.