Finding The Fuzzy Middle

It has been quite some time since I wrote about one of my longest running projects, MovieLandmarks . The UI hasn’t changed much in the intervening years. But the backend has been rewritten in Go, and the covers now come from TMDB instead of IMDB .

Recently I decided I wanted the map to open to a view of the landmarks related to the move being passed to it using the #mv-XXXX hash. Up until now I have just opened it centered on Las Angeles.

I could have used one of the google map API functions to find the center of a group of landmarks, but I wanted more control over it than that would provide, and I don’t actually serve up the movie to landmark mapping as json since all of that is already in the html that is generated by the Go program.

So I went looking for geographic center formulas. The naive way to do it is to average the positions together, but then you end up with problems when crossing 0/360° so that won’t work. I found a really nice blog post from Carto which explains the math, and includes SQL to implement it. So I implemented that in Go and ran some movies through it. Some of them looked ok, others were really, really bad. Like Friends , and Fletch .

Friends, All Landmarks

Friends consists of 5 landmarks. 3 in New York, one in California, and the last in London. The math tells us the center is just a bit off the coast of Nova Scotia (the purple marker on the maps). Which is technically correct, but not really helpful when you load it up and are staring at water and no landmarks. Like this:

Friends, Geographic center

// CalculateCenter takes a list of landmarks and returns the center
func CalculateCenter(landmarks []ml.Landmark) (float64, float64) {
	if len(landmarks) == 1 {
		return landmarks[0].Latitude, landmarks[0].Longitude
	}

	// Center of Latitude (+/-90) is just the average
	// Center of Longitude
	// 180 * atan2(zeta, xi) / pi
	// zeta = avg(sin(pi * lng / 180)) or sum(...) may be faster for larger datasets
	// xi = avg(cos(pi * lng / 180)) or sum(...)     "       "

	var zeta float64
	var xi float64
	var avgLat float64
	for _, lm := range landmarks {
		zeta += math.Sin(math.Pi * lm.Longitude / 180)
		xi += math.Cos(math.Pi * lm.Longitude / 180)

		avgLat += lm.Latitude
	}
	avgLat = avgLat / float64(len(landmarks))
	avgLng := 180 * math.Atan2(zeta, xi) / math.Pi

	return avgLat, avgLng
}

So the next tweak is to weigh each landmark using some criteria in order to adjust it to a more pleasing result. I decided to use the distance from each landmark to the geographic center and weigh them based on that. I used the Haversine formula to calculate the distance. And of course this didn’t help a whole bunch because further landmarks had more weight, as you can see here the yellow marker really isn’t anywhere nearby:

Friends, Weighted center

But if you weight them by the inverse of the distance it makes the closer landmarks a stronger influence and the weighted center is closer to your naive expectations. But still not very good, as the green marker shows:

Friends, Inverse weighted center

// CalculateDistance returns the distance between 2 points.
func CalculateDistance(lat1, lng1, lat2, lng2 float64) float64 {
	rLat1 := math.Pi * lat1 / 180
	rLat2 := math.Pi * lat1 / 180
	dLat := math.Pi * (lat2 - lat1) / 180
	dLng := math.Pi * (lng2 - lng1) / 180

	a := math.Sin(dLat/2)*math.Sin(dLat/2) +
		math.Cos(rLat1)*math.Cos(rLat2)*
			math.Sin(dLng/2)*math.Sin(dLng/2)
	return EARTH * 2 * math.Atan2(math.Sqrt(a), math.Sqrt(1-a))
}

// CalculateWeightedCenter takes a list of landmarks and returns the center
func CalculateWeightedCenter(landmarks []ml.Landmark) (float64, float64) {
	if len(landmarks) == 1 {
		return landmarks[0].Latitude, landmarks[0].Longitude
	}

	cLat, cLng := CalculateCenter(landmarks)

	var zeta float64
	var xi float64
	var avgLat float64
	var sumW float64
	for _, lm := range landmarks {
		w := CalculateDistance(lm.Latitude, lm.Longitude, cLat, cLng)
		if w == 0 {
			continue
		}

		// Weight by inverse of distance
		w = 1.0 / w

		sumW += w

		zeta += w * math.Sin(math.Pi*lm.Longitude/180)
		xi += w * math.Cos(math.Pi*lm.Longitude/180)

		avgLat += w * lm.Latitude
	}
	avgLat = avgLat / sumW
	avgLng := 180 * math.Atan2(zeta, xi) / math.Pi

	if math.IsNaN(avgLat) || math.IsNaN(avgLng) {
		return cLat, cLng
	}

	return avgLat, avgLng
}

The final trick is to iterate over the list of landmarks and their distances from the inverse weighted center, and remove the further ones until they all fall within some limit (I used 10km). This finally results in a nice place to open the map:

Friends, New Tab

// CalculateClusterCenter returns the center of the closest cluster of landmarks
func CalculateClusterCenter(landmarks []ml.Landmark) (cLat float64, cLng float64) {
	// Make a map so it's easier to remove landmarks from the list
	cluster := make(map[int]ml.Landmark, len(landmarks))
	for i := range landmarks {
		cluster[i] = landmarks[i]
	}

	// Calculate the weighted center until remaining landmarks are 'close enough' or
	// there is only one
	for len(cluster) > 1 {
		lms := make([]ml.Landmark, 0)
		for i := range cluster {
			lms = append(lms, cluster[i])
		}
		cLat, cLng = CalculateWeightedCenter(lms)

		// Calculate the distance from each landmark to the new weighted center
		dcs := make(map[int]float64, len(cluster))
		for i := range cluster {
			dist := CalculateDistance(cluster[i].Latitude, cluster[i].Longitude, cLat, cLng)
			dcs[i] = dist
		}

		// Which one is furthest?
		furthest := 0
		closest := 0
		for i := range dcs {
			if dcs[i] > dcs[furthest] {
				furthest = i
			}
			if dcs[i] < dcs[closest] {
				closest = i
			}
		}

		if dcs[furthest] < 10000 {
			break
		}
		delete(cluster, furthest)
	}

	if len(cluster) == 1 {
		for i := range cluster {
			cLat = cluster[i].Latitude
			cLng = cluster[i].Longitude
		}
	}

	return cLat, cLng
}

I now use all of this to generate a list of fuzzy centers for each movie, and when the page is first opened (or reloaded) with a #mv-XXXX it will jump directly to the correct location. See it in action with Blues Brothers , Goonies , etc.