{"id":947,"date":"2009-08-14T16:00:06","date_gmt":"2009-08-15T00:00:06","guid":{"rendered":"https:\/\/www.reenigne.org\/blog\/?p=947"},"modified":"2011-08-08T13:44:05","modified_gmt":"2011-08-08T20:44:05","slug":"improved-geohashing-algorithm","status":"publish","type":"post","link":"https:\/\/www.reenigne.org\/blog\/improved-geohashing-algorithm\/","title":{"rendered":"Improved geohashing algorithm"},"content":{"rendered":"

Geohashing<\/a> is an awesome idea (though I've never actually gone to any of the hash points). However, it does suffer from some problems - often the chosen location will be too far away, or in an inaccessible area. It is also slightly biased towards the poles (though because few people live in the polar regions this isn't a particularly big deal for most people). It would be nice to have an improved algorithm which solves these problems.<\/p>\n

We'll start the same way, by hashing the date and that date's DOW opening to get a set of 128 random bits R.<\/p>\n

Given any area A we want to find a function (which we'll call f(A)) mapping a set of bits R onto a point x, (f(A))(R) = x. We would also like to have the property that if B is a subset of A containing x and if (f(A))(R) = x then (f(B))(R) = x. So if the New York State meetup happened to be in New York City, all the people who were just going to the New York City meetup would be there too. Another desirable property would be if the points (f(A))(R) were evenly spread throughout A.<\/p>\n

Here is an algorithm that I think fulfills both properties.<\/p>\n

First, use R to pick a random point on the globe, taking 64-bit random floating point fractions u and v in [0,1) from R in the usual way and then transforming them into longitude and latitude as:
\n\\displaystyle long = 360frac(u+a(N))-180
\n\\displaystyle lat = \\frac{180}{\\pi}cos^{-1}(2frac(v+b(N))-1)
\nWhere frac takes the fractional part, leaving a number between 0 and 1 (one could also use XOR instead of add and frac) and N is the smallest integer > 0 that causes the resulting coordinates to end up inside A.<\/p>\n

a and b are functions that find points that are furthest away from any tried so far. They have binary expansions as follows:<\/p>\n

\r\nN  a(N)  b(N)  c(N)     d(N)\r\n0  0.000 0.000 0.000000 0.000000\r\n1  0.100 0.100 0.110000 0.100000\r\n2  0.100 0.000 0.010000 0.010000\r\n3  0.000 0.100 0.100000 0.110000\r\n4  0.010 0.010 0.001100 0.001000\r\n5  0.110 0.110 0.111100 0.101000\r\n6  0.110 0.010 0.011100 0.011000\r\n7  0.010 0.110 0.101100 0.111000\r\n8  0.010 0.000 0.000100 0.000100\r\n9  0.110 0.100 0.110100 0.100100\r\n10 0.110 0.000 0.010100 0.010100\r\n11 0.010 0.100 0.100100 0.110100\r\n12 0.000 0.010 0.001000 0.001100\r\n13 0.100 0.110 0.111000 0.101100\r\n14 0.100 0.010 0.011000 0.011100\r\n15 0.000 0.110 0.101000 0.111100\r\n16 0.001 0.001 0.000011 0.000010\r\n<\/pre>\n
And so on, to as many binary places as you need. If you interleave the bits of a(N) and b(N) you get c(N), which looks like d(N) but with each even bit XORed with the bit to its left. d(N) is the binary expansion of the integers but with the bits in the reverse order (and flipped to the other side of the binary point).<\/p>\n
The sequences a and b together are related to the Bayer matrix which describe a 2D ordered dither. If you want 65 shades of grey but only have a grid of 8x8 pixels, each of which can only be black or white, the most regular patterns with n black bits are described by those that have 8a(N) and 8b(N) black if N\n","protected":false},"excerpt":{"rendered":"
Geohashing is an awesome idea (though I've never actually gone to any of the hash points). However, it does suffer from some problems - often the chosen location will be too far away, or in an inaccessible area. It is also slightly biased towards the poles (though because few people live in the polar regions […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[40],"tags":[],"class_list":["post-947","post","type-post","status-publish","format-standard","hentry","category-random"],"_links":{"self":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts\/947","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/comments?post=947"}],"version-history":[{"count":7,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts\/947\/revisions"}],"predecessor-version":[{"id":1348,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts\/947\/revisions\/1348"}],"wp:attachment":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/media?parent=947"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/categories?post=947"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/tags?post=947"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}