Don't worry, you don't have to watch the whole hour. I have to say, I've seen _most of it (sorry, Mehdi, I'm a busy girl) and can assure you that the mathematics presented are not at all challenging, if you are math-phobic. If you want to skip around a bit, I would recommend beginning to watch at about the 8 minute mark (nice discussion of spatial data querying), or beginning at the 11 minute mark, for a very good discussion of what is Voronoi (and ignore the comments from the audience by the guy who clearly does not understand basic geometry, and the lady who likes to hear herself talk). MS does a lovely job of describing the Voronoi cell as "capturing the concept of closeness" and the points p as "a force forcing something outward". That point of equal force could then come to define a boundary of each irregular polygon. I found the video very informative. Starting at about the 17 minute mark he gives a good example of Voronoi diagramming applied to GIS (with some variation).
And just in case you just haven't gotten enough Voronoi awesomeness, here is a totally trippy video clip:
The music is either from an old video game, or a really terrible low-budget corporate training video.
 |
| Damn. Now I really want to watch Office Space again. |
And, finally, I found a super-cool image of the United States rendered with each state as a Voronoi-generated polygon with each state capitol serving as point p. My thanks to Scholars' Lab for the post, which I would recommend for you to read. Click each image to imbiggen.
 |
| Ordinary USA |
 |
| Voronoi States of America! |
 |
| And now in Stereo! |
Now here's what I want to know-- how do you adapt a Voronoi GIS query to incorporate topography? If anyone has an answer, or knows of some good places to look, please let me know.
Now, I don't understand your question completely, but the Voronoi concept you are talking about is very much related to 'Christaller's Central Place Theory'.Go through the math behind theory's model. It may give you some Idea.
ReplyDeleteBTW, I really like those US maps. specially the one in Stereo!:)
wow. my hands are so shaking that I cannot properly type-- I got a comment! I didn't think anyone read this thing! ^_^
ReplyDeleteokay, Foram, my question at the end (which, it is true, I could have voiced better) was this-- how do you incorporate 3D realities into a 2D locational/Voronoi query? Now, in a place like Manhattan, topography doesn't figure much, but if you are in Afghanistan or Romania or Colorado, the location of, say, a big freaking mountain is going to have a big impact on your best fit scenario path from point A to point B. So is there a Voronoi diagram that incorporates topographic changes when assigning paths?
I have many rules for living. Potteiger Rule #1: Don't leave your shit. Ever. Potteiger Rule #17: A person who looks reasonably good dry will look spectacular wet. Potteiger Rule #32: When in doubt, take the hypotenuse. Unless it is uphill.
See, my rule takes landscape into account. I just wonder if there is a way to translate that to path selection.
Once again, thank you for reading!
You can generalize the Voronoi algorithm to use a different distance metric instead of the ordinary Euclidean distance. For example, see Voronoi/Worley noise: http://www.gamedev.net/community/forums/topic.asp?topic_id=576541
ReplyDeleteBut in your question, the distance metric (or cost) is asymmetric: the distance from A to B is not the same as that from B to A.
Unfortunately, a Google search for Voronoi "asymmetric distance metric" leads to http://www.math.cmu.edu/~howell4/teaching/cvt.pdf - which is a bit hairy.
thank you, nodename!
ReplyDelete