Posted by Charlie
Last time I gave kudos to Sapphire in Steel for the addition of a Ruby console to their debugger.
This time its kudos for Arachno. Lother Scholz, the develeper, sent me an email the next day saying that the latest build now includes a Ruby console intergrated with the debugger. Excellent!
Its good to see that developer tools for Ruby are finally starting to mature - nothing like a little competition.
Posted by Charlie
In the religious war between the command line and IDE (integrated development environment), I'm firmly on the IDE side. Having said that, there's no substitute for having a console when working with a dynamic language like Ruby, or Python or JavaScript, etc.
What I really want is the two combined. I should be able to set a breakpoint in my IDE and when the breakpoint triggers have access to the standard IDE inspectors (watch window, local variables, etc.). But I also want access to a console, so I can do more sophisticated debugging when needed.
This is pretty obvious stuff - Visual Studio has had a Immediate Windows for ages where you can poke around the internals or your C++, C#, JScript or VB program. Borland's IDE's had similar functionality, although not as easy to use.
Yet its strangely lacking in the Ruby community. I've tried all the IDEs - FreeRide, Arachno (my favorite), Komodo, RDT, eric3, etc. None of them can do it. And really, its not just an IDE thing, my understanding is that the VIM Ruby integration doesn't have this either.
So kudos to Sapphire in Steel, a new plug-in that turns Visual Studio 2005 into a Ruby IDE. The integrated debugger comes complete with a Ruby console window. When you hit a breakpoint, the console is bound to the current context. So if your code set a local variable "foo" to the value 7, just type in "foo" in the console and you'll get back 7. You can do pretty much anything you want, including modifying the local variable.
Nice work - I have high hopes for the future of Sapphire in Steel.
Posted by Charlie
Update: ruby-prof 0.5.0 is now available and has significantly more features than 0.4.0, including better threading support, rails support, call tree output, etc.
After porting ruby-prof to Windows a couple of weeks ago, Shugo Maeda, ruby-prof's author, and I started working together. We're happy to announce the release of ruby-prof 0.4.0, which is chock full of new features:
Best of all, ruby-prof is now distributed as a gem so it's as easy to install as:
gem install ruby-prof
If you're on Windows, the gem includes a pre-built windows binary. If you're on Linux or Unix, the binary will be automatically built on intallation.
My favorite new feature - and the raison d’être for this release, is the addition of call graphs. Here is the source code for the following examples.
Most profiling tools for Ruby1 output flat profiles, which are useful for identifying which methods take the longest. They are concise and easy to understand. Let's take a look at an example to see what I mean.
For short programs, flat profiles work well. But for long programs, it's really helpful to understand more about the context in which a method is called. For example, which methods called the one we're interested in? Which methods did it call?
A quick word of warning - call graphs can be overwhelming if you haven't seen one before. Let's venture forth and take a look at one that shows the same results as the flat profile above. Quite a bit different, isn't it? If you haven't used a call graph before I've put together a little tutorial here. There are also a number of excellent examples on the Web - search Google for "gprof call graph tutorial."
The thing that got me started working on ruby-prof was that the built in Ruby profiler is beyond slow (and doesn't support call graphs). So how does ruby-prof compare?
We spent a good deal of time profiling ruby-prof, using oprofile on Linux and Rational PurifyPlus on Windows. When we started, ruby-prof added over 100% overhead to a program. Thus, if a program took 10 seconds to run the profile run would take at least 20. That's not too bad, but there was clearly room for improvement.
Internally ruby-prof maintains two main data structures. The first is a stack that keeps track of the current call sequence. The second is a hash table with one entry per method profiled per thread. The slowest part was looking up the method information in the hash table. This happens each time a method is entered or exited.
To give you some idea of the number of times this happens, take a look at the the Fixnum# method in the graph profile above. For a program that lasted only 8 seconds, Fixnum# got called a whopping 250,000 times (and these results are from last week before our optimization work, so the program really only takes around 3 or 4 seconds to run).
The key to speeding up ruby-prof was to reduce these lookups as much as possible. This was done by a combination of caching to avoid lookups, simplyifing the hash key to make lookups faster, and making the method tracking logic as simple as possible.
The result are quite encouraging. On "normal" programs, like Rails apps, ruby-prof's overhead is now less than 50% (and in fact, when I profile our unit tests it is more in the range of 10% to 20%). For programs that stress profilers, like the prime test above or a factorial method, the overhead is somewhere in the 50% to 80% range.
Next time - some results from profiling Rails.
1The latest release of Mauricio Fernandez excellent rcov extension looks like it now has this functionality
Posted by Charlie
Yesterday I wanted to profile some methods I'm using on a Rails controller. To get a feel for profiling Ruby code I put together a test case, added a "require 'prof'" to the top of the file and eagerly waited for the results. And waited, and waited, and waited. Thinking I did something wrong, I ran the code without a profiler - it took about 2 seconds. With the profiler it took so long I gave up. And this was on a dual core pentium D processor with 1 Gig of memory running Fedora Core 5.
Time for some investigation. It turns out this is a well known problem - the built-in Ruby profiler, which is written in Ruby, is so slow as to be useless. I came across two alternatives - ruby-prof, a C extension written by Shugo Maeda, and ZenProfile, an inline C exension done by Ryan Davis.
I went with ruby-prof. On Linux it was easy enough to download, build and install and it worked like a charm. But I do most of my work on my laptop which runs Windows XP. So I opened up MingW and built and installed the extension on Windows (that's not quite true, I had to hack the C a bit, more info below). But when I ran the test script I was met with a program fail message saying that the stack was empty. Ugh.
Since I find it impossible to debug extensions on Windows with MingW I fired up Visual Studio 2005, rebuilt the extension, and tried again. Same issue.
Digging deeper, it turns out the profilers (as well as the wonderful rcov project) work by registering a callback with Kernel::set_trace_func. When Ruby executes a line of code, enters a new Ruby or C method, or exists a Ruby or C method, the callback is activated.
The problem is that ruby-prof assumes that each call into a method is matched by a return - and if its not then the failure I see is triggered. To understand the problem, let's look at a super simple test case:
require 'profiler'
I said it was simple - didn't I! Here's the trace from Linux:
return start_profile call print_profile call stop_profile c-call set_trace_func
Start_profile is the method that installs the set_trace callback - so it makes sens that the first thing we see is returning from that method. Once the program is done, the profiler calls print_profile, which calls stop_profile, which calls set_trac_func which uninstalls the callback. So the method enters and returns do not balance.
Although the method names ruby-prof uses are slightly different, the problem remains the same. ruby-prof hacks through it by pushing and popping extra items on its stack to counterweigh the imbalanced method calls. Thus its hard-coded to a specific sequence of method calls. So why doesn't it work on Windows?
A quick trace running our test program on Windows shows the problem:
return start_profile return require call print_profile call stop_profile c-call set_trace_funcThere is an extra "return require" which is being generated by Ruby gems. And if you run the program in Arachno, which uses a modified version of Ruby to supports its fantastic debugger (its fast enough that I always run Rails under the debugger so I can set breakpoints at key places - definitely go check it out).
c-return set_trace_func return start_profile c-return require__ return require c-return require__ return require call print_profile call stop_profile c-call set_trace_func
It quickly becomes clear that assuming a balanced stack is a bad idea. If you look at the built in Ruby profile it doesn't make such an assumption.
These changes have been merged into ruby-prof-0.4.0 which is now available as a RubyGem.
So, I've patched ruby-prof to remove this assumption and to make it compile on Windows. I'll submit the patch to Shugo Maeda, but in the meantime, I've provided windows binaries for anyone who wants to use the profiler on windows. To install:
1. Download the windows extension, prof.xo, and put it in your ruby\lib\ruby\site_ruby\1.8\i386-msvcrt directory.
2. Download unprof.rb and put it in your ruby\lib\ruby\site_ruby\1.8 directory.
3. To use the profiler simply require 'unprof' at the top of the file
One thing to note about my changes. The self-time for the "toplevel" method will always show "0". Its looks like the Ruby profiler does the same thing, so I think this is ok.
This section is for anyone who's interested in some lower level details - feel free to skip it.
Getting ruby-prof to compile on windows required a few of the usual changes. For example, making sure that the extension's initialization method is property exported using __declspec(dllexport), etc.
However, ruby-prof provides an extra twist. It can measure time in several ways including using some low-level functionality provided by more recent Pentium and PowerPC processors. To access this information it uses this inline assembly call:
static prof_clock_t cpu_get_clock() { #if defined(__i386__) unsigned long long x; __asm__ __volatile__ ("rdtsc" : "=A" (x)); return x; #elif defined(__powerpc__) || defined(__ppc__) unsigned long long x, y; __asm__ __volatile__ ("\n\ 1: mftbu %1\n\ mftb %L0\n\ mftbu %0\n\ cmpw %0,%1\n\ bne- 1b" : "=r" (x), "=r" (y)); return x; #endif }
For x86 chips, what it does is call the rdtsc assembly function which returns the number of clock cycles that have been executed. So if you call get_cpu_clock, wait 1 second, and call get_cpu_clock again, you can calculate the chip's clock frequency. Using this information, you can time method calls. For instance, if the chip's frequency is 500Mhz and a method takes 250,000,000 cycles to complete, you can calculate it took 0.5 seconds.
This of course won't work with Visual C++ because it uses its own syntax for inline assembly calls. In this case there are couple ways of porting this code. Newer versions of Visual C++ support compiler intrinsics, and there is one for rdtsc. However, I thought it would be better to use inline assembly to support older versions. Here's the code:
static prof_clock_t cpu_get_clock() { prof_clock_t cycles = 0; __asm { rdtsc mov DWORD PTR cycles, eax mov DWORD PTR [cycles + 4], edx } return cycles; }To use this timing method you have to specifically enable it by including the following line in your ruby code.
ENV["RUBY_PROF_CLOCK_MODE"] = "cpu" require 'unprof'
However, I can't say this works very well. The calculated frequency for my chip is always different. I don't know why - my best guess is that its a Pentium M with Intel's speed step technology so the clock frequency varies to save power. However, I'm usually plugged in so I don't think that's it. Note you can tell ruby-prof your click frequency like this:
ENV["RUBY_PROF_CLOCK_MODE"] = "cpu" ENV["RUBY_PROF_CPU_FREQUENCY"]= "466000000" require 'unprof'
So my recommendation is just use the default ruby-prof timing method - it does the job perfectly well.
Posted by Charlie
I have an extra RailsConf ticket that unfortunately I can't use. The cost is $400 (face value). If you're interested send me an email at cfis@interserv.com.Posted by Charlie
Mike Williams provided some great feedback on my last post about Google Maps and coordinate systems. Let's look into two of his comments in more depth.
First, he pointed out that my formula for calculating the number of tiles was a bit misleading:
Math.pow(2, zoom)
This actually tells you either the number of tiles across or the number of tiles down. So at zoom level 2, there are 4 tiles across and 4 tiles down, for a total of 16. Thus, the correct formula is:
Math.pow(2, 2*zoom)
Its worth stopping and thinking about this for a minute. Let's do the math and see how many tiles Google has to generate to cover the Earth at different zoom levels.
Zoom |
Tiles |
0 |
1 |
1 |
4 |
2 |
16 |
3 |
64 |
4 |
256 |
5 |
1,024 |
6 |
4,096 |
7 |
16,384 |
8 |
65,536 |
9 |
262,144 |
10 |
1,048,576 |
11 |
4,194,304 |
12 |
16,777,216 |
13 |
67,108,864 |
14 |
268,435,456 |
15 |
1,073,741,824 |
16 |
4,294,967,296 |
17 |
17,179,869,184 |
18 |
68,719,476,736 |
19 |
274,877,906,944 |
20 |
1,099,511,627,776 |
At zoom level 20, it would require over 1 trillion tiles to cover the Earth.
Let's do a quick back of the envelope calculation to figure out the storage requirements. If you download one of the image tiles, you'll see that its an 8 bit png. I checked a few images of areas over land and saw that their sizes ranged from 8 to 16k. So let's say each land image occupies 10k, and that land occupies 25% of the Earth's surface. Each ocean image is roughly 100 bytes, so let's just ignore those (which is reasonable, since you only need to produce one nice blue png image as long as you don't want to create any with labels like "Pacific Ocean").
So as a rough estimate, the storage requirements in bytes can be calculated as:
0.25 * numberOfTiles * 10000
Working out the math we see:
| Zoom Level | Size (terrabytes) |
| 12 | 0.04 |
| 13 | 0.17 |
| 14 | 0.68 |
| 15 | 2.7 |
| 16 | 10.7 |
| 17 | 43 |
| 18 | 170 |
| 19 | 690 |
| 20 | 2750 |
At zoom level 14 you need 680 gigabytes of storage capacity, about the size of the largest hard drives available today. But remember the growth is exponential, so at zoom level 15 you need 2.7 terrabytes space. By the time you reach zoom level 120 you'll need 2,750 terrabyes. Of course all the zoom levels are cumulative. If add up the total its around 3700 terrabytes - a number that just a few years ago would have been unimaginable but I'm sure is commonplace today for Google, Yahoo, Amazon, Yahoo, etc. Assuming you use 500 Gigabyte hard drives, that would be 7,400 harddrives, not counting the same number needed to create a single backup.
The second point Mike brought up is that the farthest north, or south, that Google Maps covers is 85.05112877980660 degrees. How did they come up with that number? I have to admit I never considered it, but the answer is quite clever. It creates a perfect square - which of course is a lot easier to work with than a rectangle.
How do we know that - well let's work through an example to see. At zoom level 0 we know that we want to cover the Earth with a single 256 by 256 pixel bitmap. Remembering from last time, to convert from y to latitude we use this formula:
yToLat: function(y) { var latitude = (Math.PI/2) - (2 * Math.atan( Math.exp(-1.0 * y / this.radius))); return Math.radiansToDegrees(latitude); }
Using a y value of 128 (we'll ignore the false northing that Google uses) and a radius of 40.74 (256/2*Pi) the answer - you guessed it - is 85.05112877980660.
Thanks again Mike for the comments! And for anyone interested, Mike maintains a great set of tutorials about Google Maps that you should check out.
Posted by Charlie
Its finally time to apply our new knowledge about coordinate systems to Google Maps. Looking through the google maps newsgroups, you'll see lots of questions like:
Let's tackle the first two today, we'll get to the third item in a future post (alas, it requires a bit more background information first).
From last time, we know that a geodetic coordinate system consists of a datum, a projection, an origin, a unit system, two axes and perhaps an origin offset. Without further ado, this is what Google is doing:
How do I know they use a Mercator projection - by reading the obfuscated code of course! About six months ago I went looking through the code looking for "suspicious" looking equations. If you download the version 1 of the api, you'll see this code around line 608 (reformatted so its readable):
F.prototype.getLatLng=function(a,b,c,d) { if(!d) { d=new x(0,0) } d.x=(a-this.bitmapOrigo[c].x)/this.pixelsPerLonDegree[c] var e=(b-this.bitmapOrigo[c].y)/-this.pixelsPerLonRadian[c] d.y=(2*Math.atan(Math.exp(e))-Math.PI/2)/Fb return d }
Based on the function name and the use of atan and exp functions this is clearly the projection code. But which one? Well, a quick look through Wikipedia shows its a Mercator projection. With the recent release of version 2 of the api, there is now a public GMercatorClass api (thus proving the point).
Yet there is more to this story. Let's study the Mercator projection a bit more since its unusual. Here is some JavaScript that I've put together that translates from latitude/longitude to x/y and vice versa:
longToX: function(longitudeDegrees) { var longitude = Math.degreesToRadians(longitudeDegrees); return (this.radius * longitude); }, latToY: function(latitudeDegrees) { var latitude = Math.degreesToRadians(latitudeDegrees); var y = this.radius/2.0 * Math.log( (1.0 + Math.sin(latitude)) / (1.0 - Math.sin(latitude)) ); return y; }, xToLong: function(x) { var longRadians = x/this.radius; var longDegrees = Math.radiansToDegrees(longRadians); /* The user could have panned around the world a lot of times. Lat long goes from -180 to 180. So every time a user gets to 181 we want to subtract 360 degrees. Every time a user gets to -181 we want to add 360 degrees. */ var rotations = Math.floor((longDegrees + 180)/360) var longitude = longDegrees - (rotations * 360) return longitude }, yToLat: function(y) { var latitude = (Math.PI/2) - (2 * Math.atan( Math.exp(-1.0 * y / this.radius))); return Math.radiansToDegrees(latitude); }
Notice how this.radius plays a key part. Unlike most projections which map to a well defined part of the Earth (like British National Grid or the US State Plane system) you can use the Mercator projection to map to any sized surface you want.
The next key to the puzzle is zoom levels. As you use Google Maps, one thing you'll notice is that it has predefined zoom levels. In fact, there are 18 of them currently (the number of zoom levels has changed over time). Rummaging through the code a bit more, you'll also see that Google Maps splits the world into tiles. Each tile is 256 pixels square and the number of tiles across at each zoom level is given by this formula:
Math.pow(2, zoom)
So at zoom level 0, a single tile covers the Earth. At zoom level 1, four tiles cover the Earth (2 across by 2 down). At zoom level 2, sixteen tiles cover the earth (4 across by 4 down), etc. [Note - this is how version 2 of the api works, in version 1 the zoom levels are reversed].
Has a light bulb gone off in your head yet? Here's the first trick Google uses - each zoom level maps to its own Mercator projection! The projection is calculated like this:
var TILE_SIZE = 256 var tiles = Math.pow(2, zoom) var circumference = TILE_SIZE * tiles var radius = circumference/ (2 * Math.PI) var mercatorCoordinateSytem = createMercatorCS(radius)
Yet there is still more. Remember we said that each tile is 256 pixels square? What that means is that Google is mapping latitude/longitude values into an imaginary pixel space. This is quite unusual. Most projections map latitude and longitude values into feet (for the US) or meters (for the rest of the world). A good example is the road atlas in your car. You want your road atlas to be in miles so you can quickly figure out the distance between where you are at and where you are going. If it told you it was 1.7 billion pixels from Denver to San Francisco you'd soon be buying someone else's road atlas.
But on a computer screen pixels reign supreme. And by using pixels Google gets two big benefits. First, the map tiles, which are just bitmaps, are in pixels so using pixel space makes it much easier to line them up. Second, and this is more technical, it avoids having to convert pixels to feet or meters. That's problematic because a pixel is not a set size - it varies across monitors (let alone printers). Thus you usually "assume" a value (72 pixels per inch) knowing full well that your assumption is wrong. By working in pixels, and not feet or meters, Google avoids the issue entirely.
But we're still not done. If you've ever done any computer programming, you know that the top left of the screen is considered the origin (0,0) and y values increase downwards.
For Mercator projections, the natural origin is in the middle of the pixel space. Thus at zoom level one, it's at 128,128 pixels (which maps in the real world to where the equator intersects the prime meridian in the Atlantic Ocean west of Africa). In addition, y-values increase upwards.
Wouldn't it be easier though if the origin could be moved to the top left of the map and the y-value flipped? Well - from the last post time we already know how to shift the origin - use a false northing and easting. This is exactly what Google does:
var falseEasting = -1.0 * circumference/2.0, var falseNorthing = circumference/2.0,
The false Easting is the circumference in pixel space divided by two and then multiplied by negative one. Thus it moves the origin to the left edge of the first tile. In the real world, its on the international date line in the Pacific ocean.
The false northing is simply the circumference divided by two. This moves the origin to slightly north of 85 degrees.
Which leaves us with one problem. Y values on a computer screen increase downwards, y values in the Mercator projection increase upwards. This can actually be solved quite easily - multiply all y values by negative 1.
So let's review. Google divides the world into square bitmaps that are 256 square pixels. They use one bitmap to cover the world at zoom level 0, two bitmaps at zoom level 1, four bitmaps at zoom level 2, etc. For each zoom level, they create a Mercator projection, offset the origin to the west and north, and flip the y-axis.
Why do they do this? Because it means you can can divide the world into tiles, pre-render those tiles, and throw them onto a web server for fast access. Why is that important - because rending maps is SLOW. If you ever used an online GIS system or mapping site before Google you spent most of your time waiting for the map to show up.
Rending is so slow because the amount of information on a map is staggering. Let's take a typical Enterprise application - seeing if an item is in stock. Perhaps there's a few tens of million of parts in your database and you want to look one up by name. With the appropriate indices, your database will return at most a few dozen records to you.
Now imagine you're looking at a street map, say for Denver. Each one of those streets consists of multiple records in your database. Thus your database has tens, even hundreds, of millions of records. To render a map your database has to sift through them, and come up with the several thousand relevant records that make up the map. So you're already dealing with several orders of magnitude more information than with a standard database query. Next, a rendering engine needs to take those records and draw a map. This is a time consuming process because its usually done in software (2d vector graphics in GIS systems generally don't make use of the built-in routines in graphics cards). Thus generating maps on the fly just isn't fast. Although I can't vouch for this information (so don't hold me to it), I've heard that it takes Google several weeks to pre-render the United States to bitmaps (if anyone has more accurate information let me know).
So Google has done us all a great service by showing how to make interactive, fast maps online. So we're all happy, right?
Nope, we're not. Any cartographer worth his salt will tell you that using the Mercator projection for a world map is a terrible idea. Go look a the latToY equation above again. Now remember your high school trigonometry. What's sin(90) equal? One. So the equation becomes undefined at the North pole. What does that mean? It means that as you move towards the poles the Mercator projection gets worse and worse and worse. The example people always point out is Greenland. It looks the same size of South America, but is really 8 times smaller. Ouch. For those who want to know more, here is a good writeup on the problem.
So, Google has traded ease of implementation for accuracy. In reality though, its probably ok since most of the world's population doesn't live near the poles so it doesn't come into play. Also, when using Google Maps you're usually closely zoomed in so the distortions become less important.
Let's close this post with a word about scale. As you pan and zoom around on Google maps you'll see that the scale in the bottom left constantly changes. This strikes most people as truly weird since they are used to maps with set scales. But there ain' t no such thing. The scale on projected maps always varies across the map. Usually this doesn't matter since the covered area is small so the variation in scale is miniscule. But when you can pan the whole world, then it starts to become noticeable.
Intuitively its easy to see why the scale changes. Let's think about Google Maps zoom level 0. At zoom level 0 the world is fit into a 256 pixel wide image. But we know that the earth's circumference is the largest at the equator and dwindles down to zero at the poles. So as you move north or south away from the equator, the Earth has to be "stretched" to fit into the 256 wide bitmap. Thus as you move north or south the scale gets larger and larger because the same number of pixels on the screen are showing you a larger and larger percentage of the Earth's surface.
Ok - enough for today, this post is already long enough. Next time we'll talk about how to convert from mouse (ie, screen) coordinates to latitude and longitude.
Update 1: Thanks to Mike Williams who provided some great feedback. I've made a couple of updates, described in the link, based on his suggestions.
Update 2: A number of people asked how I got the width variable in the radius calcuation. Sorry, that was a type. It was meant to be the circumference. Equation is now fixed.
Google Maps / Virtual Earth / Yahoo Maps(?) all use a spherical datum based on WGS84. That is, it has the same center, orientation and scale as WGS84, but has no flattening. The radius of the sphere is the same as the semi-major axis of WGS84 (6378137 meters).
The map extents one can calculate using the formulas you provide gives you in degrees:
85. 05112877980659 to 180,85.05112877980659
…gives you a perfect square in Mercator units of size:
-20037508.342789, -20037508.342789 to 20037508.342789, 20037508.342789
I’m guessing it is more likely that this is the real reason behind the weird '85.05112877980659', and the other formula just follows from this.
Someone in your comments got a different extent which is the extent that you get using WGS84 (which is several miles off at the top and bottom).
Having a perfect equal-sided square also makes a lot more sense, since this also goes for the map tiles in pixel units.
+proj=merc +latts=0 +lon0=0 +k=1.0 +x0=0 +y0=0 +a=6378137.0 +b=6378137.0 +units=mNote this is different than using the ellipsoidal equations which would be:
+proj=merc +latts=0 +lon0=0 +k=1.0 +x0=0 +y0=0 +ellps=WGS84 +datum=WGS84 +units=m no_defs
Posted by Charlie
Its time to put together everything we've discussed in the last few posts. The following picture nicely summarizes the constituent parts of a geodetic coordinate system:
Image courtesy of GE
As you can see, a geodetic coordinate system consists of:
We've only briefly touched on the third part of a coordinate system, origins, axes and units, in our first post, so let's take a look at those in more detail.
Generally axes point in compass directions, commonly east and north, and are aligned along a parallel (line of latitude) and meridian (line of longitude).
The location of a coordinate system's origin is dependent upon the projection. Most projections specify a central meridian and a parallel - the intersection of the two is called the natural origin of the coordinate system.
It is common for the natural origin to be shifted. This is usually done to avoid negative coordinate values or extremely large coordinate values. Origin shifts are described using the terms False Easting and False Northing, where False Easting specifies an x offset and False Northing specifies a y offset. Note these values can be confusing - if the origin if shifted west (to the left), the False Easting is positive, not negative. This is easier to see in a picture:
Image courtesy of GE
A good example of a coordinate system with an origin shift is the British National Grid coordinate system. The natural origin is at 2°W, 49°N. However, the origin is shifted 400 kilometers to the west and 100 kilometers to the south so that most coordinate values are positive:
Image courtesy of GE
Units are often measured in meters or miles, but can also be given as degrees of latitude and longitude.
We now know enough to dig into how Google Maps uses coordinate systems in our next post. Till then...
I've updated the first image at the request of a few readers to make the text larger. Hope this is better!
Posted by Charlie
We've talked about ways of describing locations, using local, geocentric and geodetic coordinate systems. In the case of geocentric and geodetic coordinate systems we've been modeling the Earth as sphere or an ellipsoid.
This is fine if you have a globe on hand, but isn't otherwise practical. Its much easier working with flat maps, either printed on paper or displayed on a computer screen. In addition, latitude and longitude are angular measurements and thus tend to be more difficult to work with than more familiar cartesian x/y coordinates.
This is where projections come in - they convert points specified using some datum onto a flat surface. Since there is a lot of great information about projections on the web, I'll just cover the very basics and link to sites with additional information.
To create a projection we need to choose a projection surface - common ones are cylinders, cones and planes. For example, let's say we decide to use a cylinder. First we project each point on the ellipsoid onto the cylinder (images courtesy GE).
Then we unroll the cylinder:
And now we have a map:
Two great sites for more information about projections are the US Government's national atlas and Wikipedia.
No matter how you project points on the ellipsoid onto a flat surface you'll end up with distortions and inaccuracies. More specifically, map properties that projections change include:
The key thing to understand about projections is that each one embodies a compromise between these properties. One projection may be designed to maintain shapes at the expense of areas while another one might maintain areas at the expense of shapes. As a result there are thousands of projections - each one designed to portray the Earth's surface in a particular way.
To keep all these projections straight in your mind, it often helpful to categorize them. They can be categorized as conformal, equal area, equidistant or a compromise:
Compromise projections distort all map properties but only by a moderate amount.
Wikipedia and the national atlas have great introductory articles to projections. Another great site is the Gallery of Map Projections which shows images of a number of projections.
If you really need to get deep into projections, then a classic text is Map Projections - A Working Manual by John Synder. This book is available online from the USGS (requires a plugin to read), and details a number of projections and the mathematical formulas behind them.
If you need to add projection support to your software, check out the Proj4 project, which is used by PostGis, or the closely related libproj4 project.
And if you have questions about projections, a great source of information is the proj4 mailing list.
Posted by Charlie
There is still a bit more ground work to lay before getting to the fun stuff. We've talked about local coordinate systems and geocentric coordinate systems. Today, let's talk about geodetic coordinate systems.
Last time we saw that using geocentric coordinate systems results in measurement errors of approximately 12 miles on some parts of the Earth surface. The errors occur because the Earth isn't shaped like sphere - instead, its poles are compressed in towards the center of the Earth by about 12 miles also.
So we have to come with a more sophisticated way of modeling the Earth's surface. Not surprisingly, there is a whole science dedicated to this called geodesy. It turns out the Earth's shape is quite irregular, and therefore difficult to model. You might think that we could do something like use mean sea level, which in technical terms is known as the geoid. But that turns out not to work very well since the geoid is also highly irregular due to local gravity anomalies caused by mountains, trenches or regional variations in the crust's composition.
So instead we model the Earth's surface as an ellipsoid, which for our purposes looks pretty much like a sphere but is slightly squished in along one of its axes. Here is an image from the University of Colorado's site about coordinate systems that shows the difference between the Earth's surface, the geoid and an ellipsoid:
Deciding to model the Earth's surface as an ellipsoid isn't enough though. We have to decide the shape of the ellipsoid and how it should fit the geoid. Here is a diagram, courtesy of GE, that neatly shows the issues:
The picture displays an ellipsoid that has been designed to model one part of the Earth's surface quite accurately due both to the way it is shaped as well as the way it is fitted to the geoid. Of course, that means that it will not work very well for other parts of the Earth's surface.
This combination of an ellipsoid and the way it is fitted to the geoid is called a geodetic datum. As you quickly see, there are an infinite number of ellipsoid combinations and fitting parameters. In fact, there are over thirty different ellipsoids in use today for mapping with names like Airy, Bessel and Clarke. And hundreds of datums!
Until recently, datums were generally designed to fit particular parts of the Earth. For example, the North American Datum of 1927, commonly abbreviated as NAD27, was designed specifically for North America (surprise, surprise) and was defined by an initial point at Meade's Ranch in Kansas and used the Clarke 1866 ellipsoid.
However, by the 1950's it became increasingly important to create a datum that worked world-wide. Not surprisingly, the US military led this effort (its helpful to know where things are if you want to accurately deliver ICBMs) and developed a series of world geodetic systems (abbreviated WGS). The latest of these is called WGS84, since it was released in 1984, and uses an ellipsoid whose center is at the Earth's center. WGS84 is the system currently used by the global positioning system and therefore your GPS receiver.
We can now finally understand what latitude and longitude are. Latitude is the trickiest to understand. It is the angle between the equatorial plane and line that is normal (i.e., goes straight up) from the ellipsoid specified by some datum. Time for another picture from Richard Knippers:
So if you're still with me, you might realize that latitude and longitude are different depending on the datum! In fact, the difference between latitude/longitude points on the Earth's surface can be from several hundred feet up to half a mile in extreme cases depending on the datum you are using. Thus specifying a latitude and longitude is not enough - you also have to know what datum was used to measure them.
