Apr 25, 2009

How to download full resolution satellite images from Google Earth/Maps

Google Maps uses the following technique to serve images: It displays 256x256px blocks of images from their server. The server displays the image from the given parameters, for example:
So, with a script, you can fetch all the images from the starting X and Y, to the ending and then stitch them together piece by piece. Below is an example how to get the parameters for the image (v,x,y,z) And here's a script that does all the work:
error_reporting(E_ALL ^ E_NOTICE);

// Bottom Left
//Top Right

//How big is the block (in pixels)
$block_width = 256;
$block_height = 256;

//I don't know what that is, but look at the URL
$v = 38;
//Zoom level
$z = 18;

//Get these parameters from the url
$start_x = 141234;
$start_y = 93105;

$end_x = 141273;
$end_y = 93147;

//Do some simple math... Dimensions of the panorama
$dim_x = $end_x - $start_x;
$dim_y = $end_y - $start_y;

$dim_x *= $block_width;
$dim_y *= $block_height;

print("$dim_x x $dim_y px\n");

//Allocate memory space for the panorama
$img = imagecreatetruecolor($dim_x,$dim_y);

for($x = $start_x ; $x <= $end_x ; $x++) {
 for($y = $start_y ; $y <= $end_y ; $y++) {
  $f = "$x-$y-$z.jpg";
  $url = "http://www.najdi.si/servlet/ServletRedirectTileImage?x=$x&y=$y&zl=$z";
  $url = "http://khm3.google.com/kh/v=$v&x=$x&y=$y&z=$z";
  //Download the block
  $cache = "wget \"$url\" -O $f";
  //Put it on the panorama
  $block = imagecreatefromjpeg($f);
  imagecopy($img, $block, ($x-$start_x)*$block_width, ($y-$start_y)*$block_height, 0, 0, $block_width, $block_height);

I also noticed that many mapping sites are using the same technique. End result:


Apr 14, 2009

Java:: Coin Change Problem - dynamic programming - memoization - recursion

Problem: We have a series of coins, eg. 1, 3, 5 and we're trying to find the least possible number coins to sum up to a value, eg. 11 The smallest possible solution is 3 coins (5+5+1, 5+3+3).

Solution: The Greedy algorithm only works in special cases, but we're trying to find the ultimate, smallest and fast solution.

The goal is to check all possibilities, which can take a lot of time, if we don't use memoization. The solution below is a recursive function with two arguments:
  • int[] k - table of coins (1, 3, 5) ordered ascending
  • int val - the value we wish to solve
Read the comments for more information
 public static Hashtable<Integer, Integer> solved = new Hashtable<Integer, Integer>();
 public static int kovanci(int[] k, int val) {
  // we've reached the end of recursion - a leaf
  // if the value is less than zero it means that the current combination is not solvable
  // if the value is zero, it means it is solvable
  if (val <= 0) return val;

  // for as many coins try to decrease the value for the coin value 
  // and try to solve the smaller problem
  int min = -1; //default: if it's not solvable
  for (int i = k.length - 1; i >= 0; i--) {
   // if the coin k[i] exists in the solution, it means the solution is
   // solutions(value - coin_value) + 1
   // eg. we have coins: 1, 3, 5 and the value is 11
   // if the coin 5 exists in the solution, try to solve the problem for value 11-5 = 6
   // the solution is smaller_solution + 1
   int newVal = val - k[i];
   int r;

   // dynamic programming - memoization
   // if we already have the minimum for the new value, fetch it (with time complexity O(1)), 
   // so that we don't recursively re-solve the problem and waste time
   if (solved.get(newVal) != null) {
    //solution = smaller_sollution + 1
    r = solved.get(newVal) + 1;
   } else {
    //try to solve the smaller problem
    r = kovanci(k, newVal);
    //if the solution is valid, the new solution is smaller_solution + 1
    if (r >= 0) r++;
    //else, keep the negative value - it means that it's not valid
    //eg: coins 3, 5, value 11 is not solvable, the solution is -1
   // from all of the solutions, get the minimum value
   // and skip invalid solutions ( less than zero )
   if ((r > 0) && (min == -1 || r < min)) {
    min = r;
  // dynamic programming - memoization
  // once we do get the smallest possible solution, save it for later use
  // it saves A LOT of time and useless work, that's already been done
  solved.put(val, min);
  return min;