Minecraft: Navigation

I plan on building a boat access only building, but my current map didn't have a large body of water that I knew of.  So, I ventured off and sure enough found a coastal region.  I then proceeded to setup a little dock to harbour boats...

...and shelter/mine access.

The cactii are not for style, they kill the bad things.

Whilst setting this up, I realized I didn't leave a trail back to spawn for myself to follow.  So, I played quite cautiously in hope of lasting long enough to craft some gear (including a compass that points to the spawn location) in order to mark a trail to my new site.  Sadly, after escaping a few close calls, I made a fatal error and died a gruesome death.  I'm shamed to admit I mined out the ore block I was standing on and fell through into a pit of zombies.  Now, I was back at spawn and left to guess as to where my dock and lodge were hiding.

The 'O' marks the spawn point and the 'X' marks my dock.  All that explored area around the 'O' that is not in the direction of the 'X' is the area I explored trying to find the 'X'.

Overhead

Before I had the nifty application that produced this map, I just wandered in the direction I thought I had gone before.  I eventually died in a self dug pit from the arrows of a skeleton maurader. That is how I explored the area above the 'O'.  After respawning I downloaded cartographer I realized I needed to head West! That is how I explored the are below and to the right of the 'O'.  See, it turns out Cartographer takes a nod from the Romans and puts East on the top of the map.  Once I figured that out, I found it with little hassle.

The search wasn't in vain though, I did find an awesomely high mountain that seems fitting for a water slide or hermit hut.  It's the red blob on the upper right corner.

Height Map

As a bonus, here's a map from a different cartography program called AlphaVespucci.

Oblique Angle