The Problem - Part II
In a previous post, I wrote about how the Google Maps Center of Gravity Application takes care of my friday night drinking problems. Well, it doesn't anymore. My drinking buddies are so evenly spread out over town, that whoever joins for a beer to celebrate the weekend, the Center Of Gravity ends up dead center in the middle of town. We've seen all the bars, drank all the beers. It's time to broaden our look.
The Solution - Part II
What if you could mark the locations of your friends, and have Google Maps find random bars located in between those locations.
Enter the Convex Hull (wikipedia). "The convex hull may be easily visualized by imagining an elastic band stretched open to encompass the given points; when released, it will assume the shape of the required convex hull."
Or, even more easily, play around with the Convex Hull - Random Search application I whipped up. Below is an embedded version of the application. The fullscreen version can be found here.
Credits for the algorithm go entirely to InfoEcho.net. See this post for the original javascript sourcecode and an online working example.
All I did was rewrite the code so it can be used with geographical locations in a google maps application, and create/add a random-search-in-polygon script. The latter is a set of generic functions that can be used with any gmaps polygon.
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 :-)
The source code can be found here.
For my other Google Maps trials, see this overview.
Hi this is great and thanks for the script. It has opened a whole new area for me. A couple of comments: The script seems to check the degrees distance and not the true distance. So the hull falls over, over large distances and over the 180 degree line (I would suggest that the GLatLng.distanceFrom method should be used). Also I noticed that the actual polygon returned has two identical points for each corner on the Polygon. Once again thanks for this code, it will be a great building block for me. GISTIN
ReplyDelete@Justin:
ReplyDeleteYou are right, the script should use the true distance. I will implement your GLatLng.distanceFrom suggestion as soon as I get around upgrading the script. The algorithm was translated from a 2 dimensional mathematical model, whereas the the gmaps version should use a geoid model.
I'm not sure your suggestion will fix the "falling over" problem, I have a feeling this is caused by the way the Google Maps API plots large scale polygons. Not specifically when the polygon crosses the 180 degrees line, but if the polygon stretches more than half way around the globe. The Api chooses the shortest distance, while this may not result in intended polygon. But I might be wrong.
Another known issue with plotting large scale polygons is that the Google Maps api draws straight lines by default, while in this case it should actually draw "Great Circle" lines. If you draw a large triangular polygon in either of the pole regions, and move a fourth placemark around its edge, it will sometimes appear outside of the convex hull (which is impossible, by definition a convex hull contains all the given points), while in real life it will be inside. If the polygon was drawn 'properly', the lines would appear curved on the map. The solution to this is to set the polyline geodesic mode to 'true':
var polyOptions = {geodesic:true};
See the google maps api documentation for details: http://tinyurl.com/59bube
I will implement this also, in the upcomming upgrade of this application.
About the two identical points for each vertex of the returned polygon, I never noticed this. But it sounds like a silly and easily fixed bug. I'll look into it.
Thanks for the feedback! If you ever build a real life Google Maps application that uses a convex hull, let me know! I'm not sure I can think of one...
Yes this is used in real life, by many biologists. They would know it as "extent of occurrence" and it is used to calculate the range of a plant or animal. It is also used as part of the red listing (how endanger it is) of a species.
ReplyDeleteOuch, being a biologist I guess I should have known. Although in my field, urban ecology, occurrences hardly ever 'extend' municipal boundaries ;-)
ReplyDeleteManufacturing Convex Hulls is an easy task for the human eye/brain so I imagine in most biological research it is done by hand. An algorithm that calculates convex hulls from point sets would only be of interest in automated processes or on large multidimensional datasets. I'm guessing you deal a lot with GIS applications that might want to automate the calculation of convex hulls?
Calculating home ranges of individual animals tracked with gps transmitters and monitor if they overlap (mating season) would be an obvious application.
Still, I doubt the algorithm will ever find itself useful in a client side Javascript/GoogleMaps application...
Thanks for the insight!
Talking about Biology. I have used your code in Flash to display GBIF primary data. As described before the idea was to convert the points into actual distribution polygons, but this fails when you have a wide distribution in different continents... You can check it out at:
ReplyDeletehttp://biodivertido.blogspot.com/2008/06/convex-hull-over-gbif-points.html
And yes, I am suffering too the problems of not using a geodesic model, search for Puma concolor and clik on the the +.
Javier, your app looks great!
ReplyDeleteNice to see that the algorithm is put to use in Biological contexts.
One way to deal with the problem of wide distributions in different continents could be to make/find polygons that repesent the land masses of the continents, and intersect them with the calculated convex hull polygon. For marine species the "exclusive" intersect should be used. A nice resource for intersec/clipping algorithms, including some pics that illustrate this idea nicely, can be found here:
http://www.cs.man.ac.uk/~toby/alan/software/
Another idea would be not to take the convex hull, but a concave hull. But since there's not only one, but more concave hulls for a given pointset, the resulting polygon is very arbitrary and depends on the algorithm used. You could go for a brute-force approach and select the concave hull which results in the smallest area, out of all the concave hulls for a given pointset. With increasing pointsets though, the computation time will increase exponentially, possibly rendering this method useless.
Either way, you would have to ask yourself what the resulting polygon represents. The polygon in no way predicts the distribution of the species, especially with wide distributions and small datasets.
Hi Erie,
ReplyDeleteYou are totally right. Thanks. To me this looks more like a "funny representation" than anything else. I dont think that any automatically way of deriving distribution from just points. If you want you can check also another test using Heat Maps at:
http://biodivertido.blogspot.com/2008/08/gbif-data-heat-maps-heat-maps-over.html
While I am now more convinced is on the use of grid displays and using chorophlet colorizing for example. In this case you also somehow "imagine" the known distribution while staying correct with the data you have.
I have been visiting various blogs for my term papers writing research. I have found your blog to be quite useful. Keep updating your blog with valuable information... Regards
ReplyDeleteThanks dude, exactly what I was looking for. You made my day! cheers
ReplyDelete