4 ms·

It looks like this algorithm will give you better and better accuracy as you get farther from the equator. There must be some way to compress the location infor

It looks like this algorithm will give you better and better accuracy as you get farther from the equator. There must be some way to compress the location information with that in mind and shave a couple of digits off the result?

sesqu 16y ago
This has always bothered me, as well. I don't like the solution the military grid reference system came up with: http://en.wikipedia.org/wiki/File:MGRSgridSouthPole.png http://en.wikipedia.org/wiki/File:MGRSgridSouthPole.png I'd much prefer a solution that removed the square grid requirement and the dissimilar angular coordinates, divided the earth into roughly equally sized and shaped sectors, and ideally was hierarchical so that you could achieve a naming scheme similar to the geohash. A bit of googling led me to this picture, which looks promising: http://icon.enes.org/swm/icoswp/node3.html http://icon.enes.org/swm/icoswp/node3.html
- eru 16y ago
  Yes, the military grid reference system looks ugly. Icosahedron based coordinates should be much nicer and more symmetrical. There's an interesting observation about normal distributions that may prove helpful--especially if you find a way to use randomness to generate a coordinate system. If you have n pairwise independent identically normal distributed random variables X_i, and normalize them to the unit sphere Z := X * 1/length(X) then Z will be distributed equally on the surface of the unit sphere (in the sense that the distribution is symmetric under any rotation around the origin). If you add some ideas from arithmetic coding and/or the theory for de-randomization of algorithms, you might be able to get a working coordinate system out of this.
  - sesqu 16y ago
    No, that's just because P(X=x)*P(Y=y) = P(Z²=(x²+y²)). I think you could do a reasonable job by dividing first into two hemispheres, then into six(?) triangular sectors each, then recursively into four subsectors each. This would give log4(510 Mkm²/2/6/100 m^2) = 19.3 recursions, or 43 bits to reach a 100m² accuracy, assuming it really does divide nicely. Won't be square, though. Then you'd have to decide whether to use the remaining 5 bits on a checksum, or to allow arbitrary precision. Or I suppose you could add a checksum there, and interpret any further bytes as unchecked precision. I wonder if six subsectors are required in the first phase to construct the voronoi cells. The triangular scheme should work fine with four, which seems more elegant.
    - eru 16y ago
      > No, that's just because P(X=x)*P(Y=y) = P(Z²=(x²+y²)). I found a way to make my idea work, anyway.
    - sesqu 16y ago
      After a bit of further thought, I realized that the triangular sectors aren't equilateral after just one iteration. The angles at the equator are 90°, and the polar angles are 180°/n - works when n=4. But then the four nested ones will be 3x(90° 60° 60°) and one equilateral, and so no longer identical (and probably not of equal areas). For area-equality, shape-inequality, a recursive three-division becomes also worthy of consideration.
      - eru 16y ago
        Might work. Here's what I thought of: Use a Cartesian coordinate system with the centre of the sphere as its origin and the radius of the sphere normalized to 1. Each point on the square has coordinates x_1,x_2,x_3. The new coordinates will live in [0,1]^3 (i.e. three real numbers between 0 and 1). To convert, do the following: Generate a random number r from a N(0,1) normal distribution. For each coordinate determine the quantile of q_i := rx_i in the N(0,1) normal distribution. (This results in 0 <= q_i <= 1.) Take the triple (q_1,q_2,q_3) and express it as a binary number. Bonus points for using octal numbers like this: Q(j) = q_1(j) + 2q_2(j) + 4*q_3(j) where Q(j) is the j-th octal digit of the number Q after the comma and q_i(j) is the j-th digital digit of the number q_i after comma. (This octal scheme has the property that you can cut off at any time for getting a less accurate description of the location.) This coordinate scheme is redundant. Also a uniform distribution of random points on the surface of the sphere, will lead to a uniform distribution of coordinates in this scheme.
frankus 16y ago
If anything you'd want less resolution near the poles, since they are almost uniformly less populated and hence there is less potential ambiguity between, say, individual dwellings.
rsaarelm 16y ago
I wonder how this'd work: Take the XYZ coordinates of a vector on an unit sphere with North Pole being at Z=1 and lat/long 0,0 at X=1. Drop the smallest of XYZ, keep the other two. Use 3 bits to store which of XYZ was dropped and whether it was positive or negative. The point can then be reconstructed since the vector must always have length 1, and the encoding scheme will always drop that coordinate which would contribute most to loss of precision when going from 3 coordinates to 2.
- deleted 16y ago
  [deleted]
