# 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 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: ``````// CalculateCenter takes a list of landmarks and returns the center
func CalculateCenter(landmarks []ml.Landmark) (float64, float64) {
if len(landmarks) == 1 {
return landmarks.Latitude, landmarks.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: 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: ``````// 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.Latitude, landmarks.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: ``````// 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.