Google Maps: Center Of Gravity

Last update: 2008-03-17 (see comments)

The problem
The week's coming to an end, you desperately want to meet your friends for a beer (or two). But with over 250 bars in Amsterdam to choose from, where should you meet? Let's say you want to minimize the distance that everyone has to travel to the bar. So you'd want to find the bar nearest to the Center of Gravity or Center of Mass (wikipedia) of everybodies location...

How about a website that lets you pinpoint the location of all your friends, shows you the geographical center and lets you search for nearby bars?


Solutions already out there
Brammeleman already solved the hardest part of this problem, whilst trying to find the best location for his family reunion. Brammeleman's php script, as discussed in his post on nerdnotes.org (in Dutch), takes in a Google Earth KLM file and calculates the geographical center of the placemarks in the KML. This point is served back as a KML file, which can than be opened in Google Earth.
Stefan Geens, implemented Brammeleman's algorithm (with slight adjustments which Brammeleman later adopted in his script), in a similar application. His post at www.oglearth.com gives all the background info on Center Of Gravity theory, so check that out if you're interested.

The juggling with KML files and the need to have Google Earth installed doesn't make this approach a viable solution to my friday night drinking problems. Every week there is a different bunch of us, and we don't always start out from the same place. I need to be able to add and adjust locations on the fly.

At www.geomidpoint.com they come close to my needs. This application lets you put in a number of cities or coordinates by hand and then calculates either the Center of Gravity or the Center of Distance. The former is the same geographical center of the given coordinates as Brammelemans algorithm calculates. The latter is the point where the total sum of distances is minimized. Check out the methods page on their site for better explanation about the difference between the two. The Center of Distance is found by a brute force algorithm and not by mathematical calculation. The result is displayed on a Google Maps map, along with the given points.

Now this is close. But still not close enough. I want to be able to search within one city instead of in between cities. Although this is technically possible by entering latitudes and longitudes for each point... it's not really user friendly.

My solutions mash-up
Since the ultimate solution wasn't yet out there, I sacrificed a weekend on building it myself.
So, I translated Brammeleman's Center Of Gravity algorithm into Javascript to whip up a client side Google Maps application. This Google Maps mashup lets you add placemarks by clicking on a map and calculates the Center Of Gravity on the fly. The search nearby form field on the left pane queries Google Maps for the bars or pizza places closest to the geographical center of all marked locations and displays the results on the map.

Additionally, you can upload a KML file or provide the url to an online file or a custom created Google Maps map ("My Maps"). The application plots the placemarks from the KML file or the "My Maps" source on the map and calculates the Center Of Gravity. You can deselect the placemarks you don't want to use for the calculation and add additional placemarks if needed.

To use a custom made Google Maps map as the source for the calculation, simply go to the My Maps area on Google Maps, select/create the map you want to use and click the "link to this page" link. The than presented link can be copied into the form field in the Center of Gravity application to load the placemarks on the map.

The source files for this application are available here.

Below is an embedded version of the Center Of Gravity application.
The fullscreen version can be found here.


All credits for the Center of Gravity algorithm go to Brammaleman, with noted additions by Stefan Geens.

Please let me know what you think by leaving a comment. You're free to use this script for your own application, but I'd appreciate it if you tell me about it. Plain curiosity :-)

For my other Google Maps trials, see this overview.

Future improvements
* Better KML support (now only few formats actually work)
* Loading of KML files through AJAX
* Placemark management (edit name/delete)
* Doubleclick zoom-in without adding a marker (annoying!)
* Optional Center of Distance calculator
* Permalink option, to be able to send the resulting map to friends