abecedarius 16y ago
Earth's surface area = 5.1e14 square meters. Give each of 5.1e12 same-sized patches an integer identifier (one way or another): that's 8.3 base-34 digits (disallowing 'I' and 'O'). If you detect all single-character substitution errors, that rounds up to 10 characters -- oh, well. (This kind of scheme would get you better worst-case resolution with your 10 characters. I'm not sure what it is for the posted code.)

sesqu 16y ago

This has always bothered me, as well. I don't like the solution the military grid reference system came up with: http://en.wikipedia.org/wiki/File:MGRSgridSouthPole.png http://en.wikipedia.org/wiki/File:MGRSgridSouthPole.png I'd much prefer a solution that removed the square grid requirement and the dissimilar angular coordinates, divided the earth into roughly equally sized and shaped sectors, and ideally was hierarchical so that you could achieve a naming scheme similar to the geohash. A bit of googling led me to this picture, which looks promising: http://icon.enes.org/swm/icoswp/node3.html http://icon.enes.org/swm/icoswp/node3.html

eru 16y ago
Yes, the military grid reference system looks ugly. Icosahedron based coordinates should be much nicer and more symmetrical. There's an interesting observation about normal distributions that may prove helpful--especially if you find a way to use randomness to generate a coordinate system. If you have n pairwise independent identically normal distributed random variables X_i, and normalize them to the unit sphere Z := X * 1/length(X) then Z will be distributed equally on the surface of the unit sphere (in the sense that the distribution is symmetric under any rotation around the origin). If you add some ideas from arithmetic coding and/or the theory for de-randomization of algorithms, you might be able to get a working coordinate system out of this.
- sesqu 16y ago
  No, that's just because P(X=x)*P(Y=y) = P(Z²=(x²+y²)). I think you could do a reasonable job by dividing first into two hemispheres, then into six(?) triangular sectors each, then recursively into four subsectors each. This would give log4(510 Mkm²/2/6/100 m^2) = 19.3 recursions, or 43 bits to reach a 100m² accuracy, assuming it really does divide nicely. Won't be square, though. Then you'd have to decide whether to use the remaining 5 bits on a checksum, or to allow arbitrary precision. Or I suppose you could add a checksum there, and interpret any further bytes as unchecked precision. I wonder if six subsectors are required in the first phase to construct the voronoi cells. The triangular scheme should work fine with four, which seems more elegant.
  - eru 16y ago
    > No, that's just because P(X=x)*P(Y=y) = P(Z²=(x²+y²)). I found a way to make my idea work, anyway.
  - sesqu 16y ago
    After a bit of further thought, I realized that the triangular sectors aren't equilateral after just one iteration. The angles at the equator are 90°, and the polar angles are 180°/n - works when n=4. But then the four nested ones will be 3x(90° 60° 60°) and one equilateral, and so no longer identical (and probably not of equal areas). For area-equality, shape-inequality, a recursive three-division becomes also worthy of consideration.
    - eru 16y ago
      Might work. Here's what I thought of: Use a Cartesian coordinate system with the centre of the sphere as its origin and the radius of the sphere normalized to 1. Each point on the square has coordinates x_1,x_2,x_3. The new coordinates will live in [0,1]^3 (i.e. three real numbers between 0 and 1). To convert, do the following: Generate a random number r from a N(0,1) normal distribution. For each coordinate determine the quantile of q_i := rx_i in the N(0,1) normal distribution. (This results in 0 <= q_i <= 1.) Take the triple (q_1,q_2,q_3) and express it as a binary number. Bonus points for using octal numbers like this: Q(j) = q_1(j) + 2q_2(j) + 4*q_3(j) where Q(j) is the j-th octal digit of the number Q after the comma and q_i(j) is the j-th digital digit of the number q_i after comma. (This octal scheme has the property that you can cut off at any time for getting a less accurate description of the location.) This coordinate scheme is redundant. Also a uniform distribution of random points on the surface of the sphere, will lead to a uniform distribution of coordinates in this scheme.

frankus 16y ago

If anything you'd want less resolution near the poles, since they are almost uniformly less populated and hence there is less potential ambiguity between, say, individual dwellings.

rsaarelm 16y ago

I wonder how this'd work: Take the XYZ coordinates of a vector on an unit sphere with North Pole being at Z=1 and lat/long 0,0 at X=1. Drop the smallest of XYZ, keep the other two. Use 3 bits to store which of XYZ was dropped and whether it was positive or negative. The point can then be reconstructed since the vector must always have length 1, and the encoding scheme will always drop that coordinate which would contribute most to loss of precision when going from 3 coordinates to 2.

deleted 16y ago
[deleted]

abecedarius 16y ago

Earth's surface area = 5.1e14 square meters. Give each of 5.1e12 same-sized patches an integer identifier (one way or another): that's 8.3 base-34 digits (disallowing 'I' and 'O'). If you detect all single-character substitution errors, that rounds up to 10 characters -- oh, well. (This kind of scheme would get you better worst-case resolution with your 10 characters. I'm not sure what it is for the posted code.)